HugeCalc vs. GMP

gxqcn · 发表于 2008-2-28 20:37:59

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

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

×

摘要转载自：http://topic.csdn.net/u/20080226 ... 5-a609c5c88f9c.html

以下代码是我在yaos原测试代码基础上略作修改得到的：

#include <stdio.h>
#include <tchar.h>
#include <windows.h>
#include <stdlib.h>
#include <time.h>
#include "Include/gmp.h"
#include "Include/HugeCalc.h"
#include "Include/HugeIntX.h"
#pragma comment( lib, "lib/libgmp-3.lib" /*"lib/gmp.lib"*/ )
#pragma comment( lib, "lib/HugeCalc.lib" )
unsigned long sizeList[] = {256, 512, 1024, 1536, 2048, 3072, 4096,
8192, 10240, 16384, 64000, 65536, 256000, 512000, 1048576, 33554432, 0x4000000, 0x6000000/*, 0x8000000, 0xC000000*/};
char hexChar[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
bool showLastErr( void )
{
bool bErr = TRUE;
switch( HugeCalc::GetLastError() )
{
case HCERR_NO_LICENSE:
printf("Last Error: HCERR_NO_LICENSE\n");
break;
case HCERR_USER_STOP:
printf("Last Error: HCERR_USER_STOP\n");
break;
case HCERR_NO_ENOUGH_MEMORY:
printf("Last Error: HCERR_NO_ENOUGH_MEMORY\n");
break;
case HCERR_INVALID_POINTER:
printf("Last Error: HCERR_INVALID_POINTER\n");
break;
case HCERR_DIV_ZERO:
printf("Last Error: HCERR_DIV_ZERO\n");
break;
case HCERR_BASE2SMALL:
printf("Last Error: HCERR_BASE2SMALL\n");
break;
case HCERR_RADIX2SMALL:
printf("Last Error: HCERR_RADIX2SMALL\n");
break;
case HCERR_NONE:
case HCERR_UNKNOWN:
default:
bErr = FALSE;
}
return bErr;
}
void RandomStr(char *p, int sizes) //随机填充16进制数字
{
srand(GetTickCount());
p[0] = 'F'; //保证达到特定大小
for (int i = 1; i < sizes; i ++)
{
p[i] = hexChar[rand() % 16];
}
}
int main(int argc, _TCHAR* argv[])
{
mpz_t gmp_a, gmp_b, gmp_c;
CHugeIntX huge_a, huge_b, huge_c;
LARGE_INTEGER CountFreq, start, stop;
double UsedTime;
int mult;//重复次数
int i, j;
char *pA, *pB;
QueryPerformanceFrequency(&CountFreq);
SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS);
//初始化
mpz_init(gmp_a);
mpz_init(gmp_b);
mpz_init(gmp_c);
#if 1
# define _RATIO 10UL /* 被乘数与乘数长度之比 */
#else
# define _RATIO 1UL /* 被乘数与乘数长度之比 */
#endif
printf("*** 被乘数与乘数长度之比为：%d ***\n\n", _RATIO);
i = sizeof(sizeList)/sizeof(sizeList[0]);
j = sizeList[i-1] / 4;
pA = (char *)malloc( j + 1 );
RandomStr(pA, j);
j /= _RATIO;
pB = (char *)malloc( j + 1 );
RandomStr(pB, j);
for (i = 0; i < sizeof(sizeList)/sizeof(sizeList[0]); i ++)
{
printf("现在计算长度(bits)： %d\n", sizeList[i]);
// 设定字串终止符
j = sizeList[i] / 4;
pA[j] = '\0';
pB[j/_RATIO] = '\0';
if (sizeList[i] < 10000) mult = 1000; else mult = 1;
//GMP Test
mpz_set_str(gmp_a, pA, 16);
mpz_set_str(gmp_b, pB, 16);
QueryPerformanceCounter(&start);
for (j = 0; j < mult; j ++)
mpz_mul(gmp_c, gmp_a, gmp_b);
QueryPerformanceCounter(&stop);
UsedTime = (double)(stop.QuadPart - start.QuadPart) * 1000000.0 / (double)CountFreq.QuadPart / (double)mult;
// printf( " gmp_c have %u bits\n", mpz_sizeinbase( gmp_c, 2 ) );
printf(" GMP 包计算时间(us)：%.3f\n", UsedTime);
// 释放内存
mpz_set_ui( gmp_a, 0 );
mpz_set_ui( gmp_b, 0 );
mpz_set_ui( gmp_c, 0 );
//HugeCalc Test
huge_a.SetHexStr((LPCTSTR)pA);
huge_b.SetHexStr((LPCTSTR)pB);
QueryPerformanceCounter(&start);
for (j = 0; j < mult; j ++)
huge_c.Mul(huge_a, huge_b);
QueryPerformanceCounter(&stop);
UsedTime = (double)(stop.QuadPart - start.QuadPart) * 1000000.0 / (double)CountFreq.QuadPart / (double)mult;
// printf( "huge_c have %u bits\n", huge_c.GetBits() );
printf(" HugeCalc包计算时间(us)：%.3f\n", UsedTime);
if ( showLastErr() )
break;
// 释放内存
huge_c = huge_a = huge_b = 0;
// 将字串终止符恢复成16进制数字
j = sizeList[i] / 4;
pA[j] = hexChar[rand() % 16];
pB[j/_RATIO] = hexChar[rand() % 16];
}
free( pA );
free( pB );
mpz_clear(gmp_a);
mpz_clear(gmp_b);
mpz_clear(gmp_c);
system( "pause" );
return 0;
}

复制代码

测试结果如下：

*** 被乘数与乘数长度之比为：10 ***
现在计算长度(bits)： 256
GMP 包计算时间(us)：0.048
HugeCalc包计算时间(us)：0.330
现在计算长度(bits)： 512
GMP 包计算时间(us)：0.133
HugeCalc包计算时间(us)：0.354
现在计算长度(bits)： 1024
GMP 包计算时间(us)：0.347
HugeCalc包计算时间(us)：0.614
现在计算长度(bits)： 1536
GMP 包计算时间(us)：0.608
HugeCalc包计算时间(us)：1.132
现在计算长度(bits)： 2048
GMP 包计算时间(us)：1.047
HugeCalc包计算时间(us)：1.792
现在计算长度(bits)： 3072
GMP 包计算时间(us)：2.115
HugeCalc包计算时间(us)：4.024
现在计算长度(bits)： 4096
GMP 包计算时间(us)：3.532
HugeCalc包计算时间(us)：6.530
现在计算长度(bits)： 8192
GMP 包计算时间(us)：18.964
HugeCalc包计算时间(us)：21.784
现在计算长度(bits)： 10240
GMP 包计算时间(us)：37.994
HugeCalc包计算时间(us)：38.832
现在计算长度(bits)： 16384
GMP 包计算时间(us)：67.048
HugeCalc包计算时间(us)：86.324
现在计算长度(bits)： 64000
GMP 包计算时间(us)：676.622
HugeCalc包计算时间(us)：1481.753
现在计算长度(bits)： 65536
GMP 包计算时间(us)：607.060
HugeCalc包计算时间(us)：1387.048
现在计算长度(bits)： 256000
GMP 包计算时间(us)：4379.328
HugeCalc包计算时间(us)：5920.026
现在计算长度(bits)： 512000
GMP 包计算时间(us)：11874.973
HugeCalc包计算时间(us)：12876.776
现在计算长度(bits)： 1048576
GMP 包计算时间(us)：35291.357
HugeCalc包计算时间(us)：26408.384
现在计算长度(bits)： 33554432
GMP 包计算时间(us)：1331961.464
HugeCalc包计算时间(us)：1184980.773
现在计算长度(bits)： 67108864
GMP 包计算时间(us)：3154349.226
HugeCalc包计算时间(us)：2320234.555
现在计算长度(bits)： 100663296
GMP 包计算时间(us)：4559124.414
HugeCalc包计算时间(us)：4328886.772
请按任意键继续. . .

复制代码

测试环境：Windows XP SP2，AMD Athlon 64 Processor 3200+，1GB DDR - 200MHz

通过原帖对最最核心算法的测试数据表明：
1、即便在单核上，HugeCalc一样可以击败号称“地球上最快”的大数库GMP；
2、在多核上，HugeCalc可领先更多；
3、HugeCalc需要对小规模计算算法进一步提速；
4、HugeCalc效率最高的接口方式是C++静态导入，而后是C动态导入，最后是TLB形式；
5、还可以总结更多的。。。

需进一步说明的是：
3、——这与HugeCalc需实时检测退出标志，从而可实时响应用户终止计算请求有关；当然代码应还有优化余地；
4、——导出tlb形式的COM接口源于C接口-->C接口又源于C++接口；且C接口采用了“内部全程自动监控各函数出入口变量机制”而使效率略有折扣，但换来的是系统的安全稳定，值！
比如下段代码：

HHUGEINTX hResult;
HCErrCode lastErr;
hResult = new_HX(); (1)
HI_set_u32( hResult, 1 ); (2)
HI_decLShift( hResult, 100 ); (3)
lastErr = HC_getLastError(); (4)

复制代码

上述代码虽然可以通过编译；但运行时，lastErr 将返回 HCERR_INVALID_POINTER，其实该问题首次产生于语句(2)，语句(3)也有问题，这样以帮助开发者调试程序。

关于测试源代码、运行动态库及编译好的测试程序，打包如下：

GMPvsHC.rar (451.62 KB, 下载次数: 42) （请注意阅读压缩包上的注释）

gxqcn · 发表于 2008-2-28 20:49:35

最初我用的是zip格式压缩的，没注意到有513KB了（超出论坛附件大小上限），结果导致发帖失败！

而发帖前又忘了先备份文字，害得我又得再排版半天。

其实这个帖子还有段特别的背景：
前段日子在CSDN上与yaos(无心人)有点误会，彼此都很郁闷。
其实也没什么大不了的：他是想给我泼泼凉水，但可能语气措词等不太讲究，
而我又无法适应yaos式的“玩笑帖”/“无知帖”的幽默，误认为是种挑衅行为，
所以彼此都不开心。

在共同完成了这次测试后（测试代码及测试结果也得到了发起人yaos本人的认同），

我们通过 CSDN IM 进行了沟通，消除了之前的误会，并在最后彼此将对方加为好友

mathe · 发表于 2008-2-29 08:53:59

"内部全程自动监控各函数出入口变量机制" ---这是起什么作用呢？能解释一下吗？
好友，我觉得有点奇怪的是为什么效率最高的反而是C++接口，而不是C接口。通常开发软件过程中库文件应该用C接口比较好，如果采用C++接口，我担心跨越编译器会有问题(比如说用户换成VC以外的其他编译器可能链接不了).
TLB是什么的缩写呀，是指COM接口？

guetsxjm · 发表于 2008-2-29 09:12:45

郭老大太专业啦，很多名词都要上百度去搜索

关于TLB，百度结果：Translation lookaside buffer，即旁路转换缓冲，或称为页表缓冲；
可还是看不懂，有劳楼主解释哈

gxqcn: 还是直呼我的ID吧，这样也蛮亲热的。论坛里比我年长者有之，比我水平高的大有人在。。。

gxqcn · 发表于 2008-2-29 09:28:04

因为我的核心部分是用C++开发的，为了方便纯C的用户，所以包装了一下导出了C接口；
又为了适应VB、Delphi等编程环境，再将C接口以tlb（type-library）形式导出。

用 HX_new()、HI_new() 或 RC_new() 得到的 HANDLE 指针均为 LPVOID 类型，
编译器无法进行正确区别，
为了防止用户混用，我特意对调用上述函数的变量进行跟踪，
从其生命周期开始即进行登记备案，
以后用户调用相关函数时，都要先调查其“户籍所在地”，防止被误用混用，
也即把编译器的不足给找回来：
　　现在终于可正确识别 HHUGEINT / HHUGEINTX / HRADIXCONVERTER 类型了。

特别地，若用户忘了将申请的变量通过调用相应的 HI_delete() / HX_delete() / RC_delete() 销毁，HugeCalc.DLL 在临退出前会自动调用上述函数以防止内存泄露。

以上“监控机制”为我自创的，当时琢磨了好久，实现后很是兴奋，
由于该机制相对于大数计算来说，所占的工作量不大，所以对大规模计算影响甚微。

而C++类型本身在编译期即可进行类型检查，所以不需要上述过程。

gxqcn · 发表于 2008-2-29 09:54:59

仅仅一个DLL，即可提供多种标准模式的接口，并自动适应 MBCS / UNICODE 环境。

这正是我的 HugeCalc.dll 比较得意之处之一。

liangbch · 发表于 2008-2-29 10:26:12

楼主是一个完美主义者，做什么要要做精。一个大数运算库，应用了这么多技术，一般人很真折腾不起。包括汇编语言编程，SSE2指令优化，读取 CPU 信息的技术，读取硬件特征生成序列号的技术，序列号到注册码的算法，未注册版本随机错误，同时支持MBCB and UNIcode, 多种语言和Com接口，多线程，检测到用户按了cancel按钮，在大数运算函数中自动终止等。
其他未尽的技术，楼主能否奉献出来？

gxqcn · 发表于 2008-2-29 10:37:07

liangbch 兄几乎快把我的家底都透光了

好像也没别的好得意的了，再加一条：注册码与版本号相关联；但用户一旦注册，可终身自动升级。

忽然又想到了一条：全算法库，包括周边的测试程序等，我写的代码中不含一条浮点指令。即便大家看到的带小数点的计时输出，那也是全由整型得到的。

mathe · 发表于 2008-2-29 12:37:09

原帖由 gxqcn 于 2008-2-29 09:28 发表
因为我的核心部分是用C++开发的，为了方便纯C的用户，所以包装了一下导出了C接口；
又为了适应VB、Delphi等编程环境，再将C接口以tlb（type-library）形式导出。

用 HX_new()、HI_new() 或 RC_new() 得到的 HAND ...

你可以试着定义一些不包含任何数据的类，不如
typedef struct __tag_HX{
}*PHX;
typedef struct __tag_HI{
}*PHI;
然后定义函数原型
PHX HX_new();
PHI HI_new();
等，这样用户使用C接口代码中，编译器就应该可以帮忙检查类型了

gxqcn · 发表于 2008-2-29 12:48:20

这个解决方案太强了！
我以后试试！谢谢 mathe！

账号		自动登录	找回密码
密码			欢迎注册

[测试] HugeCalc vs. GMP

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

题外话

回复 3# 的帖子

回复 7# 的帖子

评分

回复 9# 的帖子