/* A structure type for storing 500-digit positive numbers, functions to
   add and multiply them, plus a main program to allow the user to enter,
   add or multiply numbers.
*/

/* The structure must store the digits.  It would be useful to also store
   the number of 'actual' (nonzero) digits.

   NB: Computer arithmetic theory allows better solutions than that
   presented here; this solution is a simple-minded implementation of the
   manual addition and multiplication methods.
*/

#define DIGS (500)
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int num_digits;     /* How many nonzero digits. */
    char digits[DIGS];  /* The digits (digits[0] is the units digit). */
    /* Note: all DIGS digits must be correct, even the zero ones. */
} bignum;

/* Note: passing and returning bignums as in the functions below is
   inefficient, as they are such large data structures.  This can be
   overcome at the cost of clumsier programming, or by using pointers,
   which have not been covered yet.
*/

bignum bigadd(bignum a, bignum b) {
    /* Returns the sum of two bignums. */
    bignum total;      /* for the sum */
    int place;         /* a position in the number (0==units etc) */
    int carry;         /* the carry. */
    int numdigits;     /* The number of digits in the total. */
    int digitsum;      /* The sum of any two digits */

    /* Now add corresponding digits from the units upwards (i.e. from
       right to left in a written number), at each step computing
       the sum of the two digits plus any carry from the previous
       position.  This digitsum is itself split into a digit and a
       new carry with the division and remainder operators.  E.g. to
       add 19 to 27, first add 9 + 7 + no carry, giving 16.  The 6
       is the units digit in the total, the 1 (i.e. 16 / 10) is the
       carry into the tens position.  The tens digit is 1 + 2 + 1 carry,
       or 4.  This 4 is the tens digit in the total, with no carry.
       As a by-product, the number of digits must also be computed.
    */

    numdigits = 1;      /* Since all numbers have at least one digit */
    for (carry = place = 0; place < DIGS; place++) {
        /* Invariant: digitsum == sum of digits [0]..[place-1]; carry ==
           carry from digit[place-1]; numdigits == no. of meaningful digits
           so far (1 at the start).
        */
        digitsum = a.digits[place] + b.digits[place] + carry;
        total.digits[place] = digitsum % 10;
        if (total.digits[place] != 0) {
            numdigits = place + 1;
        }
        carry = digitsum / 10;
    }
    total.num_digits = numdigits;

    /* Check for error: a carry from the final place means that the
       sum is too large.  In this program, we print a message and stop.
    */
    if (carry != 0) {
        printf("Error: Overflow in bignum addition.\n");
        exit(1);
    }

    return total;
}

bignum shiftleft (bignum b);
    /* Shifts the digits of b left one place */
bignum timesdigit (bignum b, int digit);
    /* Multiplies b by the single-digit number, digit. */

bignum bigmul(bignum a, bignum b) {
    /* Returns the product of two bignums. */
    bignum product;      /* for the product */
    bignum partial;      /* for partial products */
    int place;           /* which place in b is multiplying a */

    /* Method: The first number is multiplied by each digit of the second
       number in turn.  All digits in the second number except the units
       digit require that the first number be shifted left the appropriate
       number of places.  These separate products are added to give the
       final product.  This is exactly the same as the well-known manual
       method.  E.g.: 13*23 is 3 times 13, plus 2 times 130.
    */

    /* Multiply a by the units digit of b: */
    product = timesdigit(a, b.digits[0]);

    for (place = 1; place < b.num_digits; place++) {
        /* Invariant: product == the sum of the products of a with digits
           [0]..[place-1] of b.
        */

        /* Multiply a (suitably shifted) by the next digit of b: */
        a = shiftleft(a);
        partial = timesdigit(a, b.digits[place]);

        /* Add the above partial product into the full product: */
        product = bigadd(product, partial);
    }

    return product;
}


bignum shiftleft (bignum b) {
    /* Shifts the digits of b left [i.e. to higher array subscripts] one
       place; this is the same as multiplying b by ten.
    */
    bignum shift;       /* for the shifted number */
    int place;

    /* Check for overflow: */
    if (b.num_digits == DIGS) {   /* number about to become too big. */
        printf("Error: Overflow in bignum multiplication shifting.\n");
        exit(1);
    }

    /* Shift digits upward, starting at the top and moving down: */
    for (place = DIGS - 1; place > 0; place--) {
        shift.digits[place] = b.digits[place - 1];
    }

    shift.digits[0] = 0;                  /* Move zero into units digit. */
    shift.num_digits = b.num_digits + 1;  /* Record number of digits */

    return shift;
}

bignum timesdigit (bignum b, int digit) {
    /* Multiplies b by the single-digit number, digit. */

    bignum prod;       /* for the product */
    int place;         /* a position in the number (0==units etc) */
    int carry;         /* the carry. */
    int numdigits;     /* The number of digits in the product. */
    int digitprod;     /* The product of two particular digits. */

    /* Method is similar to bigadd: digits in b from the units upwards
       are at each step multiplied by the digit.  Any carry from the
       previous position is then added.  This digitsum is split into a
       digit and a new carry with the division and remainder operators.
       As a by-product, the number of digits must also be computed.
    */

    numdigits = 1;      /* Since all numbers have at least one digit */
    for (carry = place = 0; place < DIGS; place++) {
        digitprod = b.digits[place] * digit + carry;
        prod.digits[place] = digitprod % 10;
        if (prod.digits[place] != 0) {
            numdigits = place + 1;
        }
        carry = digitprod / 10;
    }
    prod.num_digits = numdigits;

    /* Check for error: a carry from the final place means that the
       product is too large.  In this program, we print a message and stop.
    */
    if (carry != 0) {
        printf("Error: Overflow in bignum digit multiplication.\n");
        exit(1);
    }

    return prod;
}

/******************************************************************

Now for input and output routines.

*/

#include <ctype.h>

bignum getbignum (void) {
    /* Skips spaces, then inputs as many digits as possible, converting
       each from an ASCII character to a numeric digit, then stores the
       digits in a bignum.  Also reads and discards the following
       character.
    */

    bignum big;
    int place, ch, i;

    do {                        /* Skip whitespace in input. */
        ch = getchar();
    } while (isspace(ch));      /* using isspace std. library function */

    if (! isdigit(ch)) {
        printf("Error: non-digit in input.\n");
        exit(1);
    }

    place = DIGS - 1;           /* the leftmost (most significant) digit */
    /* Now get digits until a nondigit is found. */
    do {
        if (place < 0) {        /* fallen off rhs of bignum digits array? */
            printf("Error: too many digits in input.\n");
            exit(1);
        }

        /* Convert ASCII digit to a mathematical digit by subtracting the
           code of the '0' character.
        */
        big.digits[place] = ch - '0';

        place--;                /* Get ready for the next digit */
    } while (ch = getchar(), isdigit(ch));

    /* At this point, the digits are loaded, but not necessarily in the
       correct places.  They were loaded into the highest places of big,
       and therefore occupy big.digits[DIGS-1] down to big.digits[place+1].
       This is only correct if the number has exactly DIGS digits, and
       therefore fills the number.  Now shift them into the right places.
    */
    place++;            /* Now indicates the place of the units digit */
    big.num_digits = DIGS - place;  /* Calculate no. of digits. */
    for (i = 0; i < big.num_digits; i++) {
        big.digits[i] = big.digits[i + place];  /* Shift the digit. */
    }

    /* Now fill the empty digit places with zeroes.  i now points at the
       first of these empty places.
    */
    for (  ; i < DIGS; i++) {
        big.digits[i] = 0;
    }

    return big;
}

void putbignum (bignum big) {
    /* Writes a bignum to the screen. */
    int i;
    /* Write digits, starting with the most significant. */
    for (i=big.num_digits - 1; i >= 0; i--) {
        printf("%d", big.digits[i]);
    }
}


main () {
    bignum a, b, c;
    int ch;
    printf(
        "Big number calculator.  Enter a sign ('+' or '*') and then two\n"
        "big numbers.  The appropriate result (sum or product) will be\n"
        "displayed.  Repeat as required, and enter # when finished.\n");

    while (ch = getchar(), ch == '+' || ch == '*') {
        a = getbignum();
        b = getbignum();

        switch (ch) {
        case '+':
            c = bigadd(a, b);
            break;
        case '*':
            c = bigmul(a, b);
            break;
        }

        putbignum(c);printf("\n");
    }

    if (ch != '#') {
        printf("Error: illegal command.\n");
        exit(1);
    }
    exit(0);
}