高速大数乘法 pk HugeCalc

nlrte13

由于工作需要，写了个大数乘法算法（作为RSA的一部分） 跟 HugeCalc V8.0.0.0对比了下，发现我的程序速度要快上许多。 下面是统计数据： 1、只累计乘法算法时间 我的HugeLib： for( int times = 0; times < 1000000; ++times ) { HugeMul(); } HugeCalc： for( int times = 0; times < 1000000; ++times ) { c = ( a * b ); } 结果： 128位*128位（按8位 = 1字节，即16字节） 耗时（单位为秒）： HugeLib：0.0863 HugeCalc：1.841 256位*256位 HugeLib：0.219 HugeCalc：2.310 512位*256位 HugeLib：0.385 HugeCalc：2.714 512位*512位 HugeLib：0.698 HugeCalc：4.151 2、累计输入数据初始化、乘法计算和结果转字符串 HugeLib： for( int times = 0; times < 1000; ++times ) { DWORD dwRet= Init( "0xA48B637BDD34BFAB24567F79751903A49AE4C92E1113745C78DAB49413DC71A6C89A0A21F3C794D4DC46ED0C6CB8DBECE4ACEA39E7A591F96E8D071A8423065A", "0x748B637BDD34BFAB24567F79751903A49AE4C92E1113745C78DAB49413DC71A6C89A0A21F3C794D4DC46ED0C6CB8DBECE4ACEA39E7A591F96E8D071A84230655" ); HugeMul(); const char* p = GetRetStr(); } HugeCalc： for( int times = 0; times < 1000; ++times ) { CHugeIntX a( "0xA48B637BDD34BFAB24567F79751903A49AE4C92E1113745C78DAB49413DC71A6C89A0A21F3C794D4DC46ED0C6CB8DBECE4ACEA39E7A591F96E8D071A8423065A" ); CHugeIntX b( "0x748B637BDD34BFAB24567F79751903A49AE4C92E1113745C78DAB49413DC71A6C89A0A21F3C794D4DC46ED0C6CB8DBECE4ACEA39E7A591F96E8D071A84230655" ); CHugeIntX c = ( a * b ); c.GetStr(); } 结果： 512位*512位耗时： HugeLib：0.002968 HugeCalc：0.167497 两者都是通过调用动态库方式进行比较的。 附件里含测试工程，包括调用HugeCalc的头文件.h，Lib和Dll，以及我的HugeLib的头文件.h，Lib和Dll文件。 由于HugeCalc v8试用版的缘故，还需要放在 "CopyrightByGuoXianqiang" 目录下进行…… #include "hugeLib.h" #pragma comment( lib, "hugeLib.lib" ) #include "Include/HugeCalc.h" // 公共接口 #include "Include/HugeInt.h" // 10进制系统 #include "Include/HugeIntX.h" // 16进制系统 #pragma comment( lib, "HugeCalc.lib" )

nlrte13

理论上乘法速度还可以再优化10%左右^^ 有空我再搞一下，嘿嘿 对了，忘记说了，上面测试使用的cpu是我可怜的 AMD Sempron 1.75GHz, 内存1G（这不是瓶颈）

mathe

可惜,你的测试程序写得不对.简单重复乘法操作会被编译器优化的

gxqcn

下载了你的附件，发现你的测试代码不公平。 1、对 HugeCalc 的测试，你是在循环体内进行构造、析构的，这本身需要耗用一定的时间； 2、在 HugeCalc 中，“c = ( a * b )”可用“c.Mul(a,b)”替换，应更高效。 你可以看看增大输入后，两者耗时的上升趋势如何？曲线曲率越小的越优。 关于 HugeCalc，它设计定位在超大数的快速运算， 在数据结构以及算法上尽量优先满足超大数的计算， 所以对小规模的计算并未做太多的优化， 但这个情形不会长久下去， 在下次内核大改动时会一并考虑的。

mathe

呵呵,没有注意还附带测试程序: LZ的函数 HugeMul(); 的调用方法很奇怪. 我修改了一下代码:

2. DWORD dwRet = Init( "0x9A34567890123456789012345678901234567890123456789012345678901234", "0x9A34567890123456789012345678901234567890123456789012345678901234" );
3. for( int times = 0; times < 100000; ++times )
4. {
5. HugeMul();
6. }

复制代码

2. CHugeIntX a( "0x9A34567890123456789012345678901234567890123456789012345678901234" );
3. CHugeIntX b( "0x9A34567890123456789012345678901234567890123456789012345678901234" );
4. CHugeIntX c;
6. for( int times = 0; times < 100000; ++times )
7. {
8. c.Mul(a,b);
9. }

复制代码

然后为了防止编译器优化引起的影响,选择Debug方式编译. 运行结果HugeLib 0.0414秒,HugeCalc0.0271秒

mathe

其实我觉得要做比较,最好直接拿像PowMod之类比较复杂的运算比较好一些. 这样,其它意外因素影响会小一些

nlrte13

如5楼所言，我改成那个样子，并用Debug方式编译，在我Intel Pentium Dual E2180 2.00GHz系统上， 使用我的算法，耗时0.0581秒，使用HugeCalc，耗时0.139秒。和你的测试结果完全不同。奇哉，怪也。 我测了一下我算法执行的计算机指令周期数，512位*512位，我的算法经历了 3139 个指令周期

nlrte13

4楼的同志，不太了解你的算法库，刚刚接触而已。工作需要，本来想直接用你的，可是发现有限制，所以只好自己写了，郁闷。

nlrte13

4楼，有点不明白，为啥你那大数转换为字符串输出，要花那么多时间。希望你尽快完善哈^^ 总体来说你的软件还是很不错的

gxqcn

HugeCalc 的输入输出的效率并不低，是经过特别优化过的。 如果仅仅为RSA服务，完全可以开一个足够大的固定数组， 而 HugeCalc 并不仅仅为RSA服务，所以其内部数据存放空间完全是动态的，包括输出转换出的字符串， 所以你在循环体里反复调用它，实际上它在反复申请空间。 而输出一般并不需要在循环体内反复调用， 你可以将它们单独分离出来对比测试一下， 这样测试才更科学。