algorithm - 将两个数字相除超过 50 位(最大 200)算法

Question

除两个大于50 位但小于200的数字的最佳方法是什么。

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

struct number{

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

我在尝试实现此算法时遇到的问题是，如果我尝试将一个数 'n' 与一个数 'm' 相除 < strong>(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.