巨大数字的算术

• 下载源文件 - 5.78 KB

引言

我最近参与了一个涉及繁重数学运算、素数提取的项目，这需要处理非常大的数字。任何处理过这些问题的人都知道，数字会很快变得非常大，而且在某个点，很快就会意识到标准数据类型的容量根本不足，然后你就会开始问自己如何对两个超过 Int64 或 double 限制的数字执行简单的加法。因此，我开始构建自己的高效数字运算代码，令人惊讶的是，我发现自己实际上在编写一些有趣的东西。所以，我想分享我的经验。

前言

问题

实际上有两个目标要实现——创建一个性能良好且精确的库，其次，使其可用到可以像使用其他内置数值类型（例如 int）一样使用新类型的程度。

要创建一个高效的自定义数值类型，起点是考虑如何构建其内部结构并实现加法和减法等基本算术方法。

所有阅读本文的人都应该很有信心通过手动添加或减去两个数字，无论它们的长度如何。然而，即使是最现代的计算机也会发现这很困难，所以我们必须帮助它们，并向它们展示如何做。

加法

小学一年级。而且你很难找到或实现一个更简单的模型——从末尾开始，相加两个数字，记住溢出并将它加到下一次迭代中，等等。关于加法，我们应该记住的是，两个相加的数字的结果永远不会比较长的一个的长度加一更长。另外，如果两个数字中有一个是负数，这就不再是加法，而是减法。如果两个数字都是负数，那么就是加法，但结果将是负数。

减法

尽管如上所述很简单，但从计算机的角度来看，这需要额外的逻辑——从 200 中减去 800。如果你这样做

 200
-800
-----
?400 - you end up nowhere. 

你必须首先找到两个数字中绝对值较大的那个，然后用较小的数减去较大的数。如果你不得不交换数字的位置，那么你也会交换符号。

 800
-200
-----
 600 - and add '-' in front to get -600

与加法一样，如果任何一个数字是负数，这就会变成加法。

派生方法

我故意省略了乘法和除法作为基本方法，因为它们实际上是加法和减法的派生。将一个数字加给自己十次，这等同于将一个数字乘以十。从另一个数字中减去一个数字 n 次，直到结果变为零，你就得到了除法结果 n。

即使是其他更复杂的方法，如求幂和开方，也都是上述方法的派生。

剩余内容

剩下的就是你的算术类型不会自行开始加减。你还需要一组运算符来支持对它们的操作。理想情况下，最终你希望在代码中达到一种情况，你可以简单地说

C = A + B;
Or
If ( A > B ) { C = A - B; }

实现

好的，让我们开始写代码吧。请注意，为了便于理解，我将使用更多伪代码而不是直接可用的代码（你可以在随附的源代码中找到）。另外，我将只关注整数运算。本文不考虑小数。

让我们从头开始——第一个问题是——如何为一个你即将创建的自定义类型赋值？嗯，你显然需要另一个内置变量来传递信息。虽然你可以传递一个整数形式的数字分数数组，但最简单的方法是传递一个只包含数字字符的字符串。在此示例中将使用此方法，因为它代表了演示中最清晰的方法。

private List<int> Digits = new List<int>();

public BigNumberInit(string nr)
{
    int i;

    for (i = 0; i < nr.Length; i++) {
        
        // check here if string contains only numbers and 
        // +/- signs at start
    
        if(i==0 && nr[i]=='-') {
            IsNegative = true;
        } else {
            Digits.Add(int.parse(nr[i]));
        }
    }
}

同样，我将一一介绍操作，这次附带代码示例。

加法

实际上，并非所有加法都是加法。例如，如果你将一个负数加到一个正数（反之亦然），这实际上是减法，所以立即排除这些情况，转为执行减法。

private static BigNumber operator +(BigNumber A, BigNumber B) {
    ...
    if (A.IsNegative && B.IsNegative) { return -(A.Abs() + B.Abs(); }
    if (A.IsNegative && B.IsPositive) { return (B - A.Abs()); }
    if (A.IsPositive && B.IsNegative) { return (A - B.Abs()); }
    ...
}

所以，你有两个字符串，转换为整数数组，然后，你将希望依靠你计算机的计算器。逐个字符地选择，将它们解析为整数并执行加法，记住溢出，然后将结果放回结果字符串。

不过，你得注意一件事；在开始遍历字符串的字符之前，你必须确定应该遍历多远。所以，首先找到“更长的”数字——数字位数更多的那个，或者其字符串表示形式具有更大的“.Length”属性的那个。迭代永远不会超过最长数字的长度加一。如果你遇到溢出，只需将其附加到结果字符串并将其整数值添加到 Digits 数组。

减法

与加法一样，首先排除你实际上是进行加法而不是减法的情况。

private static BigNumber operator -(BigNumber A, BigNumber B) {
    ...
    if (A.IsNegative && B.IsNegative) { return B.Abs() - A.Abs(); }
    if (A.IsNegative && B.IsPositive) { return -(A.Abs() + B); }
    if (A.IsPositive && B.IsNegative) { return (A + B.Abs()); }
    ...
}

与加法不同，在减法时，你最终得到的长度最多是较大数字的长度减去较小数字的长度加一（101-1 = 100，101 - 101 = 0，99-101 = -2，1-101 = -100，50-100 = 0-50，等等）。如果你得到最后一个元素为零，只需取子字符串或删除 Digits 数组的最后一个元素。

乘法

乘法非常简单

public static BigNumber operator *(BigNumber A, BigNumber B)
{
    BigNumber R=0, i;

    for(i=0;i<B;i++) R+=A;

    return R;
}

但是，我们可以在这里使用一些技巧来极大地加快速度。想象一下将 1 乘以 1000000——在上面的示例中，你会在循环中将一加一百万次。但是如果你交换这两个数字的位置，你只需添加 1000000 到结果一次——速度快得多！

另一个技巧——假设你想将 9876543210 乘以 1234567890。这需要很多次迭代，而且数字长度相同，也不符合像上一个例子那样进行交换。

在这里你做不了太多，只能从最基本的方法开始——迭代——直到乘数末尾变成零。然后你做一件聪明的事情——简单地在第一个数字的末尾附加零，并从另一个数字中删除末尾的零。在上例中，9876543210*1234567890 实际上等同于 98765432100*123456789，我相信你会立即同意。

因此，而不是重复数百万次的循环，你最多只需要进行 [所有数字的总和] 次加法，并将尾随零从一个数字剪切并粘贴到另一个数字的次数相同。是的，这很快！

乘法时，结果的长度总是最多为第一个数字的长度加上第二个数字的长度减一，这与加法的原理类比。

无论一个或两个数字是否为负数，你现在都可以依赖你正在调用的加法和减法处理器。

除法

与乘法相反，除法几乎是相同的过程，除了有一些额外的规则适用。最重要的是，你有一个例外，即你不能除以零。另外，一个方便的规则是，如果一个数字等于另一个，结果总是 1。

public static BigNumber operator /(BigNumber A, BigNumber B)
{
    BigNumber R=0, N=A;

    if(B==0) throw new Exception(…);
    if(A==B) return 1;
    if(B>A) return 0;

    while(N>0) { N-=B; R++; }
 
    return R;
}

同样，与乘法一样，如果 B 比 A 稍短，这可能会非常慢。是时候进行另一个技巧了——获取除数的长度，在前面加上 1，然后用零填充其余位置，并进行指定次数的减法，直到首位数字不大于除数。例如

98235364869 / 32347834

你肯定知道，你至少需要从除数中减去 32347834 次，直到其长度等于但首位数字不超过除数。所以，你确定

98235364869 is dividable by 32347834000

太好了，那就不要迭代 1000 次，而是立即将 1000 添加到 R。你剩下的是

(98235364869 - 32347834000) / 32347834 = 95000581469 / 32347834

然后重复将几千、几百、几十等加到 R。一旦除数大于被除数，你就无法再进行整数除法，R 就成了你的结果。

三级操作

三级操作是求幂和开方。你可能已经猜到，它们从乘法和除法派生而来，就像乘法和除法从加法和减法派生一样。

要得到一个数的幂，x^n, 只需将 x 乘以自身 n 次。要得到 x 的 n 次方根，将 x 除以 n 的结果不断除以 n，直到达到零。

其他操作

其他操作包括逻辑操作（>, <, !=, ==, 这些的组合等——参见附件源代码）以及对数、导数、微分等复杂函数。可以使用上述方法简化无理数的部分。

结论

当我开始做这件事时，我为自己取得的每一个新进展都感到兴奋。实际上，我所有的函数都依赖于已有的函数，这些函数又依赖于其基础的加法和减法以及一些基本逻辑。所有其他操作仅仅是两种最简单、已存在数千年的操作的派生。

数学是一个很好的例子，说明大步前进如此缓慢。以及人类的需求是多么渺小。当今的计算机可以快速解决我们没有它们需要数年才能解决的问题，但计算机仍然无法做一些我们确信知道如何做的事情。话又说回来，只要我们确信自己能做得更好，它们就是非常有趣且非常有用的工具。

要做的事情

• 小数的实现
• 性能改进

致谢

你可以从 www.spindlescape.net 免费下载 BigNumber 库的二进制文件。这里介绍的研究就是为了它的实现。

历史

• 文档版本 1.0：2006 年 11 月 20 日。