mathe 发表于 2014-8-7 21:57:22

我试了下用ipp对两个随机256比特大整数相乘。如果把cpu类型设置成未知，64位比32位快3倍，这个好理解。设成支持sse2,结果32位和64位速度相同。但是改成sse3以后，32位速度没有提升，但是64位提升将近3倍

liangbch 发表于 2014-8-7 23:34:09

Intel 对自己的CPU最了解。它家的库对自己的CPu优化的很好。
看来我们需要好好研究下SSE3指令的乘法运算。

mathe 发表于 2014-8-8 19:05:02

很简单的乘法代码:
#include <ippcp.h>
#include <ippcore.h>
#include <stdlib.h>
#include <time.h>
#define COUNT 1000000000
int _tmain(int argc, _TCHAR* argv[])
{
    int bignumsize512=0;
    int bignumsize256=0;
    IppsBigNumState *pSum = NULL;
    IppsBigNumState *pMul = NULL;
    unsigned int data;
    srand((int)time(NULL));
    ippInit();
    IppStatus error_code = ippsBigNumGetSize(512/32, &bignumsize512);
    if(error_code != ippStsNoErr)
      return -1;
    error_code = ippsBigNumGetSize(256/32, &bignumsize256);
    if(error_code != ippStsNoErr)
      return -1;
    int i;
    for(i=0;i<256/32;i++)data=rand()*65536+rand();
    pSum = (IppsBigNumState *)malloc(bignumsize512);
    pMul = (IppsBigNumState *)malloc(bignumsize256);
    error_code = ippsBigNumInit(512/32, pSum);
    ippsBigNumInit(256/32, pMul);
    ippsSet_BN(IppsBigNumPOS, 256/32, data, pMul);
    time_t start = time(NULL);
    for(i=0;i<COUNT;i++){
      ippsMul_BN(pMul, pMul, pSum);
    }
    printf("Total cost %d seconds\n", (int)(time(NULL)-start));
        return 0;
}

$10^9$次乘法，ipp8.0, 64位代码30秒，32位机器73秒
如果换成ipp7.0, 64位代码63秒，32位95秒

mathe 发表于 2014-9-19 07:49:38

64位机器上做256比特乘法直接做16次乘法效率相当快了。就是不知道是否可以用toom-cook算法改进。比如分为52*5,只是toom-5不是很好设计。另外一个可以考虑的是如果我们改成支持56＊4=224比特，效率是否可以高很多，toom-4只要7次乘法加些额外加减移位运算即可

liangbch 发表于 2014-9-19 09:56:35

256bit仅仅相当于8个机器字（32位模式）或者4个机器字（64位）模式，这种规模，硬乘法是最快的，toom-cook乘法运算的减少不足以抵消额外的加减和复制等操作的开销。

mathe 发表于 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周期完成？
页: 1 [2]
查看完整版本: 大素数阶有限域上的乘法运算