原帖由 gxqcn 于 2008-6-12 21:15 发表 http://bbs.emath.ac.cn/images/common/back.gif
我没有针对除10作特殊优化。
且我给的算法仅适用于基数是10的整数次幂的情形。
这是刚刚注意到的，难怪你在6#曾强调“长整数”，
因为我看到10，脑子里就默认用10的整数次幂做基数了。:o
上面的回复不太正确，当时脑子有点乱，也没有源代码可供参考。
昨天晚上在台式机上安装 Visual Studio 2008，我是在老婆的笔记本上登录论坛的。
我说一下我的做法，该算法通用于以任意数为基数的大数运算。
对于除数d为int型的大数除法，下面仅针对无符号型：
1、若d==0，则 HugeCalc::SetLastError( HCERR_DIV_ZERO )，return；
2、如果恰好等于大数内部基数，右移“一位”即可；
3、按小学生的除法算法，从高位向低位挺进：(上次的余数*基数+当前值)/d=商…本次的余数
但，当d为2的整数次幂时，上述除法指令可被移位指令替代优化。
对于“大整数*常规小整数”，类似，只是改为从低位向高位挺进模式进行而已。
你要做这个优化的目的是什么呢?
如果仅仅要做进制转化,是不需要这个优化的
进制转化确实不应这么做，因为这样做的算法复杂度太高了。
可能楼主因为经常需要碰到10进制下的“移位”处理吧。
如果这样，可能直接进行十进制计算更加好些:)
在 常规小整数<大整数基数 前提下，不同基数下的乘除法效率基本是一致的。
差异仅在于其中蕴涵的“*基数”过程是否可用移位优化，
以及因基数大小的不同，相同大整数被分割的次数。
用 n^b 为基数的大整数，在乘以（或除以）n^k 时，
当 k>>b 时，可先通过以基数的“移位”，而后再乘以（或除以）n^(k mod b) 即可。
前者是真正意义上的“移位”，是个O(1)的操作。
所以，如果算法中存在大量乘以（或除以）“10的整数次幂”运算时，
考虑以 10^b 为基数是有必要的。
最显著的例子，如大整数的输出效率。
乘以10的移位肯定是快于直接乘吧？
能有兴趣测试么？
不过，C代码在这个问题上应该不合适
这很难说，1次mul 与 2次shift+1次add 谁快？可能不同系统上有不同答案。
还有，大数基数*10 ≥ 2^32 ？这个在算法设计优化时也很重要。
下面仅是一些想法
如果32位系统，这个问题的话，用SSE2存在一次移位64位的算法
考虑循环展开的话，一次移位操作可以达到256位
加肯定存在一次加128位的4路循环展开算法的，这个我和liangbch已达到共识
乘也存在一次乘128位的的4路循环展开算法的，这个我也和liangbch已达到共识
但乘的逻辑复杂的多
考虑指令时间
乘是9个周期
加和移位是1－2个
如果安排合理，
按双字算，一个运算单位消耗的时钟
乘能达到12个（可能不准确）
加是5个
移位是0.5个
所以推测，至少是不输于直接乘
但运算时间最快只能达到直接乘的1/2左右
17# gxqcn
嗯，除了像P4之类的要考虑下，乘法其实很快了， 30# G-Spider
这里关于乘法逆元用在这个帖子里不合适，事实上其局限性很大。"Quotient will only be correct if d divides a exactly."
n_limb/1_limb，不知道郭用的什么方法，gmp中mpn_divrem_1 -- mpn by limb division.用到的方法，我没有看特别明白，可能是先求导数(选取有些讲究)，再乘法代替除法。
而这种方法用到的变量有些多，于是在x86 ALU asm中没有看到相关的实现，xmm和x64倒是有，如mpn\x86\p6\mmx\Divrem_1.asm。
mpn_invert_limb
按照它的说法
At 4 limbs the div is a touch faster than the mul (and of coursesimpler), so start the mul from 5 limbs. (mul_by_inverse)
在vc6.0中也有关于一个常量的除法的优化方法：
如(unsigned int) n/3，优化为 mov eax, -1431655765 ; aaaaaaabH
mul n
shr edx, 1aaaaaaabH 对应于2/3 (规范化，有助于得到高精度的表示)，于是上在的代码解释为(n*(2/3))/2.
又比如n/10 mov eax, -858993459 ; cccccccdH
mul n
shr edx, 31/10=(4/5)/8 如上，cccccccdH 为4/5，然后除以8(用右移3)。
19# G-Spider
上面vc做的优化是dividing a single-word number by a single-word number ,using a single-word approximate reciprocal.
这在大数除以1个limb的情况下不合适，大数中需要实现dividing a two-word number by a single-word number,using a single-word approximate reciprocal.的优化方案。
gmp有篇相关的文章Improved division by invariant integers