高速大数乘法 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();
的调用方法很奇怪.
我修改了一下代码:

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

复制代码

1. 
   
2.     CHugeIntX a( "0x9A34567890123456789012345678901234567890123456789012345678901234" );
   
3.     CHugeIntX b( "0x9A34567890123456789012345678901234567890123456789012345678901234" );
   
4.     CHugeIntX c;
   
5. 
   
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服务，所以其内部数据存放空间完全是动态的，包括输出转换出的字符串，
所以你在循环体里反复调用它，实际上它在反复申请空间。

而输出一般并不需要在循环体内反复调用，
你可以将它们单独分离出来对比测试一下，
这样测试才更科学。