论坛 › 算法交流 › 大数乘法速度过慢，求助？

落叶 发表于 2016-4-30 12:28:54

大数乘法速度过慢，求助？

我的电脑配置cpu为i5-2300，2.8G，32位操作系统，准备过一段时间改64位操作系统，所用编译器vc6.0,vb6.0
我的乘法是采用FFT算法的乘法(vc做的dll,是用别人的源码修改了一下l)，万位乘万位（十进制），精度一万，用时16.6ms ,不如论坛公布的数据，BTCAL疯狂计算器v2.5（在网上搜的，感觉还算不错的计算器）在我的电脑上用时4ms，如是我决定调用GMP的乘法试试，经过N天的学习，总算调用成功，也是用VC做的DLL，用时竟然是17.7ms，和我原先的乘法差不多（稍慢一点的原因可能是中间的参数不一致，多次转换造成的，我是用VB调用的）
我自已分析，我的FFT乘法中用到的浮点运算是64位浮点指令，好象我的cpu是支持80位浮点指令，FFT乘法没有用上更高效的指令。
但GMP的乘法据说可以根据硬件调用不同的代码，为什么速度也不快，会不会是我下的版本过低？没有采用更快的算法，GMP我用的是这个函数：mpz_mul(rop,opa,opb);
另外利用快速数论变换（NTT）实现的乘法更快，不知道和FFT乘法比，效率提高多少？
请网友们帮我分析分析，不甚感谢！

liangbch 发表于 2016-4-30 16:38:16

GMP绝对不会这么慢。我怀疑你这个时间包含输入（字符串转化为GMP的内部表示）和输出（GMP的内部表示转化为字符串）的时间。
你单独测下mpz_mul的运行时间。
另外，我认为 1万位10进制用FFT不是最快的，Toom-Took算法也许完胜FFT。

liangbch 发表于 2016-5-2 16:26:41

我的测试结果是，使用muz_mul计算两个1万位十进制数乘积，用时0.15毫秒，是你报告的速度的100倍。
我的测试环境是：
OS： Windows7 64bit,
CPU: I7-4700HQ
程序：GMP 是32位的版本，测试程序也是32位的。

liangbch 发表于 2016-5-2 16:27:37

这里给出我的测试程序。

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include "gmp.h"

static LARGE_INTEGER freq;

static BOOL initFreq()
{
        BOOL ret;
        if ( !QueryPerformanceFrequency( &freq) )
        {        ret=FALSE;        }
        else
        {        ret=TRUE;        }
        return ret;
}

double currTime() //使用高精度计时器
{       
        LARGE_INTEGER performanceCount;
        BOOL result;
        double time=0.0;
        BOOL bRet=TRUE;

        if (freq.QuadPart==0)
        {
                bRet=initFreq();
        }
       
        if (bRet)
        {
                result=QueryPerformanceCounter(&performanceCount );
                time= performanceCount.HighPart * 4294967296.0 + performanceCount.LowPart;
                time=time / (   freq.HighPart * 4294967296.0 + freq.LowPart);
        }
        return time;
}


void generate_an_integer(int dig_len, mpz_t x)
{
        int i;
        char c;
        char *pBuff=NULL;

        pBuff=(char *) malloc(dig_len+8);
        if ( pBuff==NULL)
        {
                printf("Alloc memory failed on %s:%d\n",__FILE__,__LINE__);
                return;
        }
       
        srand(GetTickCount());
        while (1)
        {
                c=rand() % 10;
                if (c >0)
                {
                        pBuff= c + 0x30;
                        break;
                }
        }
       
        for (i=1;i<dig_len;i++)
                pBuff=(rand() %10)+0x30;
        pBuff=0;
       
        mpz_set_str (x,pBuff,10);

        if ( pBuff!=NULL)
        {
                free(pBuff); pBuff=NULL;
        }
}

void test_mpz_mul(int dig_len)
{
        int j,test_count;
       
        mpz_t a;
        mpz_t b;
        mpz_t prod;
        mpz_t s;

        int len;
        size_t r_len;

        double startTime;
        double testTime;
        //---------------------
       
        test_count=1000;
        r_len = dig_len *10/3+32;

        mpz_init(a);
        mpz_init(b);
        mpz_init2(prod,r_len);
        mpz_init2(s,r_len);

        generate_an_integer(dig_len,a);
        generate_an_integer(dig_len,b);
        mpz_set_ui(s,0);

        //--------------------------------------
        startTime=currTime();
        for (j=0;j<test_count;j++)
        {
                mpz_mul (prod,a,b);
                mpz_add(s,s,prod);
        }
        testTime=currTime()-startTime;
        testTime =testTime * 1000 / (test_count); //get unit time by ms
       
        len=mpz_sizeinbase(s,10);
        printf("the result contain about %d digital\n", len);
        printf("It take %.4lf ms\n", testTime);
       
        mpz_clear(a);
        mpz_clear(b);
        mpz_clear(prod);
        mpz_clear(s);
}

落叶 发表于 2016-5-2 23:21:38

本帖最后由 落叶 于 2016-5-3 00:05 编辑

liangbch（良师益友）！浪费你N多时间给了这么详细的解答，:b:
忙了半天，才把你的程序运行成功，对这个函数（void test_mpz_mul(int dig_len)）输入10000，报告显示运行1.37ms，又把你的测试时间代码复制到我的DLL程序上测试，10000乘10000用时0.0014，因为你的测试是按1000次循环算的，我没有加循环，所以这里可以判断用时1.4ms,和你的运行时间一致，然后用你的测试代码测试整个子程序，用时15.8ms,里面包含耗时的三行代码：下面的红色代码
            mpz_set_str(opa,op1,10);   
            mpz_set_str(opb,op2,10);
            mpz_mul(rop,opa,opb);
          mpz_get_str(op1,10,rop);
和我在VB中的测试一致（15.6）
如果我的上面所述是对的话，那么现在的速度瓶颈是那些辅助程序，辅助程序搞不好，核心算法即使再加速，效果也不太明显，再次感谢！
另外我再次单独测试的我的FFT乘法子程序，用时6.2ms,具体为什么会比GMP快，应该是FFT返回的是千进制数（因为我传递的是千进制数，fft乘在32位机上采用千进制时，可以提供25800位的（十进数）精度），而GMP返回的是字符串，它多做了一个转换。传参进去后它还要多做两次转换。
GMP的大多数 函数的数据传递是用字符串，
我早先写的程序也是用字符串传递，最后实在是难以忍受，重新设计了一个数据结构存放高精度数，用于各个子程序之间的数据交换：

       Type StrToZx                                    '高精度数的结构头
            ZhFhBz As Boolean                        '正负号标志
            XsdWz As Long                           '小数点右边数字的长度。例1234.567中这个数是3（为什么要这样定义，因为大多的基本运算都是右对齐的，这样定义减少了中间一些不必要的转换）
            JzBz As Integer                           '标记数组存的是什么进制的数（十进制或其它进制数）
            strlen As Long                               '运算数长度
            Zx() As Long                                 '存放运算数的数组
            eE As Long                                 '存放指数
      End Type

落叶 发表于 2016-5-6 19:43:38

本帖最后由 落叶 于 2016-5-6 19:52 编辑

测试了一下这个函数 mpz_set_str(opa,op1,10); 一万位十进制字符串转换用时4ms左右， 这个函数实际上是把字符串转换成十六进制数
我自已写了一个十进制转十六进制程序，所用原理是除模取余法，一万位十进制转换用时竟然是1.6s,和mpz_set_str（）函数相比相差400倍，不知道它是如何实现的？
我写的十进制转万进制，用的是很普通的算法，按权相加法，一万位十进制转换用时0.5ms，准备在十进制和万进制之间做个对应表加速。
除模取余法，按权相加法两种方法，不实用两种不同类型的大数进制转换，如：十进制和十六进制互转。
在网上找了几天，也没找到更好的算法。

liangbch 发表于 2016-5-9 15:20:21

看看这个 《超长2进制数串转换为10进制数》
http://bbs.csdn.net/topics/270058394

落叶 发表于 2016-5-10 20:39:01

本帖最后由 落叶 于 2016-5-10 20:43 编辑

经过几天的优化进制转换，我的加减法算法又回到了原始社会，
原先的加减法是采用亿进制计算，理论上比十进制快9倍，但进制转换却耗去了大部分的时间，因为是采用的十进制数进行各个程序之间的数据交换，我决定改用十进制加减算法，省掉中间的进制转换，
现加减子程序的综合速度比原先的还快了5倍左右，无语中...
原先的万位sinx用时6.5ms,经过一定的进制转换子程序优化，变为5.78ms，然后再把加减法采用上述方法，速度提高到5.1ms.

liangbch 发表于 2016-5-11 10:38:18

我觉得你陷入一个误区。
在大整数计算中，仅仅输入的数据和最终输出结果采用10进制表示 (字符串), 所有的中间结果一定要采用内部格式表示，如万进制和\( 10^9 \)。这样，进制转化所占用的时间将大大减少。

liangbch 发表于 2016-5-11 10:40:45

如果核心部分想调用基于2进制的大数库，如GMP, 你的内部格式需要使用\( 2^k \) 进制表示。
如果核心部分想调用基于10进制的大数库，如apfloat和HugeCalc, 你的内部格式需要使用\( 10^k \) 表示。

查看完整版本: 大数乘法速度过慢，求助？