/**** Sample solution of Lab Test 1 ****/
/**** Prepared by: AD               ****/

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

/* Maximum space to store a big int is 100 plus one for null termination
   plus one for carry from sum */
#define ARRSIZE 102

/* I use dynamic arrays for storing big integers */
typedef char *bigint;

int cmpBigInt ( bigint m, bigint n )
{
   int mlen, nlen;

   /* compute the lengths of m and n */
   mlen = strlen(m);
   nlen = strlen(n);

   /* if one length is larger than the other, then the decision is clear */
   if (mlen > nlen) return 1;
   if (mlen < nlen) return -1;

   /* if the lengths are equal, make a lexicographic comparison */
   return strcmp(m,n);
}

/* NOTE: I do not pad the shorter operand by leading zero digits */
void addBigInt ( bigint m, bigint n )
{
   int mlen, nlen, sumlen, i, j, k;
   bigint sum;
   char carry;

   /* compute the length of the operands */
   mlen = strlen(m);
   nlen = strlen(n);

   /* initially set the length of the sum to the length of the longer operand */
   sumlen = (mlen >= nlen) ? mlen : nlen;

   /* index i is for reading from m, j for reading from n */
   i = mlen - 1; j = nlen - 1;

   /* index k is for writing to sum */
   sum = (bigint)malloc(ARRSIZE * sizeof(char));
   k = sumlen;         /* one more cell for possible output carry */
   sum[k + 1] = '\0';  /* terminate output by the null character */

   /* input carry is zero */
   carry = 0;

   /* the sum loop */
   while (1) {
      if (i < 0) {          /* all digits of m processed */
         if (j < 0) break;  /* both operands are exhausted */

         /* only n has unprocessed digits */
          sum[k] = (n[j] - '0');
         --j;
      } else {              /* m has unprocessed digits */
         if (j < 0) {       /* only m has unprocessed digits */
            sum[k] = (m[i] - '0');
         } else {           /* both m and n have unprocessed digits */
            sum[k] = (m[i] - '0') + (n[j] - '0');
            --j;
         }
         --i;
      }

      /* add input carry */
      sum[k] += carry;

      /* check for output carry */
      if (sum[k] >= 10) { sum[k] -= 10; carry = 1; } else carry = 0;

      /* convert digit value to character */
      sum[k] += '0';

      --k;
   }

   /* if there is an output carry */
   if (carry) *sum = '1';

   /* print the sum */
   printf("m + n = %s\n", (carry)? sum : sum + 1);

   free(sum);
}

int main ()
{
   bigint m, n;
   int cmpres;

   /* Input the operands */
   m = (bigint)malloc(ARRSIZE * sizeof(char)); printf("m     = "); scanf("%s",m);
   n = (bigint)malloc(ARRSIZE * sizeof(char)); printf("n     = "); scanf("%s",n);

   /* Compare the operands */
   cmpres = cmpBigInt(m,n);
   if (!cmpres) printf("m = n\n");
   else printf("m %c n\n", (cmpres > 0) ? '>' : '<');

   /* Add the operands */
   addBigInt(m,n);
}

/**** End of lt1.c ****/