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.

Ornie

Could you explain what decimaldigit is supposed to be? Also, 5482090-4813145 is a little bit more than 668944. ;) – Milled

It's numbers with floating point - <digits>.<decimaldigits>, e.g. N1 is like 5482090.00049f. – Bailes

Oh, I see. That also explains the weird off-by-one error. – Milled

Answer 1

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);
    }
}

Sonnysonobuoy

You should probably downcount in the second loop as well. – Milled

This was my original answer, but I couldn't really validate it in a case where N2 > N1. I probably should I just left it as this, looking back :( Oh well. Also, in your if (diff < 0) shouldn't you add an else to revert carry to 0? – Ornie

Oh, and you should add '0' to the result: N3->decimalDigits[i] = diff + '0'; – Milled

@Milled I'm assuming that the arrays are laid out so the decimal digits are on the right, the digits are on the left, and the zero-indices for both meet in the middle. – Sonnysonobuoy

With respect to DRY rule (Don't Repeat Yourself) i would prefer merging digits and decimaldigits into one array, running them through one cycle and then splitting. :) – Bailes

@Milled I just realized that the digits are made up of char arrays. @Trochelminth and @Ian, I fixed the carry bit. – Sonnysonobuoy

Well done, although now I feel like shooting myself in the foot for being so close and giving up. – Ornie

@Andrew, yes the char array caught me off guard until the end as well, but it's not a big deal. – Ornie

Answer 2

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?

Trochelminth

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);
}

Fillbert