B计划之大数乘以10，除以10的快速算法的讨论和实现

无心人

显然，对大整数乘以10或者除以10的高速实现，是以移位为基础实现的 希望有兴趣的能写出测试代码，以得到最优化的实现，老规矩32Bit x86平台，C/C++或者汇编，汇编指令到SSE2 乘以10的好处理，假设大数为n，长度为k 方案1 10n = (n << 2 + n) << 1 运算次数 3k，额外存储 1k 方案2 10n = n << 3 + n << 1 运算次数 3k，额外存储 2k 所以个人倾向于使用方案1 运算时间为O(k) 除以10是以一系列的右移位为基础的，算法稍后送上 运算时间是O(klogk)

无心人

$1 / 10 =\sum_{n=1}^{infty}1/2^{4n}+1/2^{4n+1}$ 所以针对除以10的算法，稍微要复杂些，个人建议是最好用c/c++写主函数，而调用汇编过程

gxqcn

固定除数的除法，有可以通过三次乘法替代的快速算法的。

无心人

你能找到么？ 另外三次乘法也不一定能快过移位 移位速度大概仅次于内存拷贝速度 至少是乘法速度的3-4倍甚至还多 所以如何选择我们需要测试

gxqcn

之前说错了，如果仅需得到商，应是需一次乘法、一次移位运算。 Unsigned division by constant ============================= enter divisor: 10 ; dividend: register other than EAX or memory location MOV EAX, 0xCCCCCCCD MUL dividend SHR EDX, 3 ; quotient now in EDX 而楼主的要求，显然需要同时获得余数，则需再增加一次乘法、一次减法运算， 下面是我写的代码，请检验： // 返回余数；u32Num 作为输入的被除数，同时作为输出的商 __declspec(naked) CONST UINT32 DivMod10( UINT32& u32Num ) { __asm { mov ecx, dword ptr[esp + 0x04]; mov edx, dword ptr[ecx]; mov eax, 0xCCCCCCCD; // [ 2^35 / 10 + 0.5 ] push edx; mul edx; shr edx, 3; mov dword ptr[ecx], edx; imul edx, 10; pop eax; sub eax, edx; ret; } } 附件是无符号固定除数的快速算法，输入除数，自动输出汇编指令（含源代码）。

无心人

长整数阿 老大

gxqcn

我知道你说的是大整数算法，但除数是个常规整数， 用普通的算法可以减少数据的读写次数，效率不会慢的。

无心人

那你的算法还有效果么

gxqcn

我没有针对除10作特殊优化。 且我给的算法仅适用于基数是10的整数次幂的情形。 这是刚刚注意到的，难怪你在6#曾强调“长整数”， 因为我看到10，脑子里就默认用10的整数次幂做基数了。

无心人

我想比如这么个题目 a = 2^1023 - 1 b = 10 c = a / b 仅针对b = 10优化 不考虑a = 2^1023 - 1的特殊性