Big Number Subtraction in C

Question

I just finished my exam in an introductory C course about 20 minutes ago. The first question on the exam caught me somewhat off guard, and involved finding the difference two large numbers.

The goal was to take two structures (N1 and N2) by value, and store the difference in a structure passed by reference (N3). We were allowed to assume N3 was initiated with all '0's. The MAX size can be anything, so the solution still has to work if the numbers are over 100 digits.

Here's the base code (original may be slightly different, this is from memory)

#include <stdio.h>
#include <stdlib.h>
/* MAX can be any length, 10, 50, 100, etc */
#define MAX 10

struct bignum
{
    char digit[MAX];
    char decimaldigit[MAX/2];
};
typedef struct bignum bigNum;
void difference(bigNum, bigNum, bigNum *);

/*
    Original values in N1 and N2

    N1.digit = { '0', '0', '0', '5', '4', '8', '2', '0', '9', '0'};
    N1.decimaldigit { '0', '0', '0', '4', '9' };

    N2.digit = { '0', '0', '0', '4', '8', '1', '3', '1', '4', '5'};
    N2.decimaldigit { '8', '0', '1', '2', '0' };
*/

/*
    Result would be:
    N3.digit = { '0', '0', '0', '0', '6', '6', '8', '9', '4', '4'}
    N3.decimaldigit { '1', '9', '9', '2', '9' }
*/

The problem isn't so much in finding a solution to this problem, but that only about ~20 lines were provided for the complete answer. My method for solving involved subtracting the digits one at a time after converting to integers, and then making appropriate carries if the result was negative. This took substantially more space than what was provided.

Based on the small amount of marks and the space provided for this question, I'm lead to believe that there's a fairly trivial solution that I'm not seeing. What is it? I have now finished the course but this question is still bothering me!

A complete solution isn't required, just the inner workings of the function difference.

No bitwise operators are to be used, just in case.

Answer 1

The BigNumber problem in most Computer Science classes is designed to make you have to do the arithmetic "by hand" precisely as you describe: convert each character to an integer, subtract, and borrow where appropriate.

Your plan attack, just as you've described it, should be only a few lines. In pseudocode, something like this:

for each character (right to left):
    difference = N1.digit[i] - N2.digit[i];
    if (difference < 0)
        N1.digit[i - 1]--;
        difference += 10;
    N3.digit[i] = difference;

(Plus a little extra hassle to apply the same logic to the decimal digits too.)

It sounds like you had the right idea, and perhaps just over-thought the implementation?

Answer 2

This should work if N1 >= N2. This also assumes that the arrays are laid out like dn...d2d1d0.e0e1...em.

char digchr(int); // Converts a single-digit integer into a character.

void difference(bigNum N1, bigNum N2, bigNum *N3) {
    int carry = 0;

    for (int i = MAX / 2 - 1; i >= 0; i--) {
        int diff = N1.decimalDigits[i] - N2.decimalDigits[i] - carry;
        if (diff < 0) { 
            diff += 10;
            carry = 1;
        } else {
            carry = 0;
        }

        N3->decimalDigits[i] = digchr(diff);
    }

    for (int i = 0; i < MAX; i++) {
        int diff = N1.digits[i] - N2.digits[i] - carry;
        if (diff < 0) {
           diff += 10;
           carry = 1;
        } else {
            carry = 0;
        }

        N3->digits[i] = digchr(diff);
    }
}

Answer 3

Dear professor, subtraction should be defined in terms of addition. I've overloaded the unary "-" operator and defined the bignum addition routine elsewhere. I'm using 9's complement to simplify/speed up the addition (no pesky carry required!) with a table based answer lookup (why calculate the sums when there are only 10 of them?). The bigNum subtraction routine (to your specs) follows:

void bigDifference(bigNum N1, bigNum N2, bigNum *N3) {
    bigSum(N1, -N2, N3);
}