基数 2^51 技巧

主要观点:

  • 在现代 CPU 上,长加法在纸上的算法可用于大整数加法,且有技巧可加快该过程。
  • 计算机以 64 位整数为接口,处理 256 位整数时需分段相加,需处理进位。
  • 常规的带进位加法(adc)指令比普通加法(add)慢,且会影响并行性,导致性能下降,在使用 SIMD 指令时更明显。
  • 通过改变数字系统,可消除加法中的进位,如使用 37 进制,先进行无进位加法,最后再转换回 10 进制。
  • 在计算机中,可通过将 256 位分成 5 个基数为 251 的“数位”来消除进位,提高加法速度,同时需有处理进位的代码。
  • 该技术可扩展到减法,将数位视为有符号整数,最高位为符号位,会降低两次归一化之间可执行的操作数。

关键信息:

  • 现代 CPU 加法算法及性能问题,如addadc的差异及并行性影响。
  • 改变数字系统以消除加法进位的方法及原理。
  • 在计算机中利用基数变化消除进位的具体操作及相关代码。
  • 减法的处理方式及与加法的差异。

重要细节:

  • 在纸上长加法从右到左逐位相加,计算机以 64 位整数为单位,处理 256 位整数时需分段。
  • adc指令因有第三输入(进位标志)更复杂且使用较少,导致执行慢,影响并行性。
  • 在改变的数字系统中,可添加最多四个归一化数字而无进位,通过归一化可将 37 进制结果转换回 10 进制。
  • 在计算机中,将 256 位分成 5 个基数为 251 的“数位”,可避免进位,提高加法速度,同时有处理进位的代码。
  • 减法处理时将数位视为有符号整数,最高位为符号位,会降低两次归一化之间的操作数。
阅读 13
0 条评论