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