大整数相乘的C实现

//之前有个测试这个题没做完，现在把它做完，通过这个程序可以对乘法了解更深刻。分析：运用整数乘法，当然进制越高越好，考虑到乘法不要越界，故考虑进制底数N应该满

//足，N^2<2^32次方。所以N最多取四个字符组成的数字。当然我们也可以取LONGLONG的乘法，那么可以取9个字节。

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>

void sub(char* a, char* sub, int pos, int posn)//sub中不包括a[posn]
{
for(int i=0; i<posn-pos; i++)
sub[i] = a[pos + i];
sub[i] = ‘\0‘;
};

int *multi(char *x, char *y, int &sAns){
int sx = strlen(x);
int sy = strlen(y);
int beginX = 0, beginY=0;
if(x[0]==‘-‘) {x[0]=‘0‘; beginX++;}
if(y[0]==‘-‘) {y[0]=‘0‘; beginY++;}
char subx[5],suby[5];//
int i,j,tx,ty;//
sAns = ((sx-1)/4+1 + (sy-1)/4+1); 

int * anss = (int *) malloc(sAns*4);
for (i=0; i<sAns; i++)
anss[i] = 0;
for(i=1; i<=(sx-1)/4+1; i++){
sub(x, subx, sx-((i*4)<(sx-beginX)? (i*4):(sx-beginX)), sx-i*4+4);
tx = atoi(subx);
for(j=1; j<=(sy-1)/4+1; j++){
sub(y,suby, sy-((j*4)<(sy-beginY)? (j*4):(sy-beginY)), sy-j*4+4);
ty = atoi(suby);
anss[sAns - ( i + j) + 1] += tx*ty;
anss[sAns - ( i + j ) ] += anss[sAns - (i+j) +1]/10000;
anss[sAns - ( i + j) + 1] %= 10000;//ensure not cross border
}
}
/*for(j=sAns; j>0; j--){
anss[j-1] += anss[j]/10000;
anss[j] =
}*/
return anss;
};

int main(){
char x[100000],y[100000];//Since sAns is a intager less than 2^32/2, mutipliers‘ places need to be less than 2^29. ie sizeof(x)<0.5 billion bytes(or 　　　　　　　　　　　　　　　　　　　//sizeof(y)<0.5 billion bytes);
while(scanf("%s%s",&x,&y)){
int flag=0;
if(x[0]==‘-‘) flag++;
if(y[0]==‘-‘) flag++;
int n;
int *a= multi(x,y,n);
if(flag%2 && (n>1||a[0]!=0)) printf("-");
char tt[5],t[5];
t[4]=‘\0‘;
int i=0;
while(a[i]==0) i++;
printf("%d", a[i]);
i++;
while(i<n){
if(a[i]<1000) {
itoa(a[i], tt, 10);
int len = strlen(tt);
for(int j=1; j<=len; j++)
t[4-j] = tt[len-j];
while(j<=4) {
t[4-j] = ‘0‘;
j++;
}
printf("%s",t);
}
else{
printf("%d", a[i]);
}
i++;
}
printf("\n");
free(a);
}
getchar();
return 0;
}

大整数相乘的C实现

原文：http://www.cnblogs.com/ele-oy/p/4892267.html