algorithm - 如何划分大数以及使用什么算法

Question

我想处理非常大的数字，并且正在尝试使用数组。我已经实现了乘法运算，但现在我想实现除法运算。

我想知道我应该使用哪种算法？是否可以使用牛顿-拉夫森除法算法，或者我应该使用我们在学校学习的算法？

PS：我知道有很多库可以处理大数字，但我想这样做是为了练习。

Answer 1

这些是我最喜欢的算法：

1. 二进制除法
   看这里：http
   ://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html 这是你应该开始的。它不是那么慢而且很简单。不要忘记+, -, <<, >>在开始之前正确测试您的操作。他们应该在任何给定的输入上完美地工作

2. 除以一半的位算术
   看这里：https
   ://stackoverflow.com/a/19381045/2521214 只需稍加调整，您就可以将其调整为数组。用途+, -, *, /, %. 如果您正确编码它应该比二进制除法快得多。

3. 除法的近似
   看这里：https
   ://stackoverflow.com/a/18398246/2521214 或者为了加快 x^2, x*y 这里：快速 bignum 平方计算
   这更适合浮点/定点除法。这有点难以理解，但速度和准确性是值得的。此外，还有许多其他近似算法，所以谷歌！