c - 如何划分大数？

Question

我有一个大数字（整数，无符号）存储在 2 个变量中（如您所见，数字的高位和低位部分）：

unsigned long long int high;
unsigned long long int low;

我知道如何添加或减去其他一些此类变量。

但我需要除以那种数字。怎么做？我知道，我可以减去 N 次，但是，也许，还有更多更好的解决方案。;-)

语言：C

score 6 · Accepted Answer

是的。这将涉及转换，我不建议在 C 中这样做。这是汇编程序仍然可以证明其价值的罕见示例之一，很容易使事情运行速度提高数百倍（而且我不认为我在夸大其词这个。）

我并没有声称完全正确，但以下内容应该可以帮助您：

(1) 将结果初始化为零。

(2) 将除数尽可能多地向左移动，不要让它变得大于被除数。

(3) 从被除数中减去移位的除数，结果加一。

(4) 现在将除数右移一次，直到它小于剩余的被除数，并且对于每个右移，将结果左移一位。除非满足停止条件，否则返回 (3)。（停止条件必须是“除数为零”，但我不确定。）

回到一些真正的编程问题真的很棒:-)

score 2 · Accepted Answer

我知道，我可以减去 N 次，但是，也许，还有更多更好的解决方案。

当 N 很大时，减 N 次可能会很慢。

更好（即更复杂但更快）将是移位和减法，使用您在小学学习的算法对十进制数进行长除法。

[也可能有对此类数字的 3rd-party 库和/或特定于编译器的支持。]

score 2 · Accepted Answer

2

您是否查看过任何大型库，例如GNU MP BigNum？

于 2009-06-19T17:28:04.153 回答

score 0 · Accepted Answer

您可以实现对字符串数组进行除法的“BigInt”类型算法。为每个高低对创建 1 个字符串数组并进行除法。将结果存储在另一个字符串数组中，然后转换回高、低整数对。

由于语言是 C，因此数组可能是字符数组。考虑它类似于我上面提到的“字符串数组”。

score 0 · Accepted Answer

您可以使用汇编程序循环和“带进位 (adc/sbb) 的加/减”指令对任意大的二进制对象进行加减运算。您可以使用它们实现其他操作。我从来没有调查过除了这两个之外的任何事情。

score 0 · Accepted Answer

如果您的处理器（或您的 C 库）具有快速的 64 位除法，则可以将 128 位除法分解为多个部分（与在具有 16 位除法的处理器上进行 32 位除法相同的方式）。

顺便说一句，如果您知道被除数和除数的典型值，您可以使用各种技巧。这些数字的来源是什么？如果你的很多案子都能很快解决，偶尔的案子可能需要很长时间。

此外，如果你能找到一个近似答案是可以的情况，这就为许多快速近似打开了大门。

score 0 · Accepted Answer

唔。我想如果你有一些“高”的空间，你可以把它全部上移一位，除以数字，然后将余数加到低位剩余的顶部数字，然后除以数字，然后将所有内容移回。

score 0 · Accepted Answer

根据我下面的评论者，我之前的回答很愚蠢。

很快，我的新答案是，当我过去尝试这样做时，它几乎总是涉及移位，因为它是唯一可以应用于多个“单词”的操作，如果你愿意的话，让它看起来就好像它是一个大字一样（除了必须跟踪结转位）。

有几种不同的方法，但我不知道有什么比使用轮班更好的大方向，除非你的硬件有一些特殊的操作。

score 0 · Accepted Answer

0

这是另一个做 128 位算术的库。 GnuCash：Math128。

于 2009-06-19T17:38:50.240 回答

9 回答 9