从“1”位置开始，我们加6+6=12，写下2，进位1。我们向左前进，一次一个位置，直到没有更多的数字要加。
在实现大整数(例如，2 64及以上)的加法时，通常会编写与此算法非常相似的代码。有趣的是，有一个简单的技巧可以在现代CPU上极大地加速这一过程。
但首先，我要问一个问题：为什么我们要从“1”开始长相加？为什么不从左边开始呢？
答案当然是进位，我们不能确定答案的给定数字是多少，直到我们完成了该数字右边的所有加法。
6+3=9，所以第一个数字是9.8+4=12，好的，第二个数字是2…。但是携带1，所以第一个数字实际上是9+1=10…。现在带回1个…。
对于心算来说，这并不是太糟糕(有些人在处理足够小的数字时实际上更喜欢它)。然而，作为一种算法，这种方法有一些基本的限制，在处理较大的数字时会变得明显。最重要的是，因为计算的后期部分依赖于计算早期部分的信息，所以很难对工作进行拆分和并行化。
当然，计算机不能在基数10下运行，取而代之的是，现代的台式机和服务器CPU提供了一个接口来操作(大部分)64位整数。
；将B中的64位值加到A中的64位值中添加A，B；注意：为简单起见，我将使用字母而不是真实的寄存器名称
只要我们的数字符合单个64位的值，事情就很简单，但是如果我们想要添加(比方说)两个256位的整数x和y怎么办？
显而易见的解决方案是将每个256位的数字分成四个64位的部分(通常称为“肢体”)。将x的最高64位放入寄存器A，将接下来的64位放入寄存器B，依此类推，将寄存器C和D放入。对于寄存器E、F、G、H，y也是如此。
但是等等，这可能会给我们错误的结果！如果最后三个加法中的一个溢出，那么我们需要将额外的1“进位”到下一个64位块。哦，嘿，这听起来熟悉吗？
幸运的是，x86有一个专门的指令，称为“带进位加法”。ADC将自动检查前一操作是否溢出，如果需要则加1。以下是正确代码的外观：
将D，H ADC C，G相加；包括来自前一运算ADC B，F进位；包括来自前一运算ADC A，E的进位；包括来自前一运算的进位。
就像基数10中的长加法一样，我们从最不重要的“数字”(D和H)开始，一直到最重要的“数字”(A和E)，一路上根据需要携带1。
有趣的是，我们固定的代码比原始的(不正确的)代码慢得多。这是为什么？
第一个原因是，在最流行的x86CPU上，ADC的执行速度只是比普通加法慢。因为ADC有第三个输入(进位标志)，所以它是一条比ADD更复杂的指令。而且ADC的使用频率也低于ADD，所以CPU设计者在优化ADC性能上花费芯片面积的动机较小。
第二个原因更有趣，让我们以Intel Haswell微体系结构为例。
在Haswell CPU上，一条加法指令需要1个周期来执行，但在理想情况下，Haswell CPU在一个周期内最多可以执行4条加法指令，这是怎么可能的呢？并行性。现代处理器预测即将出现的指令，并尝试调度它们，以便它们可以在任何可能的时候并行执行。由于哈斯韦尔CPU有8个执行端口，其中4个端口可以执行整数加法指令，因此一个哈斯韦尔处理器可以同时执行最多4个加法指令。
在我们最初的加法代码中，所有4条加法指令都是相互独立的，所以处理器很容易并行运行它们。现在，有了ADC，每条指令都依赖于前一条指令的输出，处理器别无选择，只能串行地逐条执行指令，而不是并行执行。
如果我们使用SIMD(SingleInstruction，Multiple Data，单指令多数据)指令，则性能差异会更加显著。例如，一条vpaddq(向量打包加法四字)指令可以同时执行四个64位加法运算。再加上Haswell处理器可以执行两个vpaddqsper周期，您可以看到，为了正确处理进位，我们采取了很大的性能改进措施。
让我们对数字系统的工作方式进行一些更改。首先，我们将扩大可用的数字范围。我们将使用0-9而不是0-9、A-Z和*：
(是的，我需要一个额外的字符才能很好地计算出数字。听我说。)。
虽然我们有37位数字，但我们没有使用基数37。数字仍然会有“1”、“10”和“数百”位，就像正常的基数10系统一样。29仍然是29，29+1仍然是30。唯一不同的是，碰巧9：29+1以上的数字也可以写成2A、1K甚至U。
此技巧不适用于我们的数字系统中的所有数字(例如，9+W将需要进位)，但如果我们要添加的数字是规范化的，即它们的所有数字都是9或更低，它将有效。实际上，在任何进位之前，我们可以在此记数法中添加最多四个规范化的数字：
999<；--可能的最大归一化3位数数字999 999+999-*<；--有效的3位数结果，无进位(请记住*是最高数字)。
因此，通过对数字系统进行一些巧妙的调整，我们欺骗了一些进位。当然，在某些情况下，我们需要从37位的基数10系统转换回正常的基数10。我们可以通过规范化一个数字来实现这一点，使其每个数字都在0到9之间：
«DA8A1B=1409021注：D=10+3A=10+0B=10+1。
我们从右边开始标准化一个数字，确定每个数字有多少个“十”，减去这些“十”，然后将它们进位到下一个数字。672415和736606实际上加起来等于1409021，所以系统可以工作！
这里的关键观点是，我们可以使用这种技术将进位传播延迟到结束，我们不能完全避免进位传播，但我们可以暂时避免它，如果我们保存中间相加过程中出现的进位，我们可以一次过将它们全部传播出去。
进位传播是我们早先遇到的性能问题的核心。正如您现在可能已经预料到的那样，我们可以使用此技术来帮助加速大数运算！
以前，由于x86_64处理器对64位整数进行操作，所以我们将一个256位的数字分成四个64位的部分。理解这一点的一种方法是将这些部分视为基数2 64中的“数字”，因为每个数字都有一个介于0和2 64-1(包括0和2 64-1)之间的值。
在基数10中，我们保持基数不变，但为了防止进位，我们扩展了允许的位数范围。不幸的是，我们在这里不能这样做-64位整数只有这么多可能的值，并且我们不能更改硬件。相反，我们可以通过减小基数的大小来达到同样的效果。
我们不把256位分成4个基数2 64位，而是把256位分成5个基数2 51位。每个数字的范围仍然是从0到2 64-1，但较小的基数给了我们避免数字需要进位所需的灵活性。这种技术在密码学文献中通常被称为“基数2 51表示法”。
下面是我们将256位分成五个肢体(即数字)时的情况：
。-]||[-51位-||[-|。
每个分支都有原始256位数字的51位(或52位)，剩下的12位或13位为我们提供了预防进位所需的额外“数字”，有效地，每个分支的最高位被保留作为计算期间发生的任何进位的存储。
在我们的以10为基数的示例中，37位允许我们在需要传播进位之前将最多4个规格化数字相加；在基数2 51表示中，2 64位允许我们在需要担心高13位溢出之前将最多2 13个规格化数字相加。
旁白：为什么是13位而不是12位？出于我们的目的，我们将忽略最有效分支中的进位，允许数字在溢出超过2256-1时换行(就像在C中使用正常大小整数类型的无符号加法一样)。因此，我们可以将52位分配给最有效分支，而忽略这样一个事实，即它将在其他分支之前用完进位空间。
假设x在A，B，C，D，E上分裂(A=最高有效)；假设y在F，G，H，I，J(F=最高有效)上分裂，加A，F加B，G加C，H加D，I加E，J；平行好，耶！
尽管我们现在需要5个加法而不是4个加法，但由于缺少进位，加法速度要快得多。
。将D中的进位清零T，C；将C复制到T shr T，51；移出除进位Add B，T之外的所有内容；将C中的进位添加到B和C，0x0007FFFFFFFFFFFFF；将C mov T，B中的进位清零；将B复制到T shr T，51；移出除进位Add A，T之外的所有内容；将B中的进位添加到A和B，0x0007FFFFFFFFFFFFF；将进位输入清零。
令人惊讶的是，一些快速而肮脏的基准测试表明，在我的Haswell CPU上，基数2-51加法的性能已经超过基数2-64加法，只需要3次加法--这还包括在基数2-51表示之间进行转换的成本。随着加法数量的增加，性能节约会相应地增加。
到目前为止，我们只研究了加法，将这一技术扩展到减法是很简单的，加法和减法的主要区别是减法有负进位。
以前，我们将所有的肢体(及其进位)视为无符号进位，为了支持减法，我们可以将肢体视为有符号整数，允许单个数字为正或负，这样每条肢体就可以存储一个正进位或负进位。
这样做的一个副作用是，每条肢体的最高有效位现在被保留为符号位，这使得我们可以在归一化之间执行的操作次数从213减少到212，这在大多数情况下是一个小牺牲。
我觉得这项技术相当吸引人，因为它非常违反直觉：通过跨更多的寄存器和使用更多的操作分布数据，性能实际上得到了提高。我希望您和我一样觉得它很有趣！