划分非常大的数字的算法

Question

我需要编写一个算法(我不能使用任何第三方库,因为这是一个赋值)来划分(整数除法,浮动部分并不重要)非常大的数字,如100 - 1000位数.我找到了http://en.wikipedia.org/wiki/Fourier_division算法,但我不知道这是不是正确的方法.你有什么建议吗？

1) check divisior < dividend, otherwise it's zero (because it will be an int division)
2) start from the left
3) get equal portion of digits from the dividend
4) if it's divisor portion is still bigger, increment digits of dividend portion by 1
5) multiply divisor by 1-9 through the loop
6) when it exceeds the dividend portion, previous multiplier is the answer
7) repeat steps 3 to 5 until reaching to the end

Answer 1

我认为像小学一样划分"长"的方式将是一条潜在的路线.我假设你收到原始数字作为字符串,所以你要做的是解析每个数字.例:

第0步:

   /-----------------
13 | 453453453435....

第1步:"13进入4？0多少次？

     0
   /-----------------
13 | 453453453435....

第2步:"13进入45多少次？3

     03
   /-----------------
13 | 453453453435....
   - 39
     --
      6

第3步:"有多少次13进入63？4

使用此策略,您可以拥有任何数字长度,并且只需要在内存中保留足够的数字(intisis)和double(dividend).(假设我的条款合适).您将结果存储为结果字符串中的最后一位数字.

当你遇到没有数字并且计算不会进行1次或多次的点时,你返回的结果已经被格式化为字符串(因为它可能大于int).

Answer 2

实现大数的最简单的除法算法是移位和减法.

if numerator is less than denominator then finish
shift denominator as far left as possible while it is still smaller than numerator
set bit in quotient for amount shifted
subtract shifted denominator from numerator
repeat
the numerator is now the remainder

转变不一定是文字.例如,您可以编写一个算法来从另一个值中减去左移位值,而不是在减去之前实际移动整个值.同样可以进行比较.

长划分很难实现,因为长划分中的一个步骤是长划分.如果除数是一个整数,那么你可以很容易地进行长除法.

Answer 3

Knuth,Donald,计算机程序设计的艺术,ISBN 0-201-89684-2,第2卷:半数值算法,第4.3.1节:经典算法