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

落叶

我的电脑配置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

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

liangbch

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

liangbch

这里给出我的测试程序。

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <windows.h>
   
5. #include "gmp.h"
   
6. 
   
7. static LARGE_INTEGER freq;
   
8. 
   
9. static BOOL initFreq()
   
10. {
    
11.         BOOL ret;
    
12.         if ( !QueryPerformanceFrequency( &freq) )
    
13.         {        ret=FALSE;        }
    
14.         else
    
15.         {        ret=TRUE;        }
    
16.         return ret;
    
17. }
    
18. 
    
19. double currTime() //使用高精度计时器
    
20. {       
    
21.         LARGE_INTEGER performanceCount;
    
22.         BOOL result;
    
23.         double time=0.0;
    
24.         BOOL bRet=TRUE;
    
25. 
    
26.         if (freq.QuadPart==0)
    
27.         {
    
28.                 bRet=initFreq();
    
29.         }
    
30.        
    
31.         if (bRet)
    
32.         {
    
33.                 result=QueryPerformanceCounter(  &performanceCount );
    
34.                 time= performanceCount.HighPart * 4294967296.0 + performanceCount.LowPart;
    
35.                 time=time / (   freq.HighPart * 4294967296.0 + freq.LowPart);
    
36.         }
    
37.         return time;
    
38. }
    
39. 
    
40. 
    
41. void generate_an_integer(int dig_len, mpz_t x)
    
42. {
    
43.         int i;
    
44.         char c;
    
45.         char *pBuff=NULL;
    
46. 
    
47.         pBuff=(char *) malloc(dig_len+8);
    
48.         if ( pBuff==NULL)
    
49.         {
    
50.                 printf("Alloc memory failed on %s:%d\n",__FILE__,__LINE__);
    
51.                 return;
    
52.         }
    
53.        
    
54.         srand(GetTickCount());
    
55.         while (1)
    
56.         {
    
57.                 c=rand() % 10;
    
58.                 if (c >0)
    
59.                 {
    
60.                         pBuff[0]= c + 0x30;
    
61.                         break;
    
62.                 }
    
63.         }
    
64.        
    
65.         for (i=1;i<dig_len;i++)
    
66.                 pBuff[i]=(rand() %  10)+0x30;
    
67.         pBuff[i]=0;
    
68.        
    
69.         mpz_set_str (x,pBuff,10);
    
70. 
    
71.         if ( pBuff!=NULL)
    
72.         {
    
73.                 free(pBuff); pBuff=NULL;
    
74.         }
    
75. }
    
76. 
    
77. void test_mpz_mul(int dig_len)
    
78. {
    
79.         int j,test_count;
    
80.        
    
81.         mpz_t a;
    
82.         mpz_t b;
    
83.         mpz_t prod;
    
84.         mpz_t s;
    
85. 
    
86.         int len;
    
87.         size_t r_len;
    
88. 
    
89.         double startTime;
    
90.         double testTime;
    
91.         //---------------------
    
92.        
    
93.         test_count=1000;
    
94.         r_len = dig_len *10/3+32;
    
95. 
    
96.         mpz_init(a);
    
97.         mpz_init(b);
    
98.         mpz_init2(prod,r_len);
    
99.         mpz_init2(s,r_len);
    
100. 
     
101.         generate_an_integer(dig_len,a);
     
102.         generate_an_integer(dig_len,b);
     
103.         mpz_set_ui(s,0);
     
104. 
     
105.         //--------------------------------------
     
106.         startTime=currTime();
     
107.         for (j=0;j<test_count;j++)
     
108.         {
     
109.                 mpz_mul (prod,a,b);
     
110.                 mpz_add(s,s,prod);
     
111.         }
     
112.         testTime=currTime()-startTime;
     
113.         testTime =  testTime * 1000 / (test_count); //get unit time by ms
     
114.        
     
115.         len=mpz_sizeinbase(s,10);
     
116.         printf("the result contain about %d digital\n", len);
     
117.         printf("It take %.4lf ms\n", testTime);
     
118.        
     
119.         mpz_clear(a);
     
120.         mpz_clear(b);
     
121.         mpz_clear(prod);
     
122.         mpz_clear(s);
     
123. }
     
124. 
     

复制代码

落叶

liangbch（良师益友）！浪费你N多时间给了这么详细的解答，
忙了半天，才把你的程序运行成功，对这个函数（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

落叶

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

liangbch

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

落叶

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

liangbch

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

liangbch

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