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)

erileiyuqig

$1 / 10 =\sum_{n=1}^{infty}1/2^{4n}+1/2^{4n+1}$

所以针对除以10的算法，稍微要复杂些，个人建议是最好用c/c++写主函数，而调用汇编过程

aduxoeroba

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

ahqhegudiz

你能找到么？

另外三次乘法也不一定能快过移位
移位速度大概仅次于内存拷贝速度
至少是乘法速度的3-4倍甚至还多

所以如何选择我们需要测试

aecupeemow

之前说错了，如果仅需得到商，应是需一次乘法、一次移位运算。

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;
        }
}

附件是无符号固定除数的快速算法，输入除数，自动输出汇编指令（含源代码）。

ejiwueu

长整数阿

老大

icakeekohude

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

Lpasarbola

那你的算法还有效果么

ipeuric

我没有针对除10作特殊优化。

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

owobapiakuw

我想比如这么个题目

a = 2^1023 - 1
b = 10
c = a / b
仅针对b = 10优化
不考虑a = 2^1023 - 1的特殊性