/******
I overlooked the possibility of the size of a being increased
when we normalize b. So I increased n by 1 in the following.
Thnaks to Danita, who reported this bug.
Tad 

---------------------------------------------------------------------
********/
/*
typedef *int multiple_prec;
multiple_prec b,c,temp;
*/
int b[1000],c[1000],temp[1000];
int a[1000];
char s[1000],t[1000];
int i,j,k,m,n,n1,flag,count,r;  // r is radix
char ch;

void multiply(int a[], int b[], int c[])
/* This is to multiply radix-r multiple precision numbers
a and b, and store the result in c */
{
int i,j;
  for (i=0; i<=2*n-1;i++) c[i]=0;
  for (i=0; i<=n-1; i++) {  
    for (j=0; j<= n-1; j++) {
      c[i+j+1]=c[i+j+1] + (c[i+j]+a[i]*b[j]) / r;
      c[i+j]=(c[i+j] + a[i]*b[j]) % r;
    };
  };
}
void divide(int a[], int b[], int c[], int n, int m)
/* This is to divide radix-r multiple precision numbers.
  a is divided by b and the quotient is stored in c. 
  The remainder is in a */
{
int i,j,q,x;
int a1[100];
  while (b[m-1]==0)  m=m-1;
  a[n]=0;
  n=n+1; /* inserted 14 Aug. 2001 */
// The following while loop normalizes b by multiplying it by 2
// We need to multiply a as well to have correct quotient
// At the end a is not the correct remainder due to normalization
  while (b[m-1]<(r / 2)) {
    for(i=0;i<=m-1;i++)  b[i]=2*b[i];
    for(i=0;i<=m-1;i++) { 
      b[i+1]=b[i+1]+b[i] / r;
      b[i]=b[i] % r; 
    }
    for(j=0;j<=n-1;j++)  a[j]=2*a[j];
    for(j=0;j<=n-1;j++) {
      a[j+1]=a[j+1]+a[j] / r;
      a[j]=a[j] % r; 
    }
  }
  for(j=n-m-1;j>=0;j--) {
    x=r*a[j+m]+a[j+m-1];   //     when a1[j+i] is negative, d = -a1[j+i] deficit  
    a[j+m-1]=x;            //     ..-d....-2r...-r....0....r.......
    a[j+m]=0;              //     |  | |    |    |    |    |
    q=x/b[m-1] + 1; //Guess q
    do{
      for(i=m-1;i>=0;i--)  a1[j+i]=a[j+i];
      /*  if q is too large, decrease it by 1  */
      q=q-1;
      count=count+1;
      for(i=m-1;i>=0;i--)  a1[j+i]=a1[j+i]-q*b[i];
      for(i=0;i<=m-2;i++){ // Try to subtract q*b from a
        if(a1[j+i]<0){
          a1[j+i+1]=a1[j+i+1]-(r-1-a1[i+j])/r; //borrow from left
          a1[j+i]=a1[j+i]+((r-1-a1[i+j])/r)*r; //remaining at i+j
        }
      } // for i
    } while(a1[j+m-1]<0);
    c[j]=q;
    for(i=m-1;i>=0;i--)a[j+i]=a1[j+i];
  } // for j
}
main(){
  printf("give n, r ");
  scanf("%d %d", &n, &r);
  getchar();
  count=0;
  n1=n;
  printf("n= %d \n",n);
  for(i=0;i<=n-1;i++){
    scanf("%c", &s[i]); 
    // This is a conversion table : character to number
    switch( s[i]){ 
      case ' ': a[i]=0; break;
      case 'a': a[i]=1; break;
      case 'b': a[i]=2; break;
      case 'c': a[i]=3; break;
      case 'd': a[i]=4; break;
      case 'e': a[i]=5; break;
      case 'f': a[i]=6; break;
      case 'g': a[i]=7; break;
      case 'h': a[i]=8; break;
      case 'i': a[i]=9; break;
      case 'j': a[i]=10; break;
      case 'k': a[i]=11; break;
      case 'l': a[i]=12; break;
      case 'm': a[i]=13; break;
      case 'n': a[i]=14; break;
      case 'o': a[i]=15; break;
      case 'p': a[i]=16; break;
      case 'q': a[i]=17; break;
      case 'r': a[i]=18; break;
      case 's': a[i]=19; break;
      case 't': a[i]=20; break;
      case 'u': a[i]=21; break;
      case 'v': a[i]=22; break;
      case 'w': a[i]=23; break;
      case 'x': a[i]=24; break;
      case 'y': a[i]=25; break;
      case 'z': a[i]=26; break;
    }
  }
  getchar();
  n=n1;
  printf("s= ");
  for(i=0;i<=n-1;i++) printf("%c",s[i]); getchar();
  printf("a= ");
  for(i=0;i<=n-1;i++)printf("%d ", a[i]); getchar();
  for(i=0;i<=n-1;i++){
    // This is a conversion table : number to character
    switch (a[i]) {
      case 0: t[i]=' '; break;
      case 1: t[i]='a'; break;
      case 2: t[i]='b'; break;
      case 3: t[i]='c'; break;
      case 4: t[i]='d'; break;
      case 5: t[i]='e'; break;
      case 6: t[i]='f'; break;
      case 7: t[i]='g'; break;
      case 8: t[i]='h'; break;
      case 9: t[i]='i'; break;
      case 10: t[i]='j'; break;
      case 11: t[i]='k'; break;
      case 12: t[i]='l'; break;
      case 13: t[i]='m'; break;
      case 14: t[i]='n'; break;
      case 15: t[i]='o'; break;
      case 16: t[i]='p'; break;
      case 17: t[i]='q'; break;
      case 18: t[i]='r'; break;
      case 19: t[i]='s'; break;
      case 20: t[i]='t'; break;
      case 21: t[i]='u'; break;
      case 22: t[i]='v'; break;
      case 23: t[i]='w'; break;
      case 24: t[i]='x'; break;
      case 25: t[i]='y'; break;
      case 26: t[i]='z'; break;
    }
  }
  printf("t= ");
  for(i=0;i<=n-1;i++) printf("%c", t[i]);
  printf("\n");
  multiply(a,a,b); // b=a*a
  printf("product ");
  for(i=2*n-1;i>=0;i--) printf("%d ", b[i]);
  printf("\n");
  printf("divisor  ");
  for(i=n-1;i>=0;i--)printf("%d  ",a[i]); printf("\n");
  divide(b,a,c,2*n,n); // c=b/a
  printf("quotient ");
  for(i=n-1;i>=0;i--)printf("%d ", c[i]);
  getchar();
  printf("count= %d ",count);
  getchar();
}