基数2^51位表示法通过延迟进位胜过带进位链

超过64位的整数加法应该很简单：把每个256位整数拆成四个64位部分，相加，然后向上传播溢出。问题在于溢出——没有进位，答案就是错的，所以正确的版本会从最低位部分开始链接x86的带进位加法指令（adc）。在现代乱序执行的CPU上，这条链比不正确的并行代码更慢：adc是一个较重的指令，并且每个都依赖于前一个产生的进位标志。Haswell CPU每个周期最多可以发出四个独立的加法，但链式的adc会串行执行。

这个反直觉的修复方法在密码学文献中被称为基数2^51表示法，就是使用更多部分，每个都小于寄存器。普通方法把256位拆成四个基数2^64的数字，而这种方法将其拆成五个基数2^51的数字；每个64位部分仍容纳其数字，但高12-13位保持为空，作为进位累积的空间。由于有这种余量，在备用位填满之前，添加规范化值根本不会产生进位——大约2^13次加法——因此每个加法都是独立的，处理器会并行调度它们。

进位并没有消除，只是被推迟了。当余量耗尽时，一次规范化传递将每个部分的溢出移到更高部分并清除余量，减法也可以通过将有符号处理各个部分来工作，代价是少一位余量。作者在Haswell机器上进行的快速基准测试发现，即使只有三次加法，基数2^51加法的速度也已经快于基数2^64加法，包括进入和退出该表示的转换成本，随着加法的累积，节省会更多。

这篇文章先在纸上建立了直觉：以10为基，拓宽每个数字的范围以便能计数超过9，可以使几个规范化数字在任何一个数字溢出前被加在一起，一次规范化传递将结果转换回来。移入二进制寄存器，同样的原理就是为什么这种表示在密码学中是标准的——以及为什么反直觉地，将数字分散到更多寄存器并发出更多指令会让算术更快。本文首次发布于2017年，2020年5月被发布到Hacker News，获得了518分和83条评论。

缩短部分到51位，让多余位吸收进位：加法保持独立并行，并在最后一次性规范化

进位是依赖：链式adc指令串行化，因为每个都等待前一个进位标志，而在Haswell上独立的普通加法可以每个周期发出四个。

空余量是关键：64位寄存器中的51位数字留出12-13位空闲，因此大约2^13次加法才需要传播一次进位。

一次推迟的传递胜过许多立即处理：末尾的规范化是固定扫描，而不是每个操作上的进位依赖。

额外的部分物有所值：即使算上转换成本，从仅仅三次加法开始，五个普通加法胜过四个adc链。

要打破串行依赖，就加一些以后偿还的余量：预留余量，让热门操作自由运行，然后用一次传递解决推迟的工作。

发表于2017年，2020年5月发布到Hacker News，获得518分和83条评论。实践者将这个技巧与真实代码挂钩：评论者指出Curve25519的域运算是以2^255-19为模工作的，因此值适合51位部分，在32位CPU上采用基数2^25.5的变体；其他人讨论了Broadwell的ADCX/ADOX指令和部分寄存器停顿，还有人指出了文章中关于高部分解释的错误。该技术仍然是这篇文章所称的那样：密码学中标准的基数2^51表示，用于域算术必须快速且恒定时间的场合。