将两个数字相除超过 50 位（最大 200）算法

Question

除两个多于50位但少于200的数字的最佳方法是什么.

我有结构来表示一个数字：

struct number{

     int digit[MAX_SIZE]; // MAX_SIZE = 5;
     bool negative; // Is it negative or positive number
};

我在尝试实现此算法时遇到的问题是，如果我试图将一个数字 'n' 除以一个数字 'm' (n > m) 有更多的数字然后你可以存储在一个变量中，你怎么划分它？

例如： 1234567891234567891234567 / 12345678912345678

我的第一个猜测是 重复减法 ，但这不是太慢了吗？

Answer 1

想想你是如何手工完成的：

你先计算最高位。如果数字足够大，您可以通过重复减法来实现，一次找到一个数字。

你的情况：第一个数字有25位数字，第二个数字有17位数字。

所以你从1E8对应的数字开始。

这是一些 C 风格的伪代码。

struct number n1 = 1234567891234567891234567;
struct number n2 = 12345678912345678;
int start = floor(log10(n1) - log10(n2));   // Position of most significant digit in answer
struct number result = 0;
int i,j;
struct number remainder = n1;

// Start with the most significant digit
for i = start to 0 {
  // Find the highest digit that gives a remainder >= 0
  for j = 9 to 0 step -1 {
    if (remainder - j * n2 * pow(10, i) >= 0) {
        // We found the digit!
        result = result + j * pow(10, i);
        remainder = remainder - j * n2 * pow(10, i);
        break; // Move on to the next digit
    }
  }
}
// We now have the result and the remainder.

将两个数字相除超过 50 位（最大 200）算法

Dividing two numbers with more than 50 digits(max 200) algorithm

algorithm

divide