高速大数乘法 pk HugeCalc
由于工作需要，写了个大数乘法算法（作为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" ) 理论上乘法速度还可以再优化10%左右^^
有空我再搞一下，嘿嘿
对了，忘记说了，上面测试使用的cpu是我可怜的 AMD Sempron 1.75GHz, 内存1G（这不是瓶颈） 可惜,你的测试程序写得不对.简单重复乘法操作会被编译器优化的 下载了你的附件，发现你的测试代码不公平。
1、对 HugeCalc 的测试，你是在循环体内进行构造、析构的，这本身需要耗用一定的时间；
2、在 HugeCalc 中，“c = ( a * b )”可用“c.Mul(a,b)”替换，应更高效。
你可以看看增大输入后，两者耗时的上升趋势如何？曲线曲率越小的越优。
关于 HugeCalc，它设计定位在超大数的快速运算，
在数据结构以及算法上尽量优先满足超大数的计算，
所以对小规模的计算并未做太多的优化，
但这个情形不会长久下去，
在下次内核大改动时会一并考虑的。 呵呵,没有注意还附带测试程序:
LZ的函数
HugeMul();
的调用方法很奇怪.
我修改了一下代码:
DWORD dwRet = Init( "0x9A34567890123456789012345678901234567890123456789012345678901234", "0x9A34567890123456789012345678901234567890123456789012345678901234" );
for( int times = 0; times < 100000; ++times )
{
HugeMul();
}
CHugeIntX a( "0x9A34567890123456789012345678901234567890123456789012345678901234" );
CHugeIntX b( "0x9A34567890123456789012345678901234567890123456789012345678901234" );
CHugeIntX c;
for( int times = 0; times < 100000; ++times )
{
c.Mul(a,b);
}
然后为了防止编译器优化引起的影响,选择Debug方式编译.
运行结果HugeLib 0.0414秒,HugeCalc0.0271秒 其实我觉得要做比较,最好直接拿像PowMod之类比较复杂的运算比较好一些. 这样,其它意外因素影响会小一些 如5楼所言，我改成那个样子，并用Debug方式编译，在我Intel Pentium Dual E2180 2.00GHz系统上，
使用我的算法，耗时0.0581秒，使用HugeCalc，耗时0.139秒。和你的测试结果完全不同。奇哉，怪也。
我测了一下我算法执行的计算机指令周期数，512位*512位，我的算法经历了 3139 个指令周期 4楼的同志，不太了解你的算法库，刚刚接触而已。工作需要，本来想直接用你的，可是发现有限制，所以只好自己写了，郁闷。:( 4楼，有点不明白，为啥你那大数转换为字符串输出，要花那么多时间。希望你尽快完善哈^^ 总体来说你的软件还是很不错的 HugeCalc 的输入输出的效率并不低，是经过特别优化过的。
如果仅仅为RSA服务，完全可以开一个足够大的固定数组，
而 HugeCalc 并不仅仅为RSA服务，所以其内部数据存放空间完全是动态的，包括输出转换出的字符串，
所以你在循环体里反复调用它，实际上它在反复申请空间。
而输出一般并不需要在循环体内反复调用，
你可以将它们单独分离出来对比测试一下，
这样测试才更科学。
页:
[1]
2