整数数学：超越极限
4.79/5 (20投票s)
一种处理大整数的粗略方法。
引言
我们多久会遇到超出 MAXUINT32 甚至 MAXUINT64 的数字？确实，2^32 - 1 = 4294967295 和 2^64 - 1 = 18446744073709551615 是极其庞大的数字。但是，如果您需要精确处理像 2^3232 或更大的数字怎么办？这永远不可能发生，但万一您遇到这种情况，它可能会让您感到惊讶。在我解决一个特殊的难题时，我曾惊讶于计算这些额外巨大数值的问题。所以我想我的经验可能会对某人有所帮助。
背景
让我们来看看写在纸上的任意整数：例如 123456。我们人类使用一组符号 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 进行书写，并且不会过多考虑在纸或桌子上写一个数字需要多少这样的符号。实际上，我们只受限于可用的空白空间来写下一个数字。即使行满了，我们也会大胆地在下一行继续写。当我们进行加/减/乘/除时，我们使用我们聪明的电子助手。如今，由于系统架构对设备能够处理的数字长度有限制，我们通常会查看所谓的科学计数法。科学计数法让我们能够评估运算结果，例如数字的指数。但是，如果巨大的和超巨大的数字的算术运算结果必须是精确的，并且精度不能有任何折衷，该怎么办？在这种情况下，我们需要编写一些代码来解决这个问题。
模型
首先，让我们回顾一下古代的知识。CPU（以下简称 x86）在其工作中采用二进制代码。数字 123456（十进制）在二进制系统中看起来是 1 1110 0010 0100 0000。当这个数字存储在地址 N 的进程内存中时，它将如下所示：
N: [0100 0000] N + 1: [1110 0010] N+2: [0000 0001]我们有 3 个字节。如您所知，字节是最小的内存存储单位（是的，它包含 8 位，但您无法通过单一指令原子地将第 5 位与第 7 位相加）。因此，存储在内存中的任意数字会分解成字节，而较高有效字节存储在较高的内存地址。CPU 可以操作内存中的数字，但这些操作的原子性是有限的。32 位处理器可以通过一条指令处理 32 位操作数（某些情况下是 64/128 位）。作为有限状态机，CPU 会根据执行操作的结果相应地改变其状态。
现在是时候回顾一下二进制算术知识了。
让我们尝试将两个数字相加，17 (10001) 和 18 (10010)。我使用较小的数字是为了简洁明了。
10001 (17)
+ 10010 (18)
-------
100011 (35)
正如您所见，在相加第 4 位时发生了溢出，出现了第 5 位。结果的宽度增加了。如果我们限制为 5 位，结果将是 00011 且发生溢出。在减法中，有时我们需要从较高有效位“借用”1，这被称为下溢。因此，在内存中分割数字时，我们不能在不考虑溢出（下溢）状态作为另一个操作数的情况下进行加（减）下一个部分。处理器为我们提供了这种机会——“adc”和“sbb”指令来自“经典”指令集会派上用场（代码片段仅用于演示目的）。
mov ecx, [Size]
xor esi, esi
clc
lahf
_AddLoop:
mov ebx, [Addend]
mov dl, [ebx][esi]
mov ebx, [AddResult]
sahf
adc [ebx][esi], dl
lahf
inc esi
loop __AddLoop
减法操作的实现方式类似。
现在让我们谈谈乘法，尝试将 17 (10001) 和 18 (10010) 相乘。
10010 (18)
* 10001 (17)
--------
10010
00000
00000
00000
010010
-----------------
0100110010 (306)
正如您所见，我只是将乘法分解为一系列移位和加法。每次检查第二个操作数的下一个位时，我们都会将第一个操作数向左移位。如果第二个操作数的位非零，则执行加法。
这非常直接。结果的宽度是操作数宽度的总和。乘法操作的实现可以在 源代码 中找到。
最后是除法。像往常一样，用手、笔和纸来做。
100110001 (305) 1110 (14) 01110 10101 (21) - Quotient ------- 0010100 0001110 --------- 000011001 000001110 ----------- 000001011 - Remainder (11)
确实，21 * 14 + 11 = 305。
因此，正如您所见，除法运算可以分解为一系列移位、比较和减法，这个算法并不复杂。被除数和商向左移位，直到其最高有效部分大于除数（我称之为“对齐头部”）。当除数小于那个移位的块时，执行减法，并在商中设置 1。余数是所有移位和减法后剩下的位。被除数被复制并处理到一个单独的双字节缓冲区中。
机械结构
所有这些函数都在 源代码 中使用通用的汇编指令实现，并且有待改进。我的方法很直接，并且存在一些限制：
- 所有数字都是无符号的。这有助于避免处理负数的一些困难。
- 所有数字的大小都相等。
- 所有数字都是 DWORD 数组。
提高性能的方法。
首先也是最简单的——将函数声明为 naked 和 __fastcall。这减少了序言/尾声代码执行以及通过堆栈传递参数的开销。然后——使用处理最大大小操作数的指令。（我使用了来自古老“经典”命令集的指令）。但在执行此操作之前，请确保处理器支持这些指令。CPUID 是实现此目的的好方法。其次也是更复杂的——审查算法的控制流。在加法和减法例程的情况下，似乎没有什么可以通过这种方式来增强，但乘法和除法是进行此类分析和改进的主体。对于乘法算法，我们首先可以减少第一操作数的移位次数。我们可以计算到第二个操作数中下一个非零位的“距离”，并将第一个操作数移动该位数。例如，下面的代码片段连续检查第二个操作数的位是否为 1，并计算这种“距离”。
mov ebx, [lpUIntR]
xor eax, eax // Bit #no for test
mov esi, eax // lpUIntR DWORD part #no
mov edi, eax // Bits count for shift buffer
__L_BitTest:
bt [ebx][esi * 4], eax
jc __L_BitIsNonZero
inc edi
__L_BitTestLoop:
inc eax
cmp eax, 32
jne __L_BitTest
xor eax, eax
inc esi
cmp esi, [cnSize]
jne __L_BitTest
jmp __L_MulIsDone
但是，在第二个操作数“密集”的情况下，这种操作可能会影响性能。
除法算法更是如此，更易于改进。正如您所记得的，在迭代开始之前，被除数和除数必须彼此“对齐”。这个启动“对齐”操作可以通过一个“传递”（在迭代之前）来完成。在除法指数接近的数字时，这可以提高性能，但在除源中的数字时则不能。另一个增强功能是在迭代循环内计算缓冲区的左移距离以使其与除数对齐。但是这种改进的优点很微妙：缓冲区会随着每次迭代而改变。
无论如何，如果您感兴趣，您会在实验中找到合适的解决方案。因此，在 源代码 中，您会找到粗略的算法实现。
现在，让我尝试让您惊叹。看看源代码中测试的结果。
被除数：3121748550315992231381597229793166305748598142664971150859156959625371738819765620120306103063491971159826931121406622895447975679288285306290175
除数：100000
结果：31217485503159922313815972297931663057485981426649711508591569596253717388197656201203061030634919711598269311214066228954479756792882853062
余数：90175
对我来说，处理整数的指数是令人印象深刻的。
结论
使用汇编语言没有什么不可能的。它赋予我们系统的一切力量，但我们必须极其小心地使用它。就像整数运算一样，您可以忘记整数计算中的精度损失。但请记住：我们总是要为一切付出代价。在这种情况下，您将以应用程序的性能作为代价。
附注：抱歉我的英语不好。