如何划分大的数字和使用什么样的算法 [英] How to divide large numbers and what algorithm to use
问题描述
我要处理非常大的数字，我试图使用数组的工作。我已经执行了乘法运算，但现在我要实现的除法运算。
I want to manipulate really big numbers and I am trying to work with arrays. I have already implemented the multiplication operation, but now I want to implement the division operation.
我想知道哪种算法（S）我应该使用？是否有可能使用牛顿迭代师的算法或者应我用的是我们在学校里学到的算法？
I was wondering which algorithm(s) should I use? Is it possible to use the Newton–Raphson division algorithm or maybe should I use the algorithm that we learned in the school?
PS：我知道有一些大的数字工作的许多库，但我想这样做练习
PS: I know that there are many libraries that work with big numbers, but I want to do this for practice.
推荐答案
这些都是我最喜欢的算法，我使用：
These are my favorite algorithms I use:
-
二进制除法
看看这里： http://courses.cs.vt.edu/~ cs1104 / BuildingBlocks / divide.030.html
这是你应该从什么。这并不是说慢，这很简单。不要忘记适当地测试你的+， - ，＆LT;＆LT;，＆GT;＆GT;操作，然后再开始。他们应该完美地在任何给定的输入
Binary division
Look here: http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html
This is what you should start with. It's not that slow and it is simple. Do not forget to properly test your+, -, <<, >>operations before you start. They should work flawlessly on any given input
司半个位算术
看看这里：<一href="http://stackoverflow.com/a/19381045/2521214">http://stackoverflow.com/a/19381045/2521214
随着稍加调整就可以使其适应阵列。用途 +， - ，*，/，％。如果$ C C $它正确的要快很多，然后二进制除法。
Division by half the bits arithmetics
Look here: http://stackoverflow.com/a/19381045/2521214
With little tweaking you can adapt it to arrays. Uses +, -, *, /, %. If you code it properly should be much faster then Binary division.
逼近师
看看这里：<一href="http://stackoverflow.com/a/18398246/2521214">http://stackoverflow.com/a/18398246/2521214
或为X ^ 2，X *这里Ÿ一些加速：快速BIGNUM平方米计算
这是更适合浮点/定点除法。这是一个有点难以理解，但速度和准确性是值得的。此外，还有很多其他的近似算法在那里，因此谷歌！
approximation of division
Look here: http://stackoverflow.com/a/18398246/2521214
Or for some speed up of x^2, x*y here: Fast bignum square computation
This is more suited for floating/fixed point division. It's a little bit harder to understand, but the speed and accuracy is worth the while. Also, there are many other approximation algorithms out there, So google!
这篇关于如何划分大的数字和使用什么样的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
