大数乘法。大数运算。“无限大数字”乘法。大数乘法两种方法对比

最近在看笔试题,得知大数运算是个经常考的题目。所以有兴趣试了试。

一开始按照笔算方法自己写了个,但是时间复杂度是o(n3)。

参考了网上的算法之后,修改了自己的算法,时间复杂度变成o(n2)。

下面的测试结果中,两个2000位的数字(阿拉伯数字的位数)相乘,耗时90多毫秒。

200位,1毫秒。可以看到,复杂度的确是N的平方级别。

自己写的笨办法,每次累加之后都要判断是否有进位。但是安全。

网上有个高效的算法,使用int存储临时结果,不用每次累加后都判断一次进位。等

所有的累加都完成之后再判断,所以时间复杂度降低了一个数量级。

但是这样也有个坏处,就是int早晚有溢出的时候,当整数的位数足够多,

也就是达到了2的29、30、31、32次方位(当然这种情况基本没可能发生),这种方法的运算结果就是错误的了。

 

 下面是算法对应的函数。

[cpp] 
view plain
copy

  1. char* BigIntMultiply ( const char * const a, const char * const b , charconst lresult)  
  2. {  
  3.     int i,j;  
  4.     int la = strlen(a);  
  5.     int lb = strlen(b);  
  6.     int rlen = la+lb;  
  7.     int* r = (int*)calloc( rlen, sizeof(int) );  
  8.   
  9.     for(i = 0;i < lb; i++)  
  10.         for(j = 0; j < la; j++)  
  11.             r[rlen – 1 – i – j] += (b[lb – i – 1] – ‘0’) * (a[la – j – 1] – ‘0’);  
  12.   
  13.     //then is there carry on current number  
  14.     for(j = rlen – 1; j >= 1; j–)  
  15.         if(r[j] > 9)  
  16.         {  
  17.             r[j-1] += r[j] / 10;  
  18.             r[j] %= 10;  
  19.         }  
  20.     //find first none_zero_index  
  21.     for(i = 0; 0 == r[i]; i++){}  
  22.           
  23.     //mem cpy  
  24.     for(j=0; i< rlen; i++,j++)  
  25.         lresult[j] = r[i]+‘0’;  
  26.     lresult[j]=‘\0’;  
  27.   
  28.     free(r);  
  29.     return lresult;  
  30. }  

 

 

 

下面的代码在Visual Studio 2008里面编译运行,没有问题。 Linux上没有 SYSTEMTIME,

没有atoi,itoa,GetLocalTime。所以要在Linux运行,得相应的修改一下。

[cpp] 
view plain
copy

  1. #include <iostream>  
  2. #include <assert.h>  
  3. #include <stdio.h>  
  4. #include <time.h>  
  5. #include <windows.h>  
  6. #include <malloc.h>  
  7.   
  8.   
  9. using namespace std;  
  10.   
  11. const int MAX = 2001;  
  12.   
  13. char num1[MAX];  
  14. char num2[MAX];  
  15. char result[2*MAX];  
  16.   
  17.   
  18. void  SafeGetNumFromStr ( char* num, char* str);  
  19. char* BigIntMultiply ( const char * const a, const char * const b , charconst lresult);  
  20. void  multiply( const char *a, const char *b);  
  21.   
  22. int main(int argc, char *argv[])  
  23. {  
  24.     //test speed  
  25.     cout<<“\n\nspeed test… Number of digits is : “<<MAX-1<<“\n”;  
  26.     int i;  
  27.     const int TEST_TIME = 20;  
  28.     srand((unsigned)time(NULL));  
  29.     for(i = 0;i<MAX;i++)  
  30.     {  
  31.         num1[i] = 0;  
  32.         num2[i] = 0;  
  33.     }  
  34.     //create data with random  
  35.     for(i = 0; i< MAX – 1; i++)  
  36.     {  
  37.         num1[i] = rand()%10 + ‘0’;  
  38.         num2[i] = rand()%10 + ‘0’;  
  39.     }  
  40.   
  41.     SYSTEMTIME wtm;  
  42.     GetLocalTime(&wtm);  
  43.     long long time_start = wtm.wMilliseconds + wtm.wSecond * 1000;  
  44.     cout<<num1<<endl;  
  45.     cout<<“*\n”;  
  46.     cout<<num2<<endl;  
  47.     for(i = 0; i<TEST_TIME; i++)  
  48.     {  
  49.         BigIntMultiply(num1,num2,result);  
  50.     }  
  51.     GetLocalTime(&wtm);  
  52.     cout<<“Result is:\n”;  
  53.     cout<<result<<endl;  
  54.     double tmv = (double)(wtm.wMilliseconds + wtm.wSecond * 1000 – time_start);  
  55.     cout<<“Test Over. “<<TEST_TIME<<” loops use time: “<<tmv<<” ms\n”;  
  56.     cout<<”     Each One Time Use: “<<tmv/(double)TEST_TIME<<” ms\n\n\n”;  
  57.       
  58.   
  59.   
  60.     //test validation  
  61.     cout<<“Validation work…\n”;  
  62.     long long  testNum1;  
  63.     long long  testNum2;  
  64.     int testI;  
  65.     for(testNum1 = 0;testNum1<1000000000000000;testNum1 = (testNum1+1)*181+1)  
  66.         for(testI= 0;testI<200; testI++)  
  67.         {  
  68.             char a[2*MAX];  
  69.             char b[2*MAX];  
  70.             testNum2 = (testNum1+testI)<0?0:testNum1+testI;  
  71.             for(i = 0;i<MAX;i++)  
  72.             {  
  73.                 num1[i] = 0;  
  74.                 num2[i] = 0;  
  75.             }  
  76.             itoa(testNum1,a,10);  
  77.             itoa(testNum2,b,10);  
  78.             SafeGetNumFromStr(num1,a);  
  79.             SafeGetNumFromStr(num2,b);  
  80.             BigIntMultiply(num1,num2,result);  
  81.   
  82.             if(8 == testNum2%10)  
  83.                 if(testNum1*testNum2 == atoi(result))  
  84.                     cout<<testNum1<<” * “<<testNum2<<”  ==  “<<testNum1*testNum2<<”    Correct!\n”;  
  85.                 else  
  86.                     cout<<testNum1<<” * “<<testNum2<<”  Result:”<<result<<“\n”;  
  87.         }  
  88.       
  89.       
  90.       
  91.   
  92.     //free test  
  93.     cout<<“Now ….. Free Test!\n”;  
  94.   
  95.     while(1)  
  96.     {  
  97.         char a[2*MAX];  
  98.         char b[2*MAX];  
  99.         cout<<“\n\ninput long integer for A”<<endl;  
  100.         cin>>a;  
  101.         cout<<“input long integer for B”<<endl;  
  102.         cin>>b;  
  103.   
  104.         //get data  
  105.         SafeGetNumFromStr(num1,a);  
  106.         SafeGetNumFromStr(num2,b);  
  107.         cout<<endl<<endl;  
  108.         cout<<num1;  
  109.         cout<<”  *  “;  
  110.         cout<<num2;  
  111.         cout<<endl;  
  112.         BigIntMultiply(num1,num2,result);  
  113.         cout<<“Result is:”<<endl;  
  114.         cout<<result;  
  115.     }  
  116.   
  117.     system(“pause”);  
  118.     return 0;  
  119. }  
  120.   
  121.   
  122.   
  123. void SafeGetNumFromStr( char* num, char* str)  
  124. {  
  125.     memset(num,0,sizeof(num[0])*MAX);  
  126.     int i;  
  127.     int index = 0;  
  128.     for(i=0;i<2*MAX && index < MAX;i++)  
  129.     {  
  130.         if(str[i] <= ‘9’ && str[i] >=‘0’)  
  131.             num[index++] = str[i];  
  132.         if(‘\0’==str[i])  
  133.             break;  
  134.     }  
  135.     assert( 0 != index );  
  136. }  
  137.   
  138.   
  139.   
  140. char* BigIntMultiply ( const char * const a, const char * const b , charconst lresult)  
  141. {  
  142.     int i,j;  
  143.     int la = strlen(a);  
  144.     int lb = strlen(b);  
  145.     int rlen = la+lb;  
  146.     int* r = (int*)calloc( rlen, sizeof(int) );  
  147.   
  148.     for(i = 0;i < lb; i++)  
  149.         for(j = 0; j < la; j++)  
  150.             r[rlen – 1 – i – j] += (b[lb – i – 1] – ‘0’) * (a[la – j – 1] – ‘0’);  
  151.   
  152.     //then is there carry on current number  
  153.     for(j = rlen – 1; j >= 1; j–)  
  154.         if(r[j] > 9)  
  155.         {  
  156.             r[j-1] += r[j] / 10;  
  157.             r[j] %= 10;  
  158.         }  
  159.     //find first none_zero_index  
  160.     for(i = 0; 0 == r[i]; i++){}  
  161.           
  162.     //mem cpy  
  163.     for(j=0; i< rlen; i++,j++)  
  164.         lresult[j] = r[i]+‘0’;  
  165.     lresult[j]=‘\0’;  
  166.   
  167.     free(r);  
  168.     return lresult;  
  169. }  

 

 

 《大数乘法。大数运算。“无限大数字”乘法。大数乘法两种方法对比》

 

《大数乘法。大数运算。“无限大数字”乘法。大数乘法两种方法对比》

 

《大数乘法。大数运算。“无限大数字”乘法。大数乘法两种方法对比》

    原文作者:雪天飞山狐狸
    原文地址: https://blog.csdn.net/gws1229/article/details/8185194
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞