c++ - 用于划分非常大的数字的算法

Question

我需要编写一个算法(我不能使用任何 3rd 方库，因为这是一个作业)来划分(整数除法， float 部分并不重要)非常大的数字，例如 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

等等等等。使用这种策略，你可以有任何数字长度，并且只需要在内存中为 int(除数)和 double(除数)保存足够的数字。 (假设我的这些条款是正确的)。您将结果存储为结果字符串中的最后一位。

当您遇到没有数字剩余且计算不会进行 1 次或更多次的点时，您会返回已格式化为字符串的结果(因为它可能比 int 大)。