我发现的大数表示法，请各位评价下

G-Spider

10# liangbch 如果将 if (sum>=10000) { carry=1; sum-=10000; } 转化成总是执行的等效形式，会不会好一点呢。 比如，以2^B-1 为模，可以使用移位和掩码。

liangbch

　　使用不同的进制，效率会有差异。需要仔细权衡。 　　在当前的32位计算机，$R=2^32$可能是最直接的选择，如用高级语言处理进位处理就麻烦很多，使用汇编语言做长整数加法计算时，可使用带进位的加法指令ADC,但ADC指令比ADD慢很多。这种表示法，虽然节省空间，使得数的长度变短，运算次数减少，但进位和规约须增加额外的成本。我个人不推荐。 　　采用$2^31$为基，对于大数加法来算可使用移位和掩码求得本位和进位。 　　由于大数乘法是大数运算的核心（加减法的复杂度较小,可忽略, 乘法也是除法和开方运算的基础），因此，基于运算速度的考虑，进制的选择主要考虑的大数乘法的效率。采用$2^31$进制，每4次乘积的累加就需要一次规约运算，个人觉得这个进制仍然偏大。我建议，大数的表示宜采用$2^30$进制和$10^9$进制，这样，运算次数和规约/进位处理得到一个好的平衡。 　　另外，即使采用$10^k$进制，也有不用分支的进位处理办法，可使用汇编语言编程消除分支，只是比$2^K$进制更复杂些。

G-Spider

"ADC指令比ADD慢很多" ，我查了一份文档，没有看出慢。http://bbs.chinaunix.net/thread-2133668-1-1.html

liangbch

你可能没有做过类似的编程，没有切实的感受。ADC指令确实比ADD慢多了。你的那个手册是旧的，不适合当前主流的CPU. 关于奔腾以后的cpu，其指令周期等数据请参考instruction_tables.pdf, 692K,更新时间2008-1-14. 文件开头写着。 Lists of instruction latencies, throughputs and microoperation breakdowns for Intel and AMD CPU's By Agner Fog. Copenhagen University College of Engineering. Copyright © 1996 - 2008. Last updated 2008-01-14. 和执行时间有关的参数有2个，Additional latency (额外的延时，越小越好）和 Reciprocal throughput (吞吐量的倒数，越小越好）。 intel P4 CPU ADD r,r 的值 0.5-1,0.25 ADC r,r 的值 0, 6 intel core2 CPU ADD r,r 的值 1, 0.33 ADC r,r 的值 2, 2 这意味者，对于P4， 每个周期可以执行4条Add指令，0.5-1个周期后可以得到结果。 每6个周期可以执行1条AdC指令，指令执行后，可立即得到结果。 由上表可知，对于core2CPU， ADD 指令的吞吐量是ADC的6倍，2/0.33.

gxqcn

instruction_tables.pdf 源于 optimization_manuals.zip，最近更新日期为 2011-01-30 似乎在 AMD CPU 上，ADC/ADD 指令周期差距没有 Intel CPU 的那么大。 另，对于$10^k$进制，怎样用汇编编程消除分支？

G-Spider

instruction_tables.pdf 源于 optimization_manuals.zip，最近更新日期为 2011-01-30 似乎在 AMD CPU 上， ADC/ADD 指令周期差距没有 Intel CPU 的那么大。 另，对于10^k进制，怎样用汇编编程消除分支？ gxqcn 发表于 2011-4-2 15:57

或许有更好的方法。

1. _asm
2. {
3. xor eax,eax
4. mov edx,10000
5. cmp sum,edx
6. cmovnb eax,edx
7. sub sum,eax
8. shr eax,13
9. mov carry,eax
10. }

复制代码

性能有所改善 Elapsed time: 4.668000 s Elapsed time: 6.032000 s

zeroieme

是否意味着让CPU做一点点无用功，反比判断分支还快。

liangbch

16# G-Spider 这个代码的效果应该不错。 我在数年前写过Radix为10^9的大数加法程序，使用了消除分支的代码，用到的adc指令，当时不知道可用cmovcc指令来消除分支，速度应该没有你这个代码快。

liangbch

粗粗的扫了一遍15楼给出的文章,真不错，内容全面翔实。另外，对作者Agner Fog google了一下，发现作者确实是X86优化的资深专家。

关于优化的参考 X86 平台，Agner Fog 是绝对的权威。

▄︻┻═┳一‥

还是没看明白楼主 说的 优势， [-M/2,M/2-1] 里面有负数，你这个负号“-”总要占bit位吧，那岂不是浪费？