找回密码
 欢迎注册
查看: 28870|回复: 25

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

[复制链接]
发表于 2008-6-7 13:08:19 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
显然,对大整数乘以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)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-7 14:05:56 | 显示全部楼层
$1 / 10 =\sum_{n=1}^{infty}1/2^{4n}+1/2^{4n+1}$

所以针对除以10的算法,稍微要复杂些,个人建议是最好用c/c++写主函数,而调用汇编过程
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-7 14:21:44 | 显示全部楼层
固定除数的除法,有可以通过三次乘法替代的快速算法的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-7 14:27:09 | 显示全部楼层


你能找到么?

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

所以如何选择我们需要测试
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-12 09:21:02 | 显示全部楼层
之前说错了,如果仅需得到商,应是需一次乘法、一次移位运算。

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

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

uDiv.zip

25.21 KB, 下载次数: 12, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-12 17:49:20 | 显示全部楼层
长整数阿

老大
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-12 19:36:39 | 显示全部楼层
我知道你说的是大整数算法,但除数是个常规整数,
用普通的算法可以减少数据的读写次数,效率不会慢的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-12 20:42:59 | 显示全部楼层
那你的算法还有效果么
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-6-12 21:15:31 | 显示全部楼层
我没有针对除10作特殊优化。

且我给的算法仅适用于基数是10的整数次幂的情形。
这是刚刚注意到的,难怪你在6#曾强调“长整数”,
因为我看到10,脑子里就默认用10的整数次幂做基数了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-6-12 21:41:19 | 显示全部楼层


我想比如这么个题目

a = 2^1023 - 1
b = 10
c = a / b
仅针对b = 10优化
不考虑a = 2^1023 - 1的特殊性
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-19 17:34 , Processed in 0.049212 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表