数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
查看: 21008|回复: 61

[测试] HugeCalc vs. GMP

[复制链接]
发表于 2008-2-28 20:37:59 | 显示全部楼层 |阅读模式

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

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

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

以下代码是我在yaos原测试代码基础上略作修改得到的:
  1. #include <stdio.h>
  2. #include <tchar.h>
  3. #include <windows.h>
  4. #include <stdlib.h>
  5. #include <time.h>

  6. #include "Include/gmp.h"
  7. #include "Include/HugeCalc.h"
  8. #include "Include/HugeIntX.h"

  9. #pragma comment( lib, "lib/libgmp-3.lib" /*"lib/gmp.lib"*/ )
  10. #pragma comment( lib, "lib/HugeCalc.lib" )

  11. unsigned long sizeList[] = {256, 512, 1024, 1536, 2048, 3072, 4096,
  12. 8192, 10240, 16384, 64000, 65536, 256000, 512000, 1048576, 33554432, 0x4000000, 0x6000000/*, 0x8000000, 0xC000000*/};
  13. char hexChar[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};


  14. bool showLastErr( void )
  15. {
  16.     bool bErr = TRUE;

  17.     switch( HugeCalc::GetLastError() )
  18.     {
  19.     case HCERR_NO_LICENSE:
  20.         printf("Last Error: HCERR_NO_LICENSE\n");
  21.         break;

  22.     case HCERR_USER_STOP:
  23.         printf("Last Error: HCERR_USER_STOP\n");
  24.         break;

  25.     case HCERR_NO_ENOUGH_MEMORY:
  26.         printf("Last Error: HCERR_NO_ENOUGH_MEMORY\n");
  27.         break;

  28.     case HCERR_INVALID_POINTER:
  29.         printf("Last Error: HCERR_INVALID_POINTER\n");
  30.         break;

  31.     case HCERR_DIV_ZERO:
  32.         printf("Last Error: HCERR_DIV_ZERO\n");
  33.         break;

  34.     case HCERR_BASE2SMALL:
  35.         printf("Last Error: HCERR_BASE2SMALL\n");
  36.         break;

  37.     case HCERR_RADIX2SMALL:
  38.         printf("Last Error: HCERR_RADIX2SMALL\n");
  39.         break;


  40.     case HCERR_NONE:
  41.     case HCERR_UNKNOWN:
  42.     default:
  43.         bErr = FALSE;
  44.     }

  45.     return bErr;
  46. }

  47. void RandomStr(char *p, int sizes) //随机填充16进制数字
  48. {
  49.     srand(GetTickCount());
  50.     p[0] = 'F'; //保证达到特定大小
  51.     for (int i = 1; i < sizes; i ++)
  52.     {
  53.         p[i] = hexChar[rand() % 16];
  54.     }
  55. }

  56. int main(int argc, _TCHAR* argv[])
  57. {
  58.     mpz_t gmp_a, gmp_b, gmp_c;
  59.     CHugeIntX huge_a, huge_b, huge_c;
  60.     LARGE_INTEGER CountFreq, start, stop;
  61.     double UsedTime;
  62.     int mult;//重复次数
  63.     int i, j;
  64.     char *pA, *pB;

  65.     QueryPerformanceFrequency(&CountFreq);
  66.     SetPriorityClass(GetCurrentProcess(), REALTIME_PRIORITY_CLASS);

  67.     //初始化
  68.     mpz_init(gmp_a);
  69.     mpz_init(gmp_b);
  70.     mpz_init(gmp_c);

  71. #if 1
  72. #   define _RATIO  10UL  /* 被乘数与乘数长度之比 */
  73. #else
  74. #   define _RATIO   1UL  /* 被乘数与乘数长度之比 */
  75. #endif

  76.     printf("*** 被乘数与乘数长度之比为:%d ***\n\n", _RATIO);

  77.     i = sizeof(sizeList)/sizeof(sizeList[0]);
  78.     j = sizeList[i-1] / 4;

  79.     pA = (char *)malloc( j + 1 );
  80.     RandomStr(pA, j);

  81.     j /= _RATIO;
  82.     pB = (char *)malloc( j + 1 );
  83.     RandomStr(pB, j);

  84.     for (i = 0; i < sizeof(sizeList)/sizeof(sizeList[0]); i ++)
  85.     {
  86.         printf("现在计算长度(bits): %d\n", sizeList[i]);

  87.         // 设定字串终止符
  88.         j = sizeList[i] / 4;
  89.         pA[j] = '\0';
  90.         pB[j/_RATIO] = '\0';


  91.         if (sizeList[i] < 10000) mult = 1000; else mult = 1;


  92.         //GMP Test
  93.         mpz_set_str(gmp_a, pA, 16);
  94.         mpz_set_str(gmp_b, pB, 16);
  95.         QueryPerformanceCounter(&start);
  96.         for (j = 0; j < mult; j ++)
  97.             mpz_mul(gmp_c, gmp_a, gmp_b);
  98.         QueryPerformanceCounter(&stop);
  99.         UsedTime = (double)(stop.QuadPart - start.QuadPart) * 1000000.0 / (double)CountFreq.QuadPart / (double)mult;
  100. //      printf( " gmp_c have %u bits\n", mpz_sizeinbase( gmp_c, 2 ) );
  101.         printf("    GMP     包计算时间(us):%.3f\n", UsedTime);

  102.         // 释放内存
  103.         mpz_set_ui( gmp_a, 0 );
  104.         mpz_set_ui( gmp_b, 0 );
  105.         mpz_set_ui( gmp_c, 0 );


  106.         //HugeCalc Test
  107.         huge_a.SetHexStr((LPCTSTR)pA);
  108.         huge_b.SetHexStr((LPCTSTR)pB);
  109.         QueryPerformanceCounter(&start);
  110.         for (j = 0; j < mult; j ++)
  111.             huge_c.Mul(huge_a, huge_b);
  112.         QueryPerformanceCounter(&stop);
  113.         UsedTime = (double)(stop.QuadPart - start.QuadPart) * 1000000.0 / (double)CountFreq.QuadPart / (double)mult;
  114. //      printf( "huge_c have %u bits\n", huge_c.GetBits() );
  115.         printf("    HugeCalc包计算时间(us):%.3f\n", UsedTime);

  116.         if ( showLastErr() )
  117.             break;

  118.         // 释放内存
  119.         huge_c = huge_a = huge_b = 0;

  120.         // 将字串终止符恢复成16进制数字
  121.         j = sizeList[i] / 4;
  122.         pA[j] = hexChar[rand() % 16];
  123.         pB[j/_RATIO] = hexChar[rand() % 16];
  124.     }

  125.     free( pA );
  126.     free( pB );

  127.     mpz_clear(gmp_a);
  128.     mpz_clear(gmp_b);
  129.     mpz_clear(gmp_c);

  130.     system( "pause" );

  131.     return 0;
  132. }
复制代码
测试结果如下:
  1. *** 被乘数与乘数长度之比为:10 ***

  2. 现在计算长度(bits): 256
  3.     GMP     包计算时间(us):0.048
  4.     HugeCalc包计算时间(us):0.330
  5. 现在计算长度(bits): 512
  6.     GMP     包计算时间(us):0.133
  7.     HugeCalc包计算时间(us):0.354
  8. 现在计算长度(bits): 1024
  9.     GMP     包计算时间(us):0.347
  10.     HugeCalc包计算时间(us):0.614
  11. 现在计算长度(bits): 1536
  12.     GMP     包计算时间(us):0.608
  13.     HugeCalc包计算时间(us):1.132
  14. 现在计算长度(bits): 2048
  15.     GMP     包计算时间(us):1.047
  16.     HugeCalc包计算时间(us):1.792
  17. 现在计算长度(bits): 3072
  18.     GMP     包计算时间(us):2.115
  19.     HugeCalc包计算时间(us):4.024
  20. 现在计算长度(bits): 4096
  21.     GMP     包计算时间(us):3.532
  22.     HugeCalc包计算时间(us):6.530
  23. 现在计算长度(bits): 8192
  24.     GMP     包计算时间(us):18.964
  25.     HugeCalc包计算时间(us):21.784
  26. 现在计算长度(bits): 10240
  27.     GMP     包计算时间(us):37.994
  28.     HugeCalc包计算时间(us):38.832
  29. 现在计算长度(bits): 16384
  30.     GMP     包计算时间(us):67.048
  31.     HugeCalc包计算时间(us):86.324
  32. 现在计算长度(bits): 64000
  33.     GMP     包计算时间(us):676.622
  34.     HugeCalc包计算时间(us):1481.753
  35. 现在计算长度(bits): 65536
  36.     GMP     包计算时间(us):607.060
  37.     HugeCalc包计算时间(us):1387.048
  38. 现在计算长度(bits): 256000
  39.     GMP     包计算时间(us):4379.328
  40.     HugeCalc包计算时间(us):5920.026
  41. 现在计算长度(bits): 512000
  42.     GMP     包计算时间(us):11874.973
  43.     HugeCalc包计算时间(us):12876.776
  44. 现在计算长度(bits): 1048576
  45.     GMP     包计算时间(us):35291.357
  46.     HugeCalc包计算时间(us):26408.384
  47. 现在计算长度(bits): 33554432
  48.     GMP     包计算时间(us):1331961.464
  49.     HugeCalc包计算时间(us):1184980.773
  50. 现在计算长度(bits): 67108864
  51.     GMP     包计算时间(us):3154349.226
  52.     HugeCalc包计算时间(us):2320234.555
  53. 现在计算长度(bits): 100663296
  54.     GMP     包计算时间(us):4559124.414
  55.     HugeCalc包计算时间(us):4328886.772
  56. 请按任意键继续. . .
复制代码
测试环境: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接口采用了“内部全程自动监控各函数出入口变量机制”而使效率略有折扣,但换来的是系统的安全稳定,值!
比如下段代码:
  1. HHUGEINTX hResult;
  2. HCErrCode lastErr;

  3. hResult = new_HX();              (1)
  4. HI_set_u32( hResult, 1 );        (2)
  5. HI_decLShift( hResult, 100 );    (3)
  6. lastErr = HC_getLastError();     (4)
复制代码
上述代码虽然可以通过编译;但运行时,lastErr 将返回 HCERR_INVALID_POINTER,其实该问题首次产生于语句(2),语句(3)也有问题,这样以帮助开发者调试程序。

关于测试源代码、运行动态库及编译好的测试程序,打包如下: GMPvsHC.rar (451.62 KB, 下载次数: 42)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-28 20:49:35 | 显示全部楼层

题外话

最初我用的是zip格式压缩的,没注意到有513KB了(超出论坛附件大小上限),结果导致发帖失败!
而发帖前又忘了先备份文字,害得我又得再排版半天。

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

在共同完成了这次测试后(测试代码及测试结果也得到了发起人yaos本人的认同),
我们通过 CSDN IM 进行了沟通,消除了之前的误会,并在最后彼此将对方加为好友
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-29 08:53:59 | 显示全部楼层
"内部全程自动监控各函数出入口变量机制" ---这是起什么作用呢?能解释一下吗?
好友,我觉得有点奇怪的是为什么效率最高的反而是C++接口,而不是C接口。通常开发软件过程中库文件应该用C接口比较好,如果采用C++接口,我担心跨越编译器会有问题(比如说用户换成VC以外的其他编译器可能链接不了).
TLB是什么的缩写呀,是指COM接口?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-29 09:12:45 | 显示全部楼层
郭老大太专业啦,很多名词都要上百度去搜索
关于TLB,百度结果:Translation lookaside buffer,即旁路转换缓冲,或称为页表缓冲;
可还是看不懂,有劳楼主解释哈

gxqcn: 还是直呼我的ID吧,这样也蛮亲热的。论坛里比我年长者有之,比我水平高的大有人在。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-29 09:28:04 | 显示全部楼层

回复 3# 的帖子

因为我的核心部分是用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++类型本身在编译期即可进行类型检查,所以不需要上述过程。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-29 09:54:59 | 显示全部楼层
仅仅一个DLL,即可提供多种标准模式的接口,并自动适应 MBCS / UNICODE 环境。

这正是我的 HugeCalc.dll 比较得意之处之一。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-2-29 10:26:12 | 显示全部楼层
楼主是一个完美主义者,做什么要要做精。一个大数运算库,应用了这么多技术,一般人很真折腾不起。包括汇编语言编程,SSE2指令优化,读取 CPU 信息的技术, 读取硬件特征生成序列号的技术,序列号到 注册码的算法,未注册版本随机错误,同时支持MBCB and UNIcode, 多种语言和Com接口,多线程,检测到用户按了cancel按钮,在大数运算函数中自动终止等。
  其他未尽的技术,楼主能否奉献出来?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-2-29 10:37:07 | 显示全部楼层

回复 7# 的帖子

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

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

忽然又想到了一条:全算法库,包括周边的测试程序等,我写的代码中不含一条浮点指令。即便大家看到的带小数点的计时输出,那也是全由整型得到的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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接口代码中,编译器就应该可以帮忙检查类型了

评分

参与人数 1威望 +2 贡献 +3 鲜花 +5 收起 理由
gxqcn + 2 + 3 + 5 谢谢如此绝妙的解决方案!:)

查看全部评分

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

回复 9# 的帖子

这个解决方案太强了!
我以后试试!谢谢 mathe!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2017-7-26 18:34 , Processed in 0.294231 second(s), 26 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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