10# liangbch
如果将
if (sum>=10000)
{
carry=1;
sum-=10000;
}
转化成总是执行的等效形式，会不会好一点呢。
比如，以2^B-1 为模，可以使用移位和掩码。
使用不同的进制，效率会有差异。需要仔细权衡。
在当前的32位计算机，$R=2^32$可能是最直接的选择，如用高级语言处理进位处理就麻烦很多，使用汇编语言做长整数加法计算时，可使用带进位的加法指令ADC,但ADC指令比ADD慢很多。这种表示法，虽然节省空间，使得数的长度变短，运算次数减少，但进位和规约须增加额外的成本。我个人不推荐。
采用$2^31$为基，对于大数加法来算可使用移位和掩码求得本位和进位。
由于大数乘法是大数运算的核心（加减法的复杂度较小,可忽略, 乘法也是除法和开方运算的基础），因此，基于运算速度的考虑，进制的选择主要考虑的大数乘法的效率。采用$2^31$进制，每4次乘积的累加就需要一次规约运算，个人觉得这个进制仍然偏大。我建议，大数的表示宜采用$2^30$进制和$10^9$进制，这样，运算次数和规约/进位处理得到一个好的平衡。
另外，即使采用$10^k$进制，也有不用分支的进位处理办法，可使用汇编语言编程消除分支，只是比$2^K$进制更复杂些。
"ADC指令比ADD慢很多"，我查了一份文档，没有看出慢。http://bbs.chinaunix.net/thread-2133668-1-1.html
你可能没有做过类似的编程，没有切实的感受。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
ADDr,r 的值 0.5-1,0.25
ADCr,r 的值 0, 6
intel core2 CPU
ADDr,r 的值 1, 0.33
ADCr,r 的值 2, 2
这意味者，对于P4，
每个周期可以执行4条Add指令，0.5-1个周期后可以得到结果。
每6个周期可以执行1条AdC指令，指令执行后，可立即得到结果。
由上表可知，对于core2CPU， ADD 指令的吞吐量是ADC的6倍，2/0.33.
instruction_tables.pdf 源于 optimization_manuals.zip，最近更新日期为 2011-01-30
似乎在 AMD CPU 上，ADC/ADD 指令周期差距没有 Intel CPU 的那么大。
另，对于10^k进制，怎样用汇编编程消除分支？
instruction_tables.pdf 源于 optimization_manuals.zip，最近更新日期为 2011-01-30
似乎在 AMD CPU 上， ADC/ADD 指令周期差距没有 Intel CPU 的那么大。
另，对于10^k进制，怎样用汇编编程消除分支？
gxqcn 发表于 2011-4-2 15:57 http://bbs.emath.ac.cn/images/common/back.gif
或许有更好的方法。_asm
{
xoreax,eax
movedx,10000
cmpsum,edx
cmovnb eax,edx
subsum,eax
shreax,13
movcarry,eax
}性能有所改善
Elapsed time: 4.668000 s
Elapsed time: 6.032000 s
是否意味着让CPU做一点点无用功，反比判断分支还快。
16# G-Spider
这个代码的效果应该不错。
我在数年前写过Radix为10^9的大数加法程序，使用了消除分支的代码，用到的adc指令，当时不知道可用cmovcc指令来消除分支，速度应该没有你这个代码快。
粗粗的扫了一遍15楼给出的文章,真不错，内容全面翔实。另外，对作者Agner Fog google了一下，发现作者确实是X86优化的资深专家。关于优化的参考 X86 平台，Agner Fog 是绝对的权威。
还是没看明白楼主 说的 优势， [-M/2,M/2-1] 里面有负数，你这个负号“-”总要占bit位吧，那岂不是浪费？