/*** This program pack two ascii characters in a word of
a one-dimensional array. Input the length of a string,
followed by the string.
***/
/*
typedef *int multiple_prec;
multiple_prec b,c,temp;
*/
int b[1000],c[1000],temp[1000];
int a[1000];
char s[1000],t[1000], ch;
int i,j,k,m,n,n1,flag,count,r;
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
  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 ");
  scanf("%d ", &n);
  count=0;
  r=128*128;
  printf("n= %d \n",n);
  for(i=0;i<=n-1;i++){
    scanf("%c", &s[i]); 
  }
  printf("s= ");
  for(i=0;i<=n-1;i++) printf("%c",s[i]); getchar();
  for(i=0;i<=n/2;i++)a[i]=(int)s[2*i+1]*128+(int)s[2*i];
  getchar();
  printf("In a, two characters are packed in one word in the order\n");
  printf("from the key board\n");
  printf("a= ");
  for(i=0;i<=n/2;i++) printf("%d ",a[i]); getchar();
  n=n/2+1;
  printf("\n");
  printf("In the following, multiple precision numbers are given\n");
  printf("in the order where higher radixes are from left end\n");
  multiply(a,a,b);
  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);
  printf("quotient ");
  for(i=n-1;i>=0;i--)printf("%d  ", c[i]);
  getchar();
  printf("count= %d ",count);
  getchar();
}