/* 俄罗斯式算法求大数乘 */
/* 原理: 举例 ( 9 * 8 ) */
/* (乘数) 9 (被乘数)8 */
/* 4 16 */
/* 2 32 */
/* 1 64 */
/* 将乘数为奇时的被乘数相加 8 + 64 = 72 OK ! */
/* 这钟算法只比传统的好,分治法就比这种要好 */
/* 编译环境: VC ++ 6.0 */
/* Author: 江南孤峰 Time: 2006-10-24 */

#include <stdio.h>
#include <ctype.h>

#define MAX 1000 //存结果的数组大小,乘数较大时需要修改这里
#define MULMAX 100 //存两个乘数的数组大小

void mul(char a[],char b[],int la,int lb);
void divTwo(char a[],int *la);
void add(char a[],char b[],int *la,int *lb);
int input(char a[],char b[],int *la,int *lb);

void mul(char a[],char b[],int length_a,int length_b){
// 求数组 a 与 b 中数相乘的结果
char result[MAX];
int la = length_a,lb = length_b,lr = 0,i = 0;

while(a[0] != '0' || la != 0){
if(a[0] % 2) // 乘数为奇
add(result,b,&lr,&lb);
divTwo(a,&la); // 乘数除 2
add(b,b,&lb,&lb); // 被乘数扩大一倍
}
for(i = lr - 1; i >= 0; i --)
putchar(result[i]);
}

void divTwo(char a[],int *la){
// 数组 a 中的数除 2
int rr,i = *la - 1,t;

if(a[i] == '1')
*la = i;
for(rr = t = 0; i >= 0; i --){
t = rr + a[i] - 48;
if( t >= 2 ){
a[i] = t / 2 + 48;
rr = (t % 2) ? 10 : 0;
}
else{
if(a[i] == '1')
rr = 10;
a[i] = '0';
}
}
}

void add(char a[],char b[],int *la,int *lb){
// 数组 a 与 数组 b的和 存于数组 a 中
int t,rr,n;

for(t = rr = n = 0; n < *la && n < *lb; n ++){
t = rr + a[n] + b[n] - 96;
a[n] = t % 10 + 48;
rr = t / 10;
}
for(; n < *la; n ++){
if( !rr )
break;
t = a[n] + rr;
a[n] = t % 10 + 48;
rr = t / 10;
}
for(; n < *lb; n ++){
t = b[n] + rr - 48;
a[n] = t % 10 + 48;
rr = t / 10;
}
if( rr ){
a[n] = '1';
n ++;
}
*la = n;
}

int input(char a[],char b[],int *la,int *lb){
// 输入两个数字数组
char stack[MULMAX];
int lena,lenb,i;

printf("Input a:");
for(lena = 0;; lena ++){
scanf("%c",&stack[lena]);
if(stack[lena] == '\n')
break;
if(stack[lena] < 48 || stack[lena] > 57) // 含有非数字 不合法
return 0;
}
for(i = 0; i < lena; i ++)
a[i] = stack[lena-i-1];
printf("Input b:");
for(lenb = 0;; lenb ++){
scanf("%c",&stack[lenb]);
if(stack[lenb] == '\n')
break;
if(stack[lenb] < 48 || stack[lenb] > 57)
return 0;
}
if(a[lena-1] == 48 || stack[lenb] == 48)// 首位为 0 不合法
return 0;
for(i = 0; i < lenb; i ++)
b[i] = stack[lenb-i-1];
*la = lena;
*lb = lenb;
return 1;
}

int main(){
char a[MULMAX],b[MULMAX],c;
int lena,lenb;

while( 1 ){
if( input(a,b,&lena,&lenb) )
mul(a,b,lena,lenb);
else{
getchar(); // 接收回车符
printf("Input error !\n");
}
printf("\nContinue(y/n)? :");
c = getchar();
c = tolower(c);
getchar(); // 接收回车符
if(c == 'y')
continue;
else
break;

}
return 0;
}