# 【原】biginteger。大数乘法。大数运算。“无限大数字”乘法。大数乘法两种方法对比

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

下面是算法对应的函数。

``````char* BigIntMultiply ( const char * const a, const char * const b , char* const lresult)
{
int i,j;
int la = strlen(a);
int lb = strlen(b);
int rlen = la+lb;
int* r = (int*)calloc( rlen, sizeof(int) );

for(i = 0;i < lb; i++)
for(j = 0; j < la; j++)
r[rlen - 1 - i - j] += (b[lb - i - 1] - '0') * (a[la - j - 1] - '0');

//then is there carry on current number
for(j = rlen - 1; j >= 1; j--)
if(r[j] > 9)
{
r[j-1] += r[j] / 10;
r[j] %= 10;
}
//find first none_zero_index
for(i = 0; 0 == r[i]; i++){}

//mem cpy
for(j=0; i< rlen; i++,j++)
lresult[j] = r[i]+'0';
lresult[j]='\0';

free(r);
return lresult;
}
``````

``````#include <iostream>
#include <assert.h>
#include <stdio.h>
#include <time.h>
#include <windows.h>
#include <malloc.h>

using namespace std;

const int MAX = 2001;

char num1[MAX];
char num2[MAX];
char result[2*MAX];

void  SafeGetNumFromStr ( char* num, char* str);
char* BigIntMultiply ( const char * const a, const char * const b , char* const lresult);
void  multiply( const char *a, const char *b);

int main(int argc, char *argv[])
{
//test speed
cout<<"\n\nspeed test... Number of digits is : "<<MAX-1<<"\n";
int i;
const int TEST_TIME = 20;
srand((unsigned)time(NULL));
for(i = 0;i<MAX;i++)
{
num1[i] = 0;
num2[i] = 0;
}
//create data with random
for(i = 0; i< MAX - 1; i++)
{
num1[i] = rand()%10 + '0';
num2[i] = rand()%10 + '0';
}

SYSTEMTIME wtm;
GetLocalTime(&wtm);
long long time_start = wtm.wMilliseconds + wtm.wSecond * 1000;
cout<<num1<<endl;
cout<<"*\n";
cout<<num2<<endl;
for(i = 0; i<TEST_TIME; i++)
{
BigIntMultiply(num1,num2,result);
}
GetLocalTime(&wtm);
cout<<"Result is:\n";
cout<<result<<endl;
double tmv = (double)(wtm.wMilliseconds + wtm.wSecond * 1000 - time_start);
cout<<"Test Over. "<<TEST_TIME<<" loops use time: "<<tmv<<" ms\n";
cout<<"     Each One Time Use: "<<tmv/(double)TEST_TIME<<" ms\n\n\n";

//test validation
cout<<"Validation work...\n";
long long  testNum1;
long long  testNum2;
int testI;
for(testNum1 = 0;testNum1<1000000000000000;testNum1 = (testNum1+1)*181+1)
for(testI= 0;testI<200; testI++)
{
char a[2*MAX];
char b[2*MAX];
testNum2 = (testNum1+testI)<0?0:testNum1+testI;
for(i = 0;i<MAX;i++)
{
num1[i] = 0;
num2[i] = 0;
}
itoa(testNum1,a,10);
itoa(testNum2,b,10);
SafeGetNumFromStr(num1,a);
SafeGetNumFromStr(num2,b);
BigIntMultiply(num1,num2,result);

if(8 == testNum2%10)
if(testNum1*testNum2 == atoi(result))
cout<<testNum1<<" * "<<testNum2<<"  ==  "<<testNum1*testNum2<<"    Correct!\n";
else
cout<<testNum1<<" * "<<testNum2<<"  Result:"<<result<<"\n";
}

//free test
cout<<"Now ..... Free Test!\n";

while(1)
{
char a[2*MAX];
char b[2*MAX];
cout<<"\n\ninput long integer for A"<<endl;
cin>>a;
cout<<"input long integer for B"<<endl;
cin>>b;

//get data
SafeGetNumFromStr(num1,a);
SafeGetNumFromStr(num2,b);
cout<<endl<<endl;
cout<<num1;
cout<<"  *  ";
cout<<num2;
cout<<endl;
BigIntMultiply(num1,num2,result);
cout<<"Result is:"<<endl;
cout<<result;
}

system("pause");
return 0;
}

void SafeGetNumFromStr( char* num, char* str)
{
memset(num,0,sizeof(num[0])*MAX);
int i;
int index = 0;
for(i=0;i<2*MAX && index < MAX;i++)
{
if(str[i] <= '9' && str[i] >='0')
num[index++] = str[i];
if('\0'==str[i])
break;
}
assert( 0 != index );
}

char* BigIntMultiply ( const char * const a, const char * const b , char* const lresult)
{
int i,j;
int la = strlen(a);
int lb = strlen(b);
int rlen = la+lb;
int* r = (int*)calloc( rlen, sizeof(int) );

for(i = 0;i < lb; i++)
for(j = 0; j < la; j++)
r[rlen - 1 - i - j] += (b[lb - i - 1] - '0') * (a[la - j - 1] - '0');

//then is there carry on current number
for(j = rlen - 1; j >= 1; j--)
if(r[j] > 9)
{
r[j-1] += r[j] / 10;
r[j] %= 10;
}
//find first none_zero_index
for(i = 0; 0 == r[i]; i++){}

//mem cpy
for(j=0; i< rlen; i++,j++)
lresult[j] = r[i]+'0';
lresult[j]='\0';

free(r);
return lresult;
}
``````

原文作者：delacrxoix_xu
原文地址: https://blog.csdn.net/delacroix_xu/article/details/6795807
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。