/*  俄罗斯式算法求大数乘          */
/* 原理:   举例 ( 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;
}