找回密码
 欢迎注册
楼主: mathe

[讨论] 大素数阶有限域上的乘法运算

[复制链接]
 楼主| 发表于 2014-8-7 21:57:22 来自手机 | 显示全部楼层
我试了下用ipp对两个随机256比特大整数相乘。如果把cpu类型设置成未知,64位比32位快3倍,这个好理解。设成支持sse2,结果32位和64位速度相同。但是改成sse3以后,32位速度没有提升,但是64位提升将近3倍

点评

能不能帖一下代码。  发表于 2014-8-8 18:46
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-8-7 23:34:09 | 显示全部楼层
Intel 对自己的CPU最了解。它家的库对自己的CPu优化的很好。
看来我们需要好好研究下SSE3指令的乘法运算。

点评

256的可以搞个擂台,呵呵。  发表于 2014-8-8 18:41
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-8-8 19:05:02 | 显示全部楼层
很简单的乘法代码:
  1. #include <ippcp.h>
  2. #include <ippcore.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5. #define COUNT 1000000000
  6. int _tmain(int argc, _TCHAR* argv[])
  7. {
  8.     int bignumsize512=0;
  9.     int bignumsize256=0;
  10.     IppsBigNumState *pSum = NULL;
  11.     IppsBigNumState *pMul = NULL;
  12.     unsigned int data[256/32];
  13.     srand((int)time(NULL));
  14.     ippInit();
  15.     IppStatus error_code = ippsBigNumGetSize(512/32, &bignumsize512);
  16.     if(error_code != ippStsNoErr)
  17.         return -1;
  18.     error_code = ippsBigNumGetSize(256/32, &bignumsize256);
  19.     if(error_code != ippStsNoErr)
  20.         return -1;
  21.     int i;
  22.     for(i=0;i<256/32;i++)data[i]=rand()*65536+rand();
  23.     pSum = (IppsBigNumState *)malloc(bignumsize512);
  24.     pMul = (IppsBigNumState *)malloc(bignumsize256);
  25.     error_code = ippsBigNumInit(512/32, pSum);
  26.     ippsBigNumInit(256/32, pMul);
  27.     ippsSet_BN(IppsBigNumPOS, 256/32, data, pMul);
  28.     time_t start = time(NULL);
  29.     for(i=0;i<COUNT;i++){
  30.         ippsMul_BN(pMul, pMul, pSum);
  31.     }
  32.     printf("Total cost %d seconds\n", (int)(time(NULL)-start));
  33.         return 0;
  34. }
复制代码

$10^9$次乘法,ipp8.0, 64位代码30秒,32位机器73秒
如果换成ipp7.0, 64位代码63秒,32位95秒
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-9-19 07:49:38 来自手机 | 显示全部楼层
64位机器上做256比特乘法直接做16次乘法效率相当快了。就是不知道是否可以用toom-cook算法改进。比如分为52*5,只是toom-5不是很好设计。另外一个可以考虑的是如果我们改成支持56*4=224比特,效率是否可以高很多,toom-4只要7次乘法加些额外加减移位运算即可
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-9-19 09:56:35 | 显示全部楼层
256bit仅仅相当于8个机器字(32位模式)或者4个机器字(64位)模式,这种规模,硬乘法是最快的,toom-cook乘法运算的减少不足以抵消额外的加减和复制等操作的开销。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2014-10-10 19:06:39 | 显示全部楼层
普通两256比特整数乘法需要16次64比特整数乘法,而一个256比特整数平方需要10次64比特整数乘法
找到一篇文章: A Cryptographic Library for the Motorola DSP56000,利用其中算法,做一次Montgomery Reduce只需要20次64比特整数乘法。(远远好于二次乘法)

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2014-11-4 11:29:38 | 显示全部楼层
现在的CPU 5周期1次乘法,是不是256位乘,能在200周期完成?

点评

mathe有相关架构方面的资料么  发表于 2014-11-5 08:22
还可以并行做两到四次乘法的,所以应该可以更短  发表于 2014-11-4 19:23
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 20:46 , Processed in 0.045931 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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