Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Big Number Subtraction in C

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.

like image 898
Ian Elliott Avatar asked Aug 22 '09 20:08

Ian Elliott


1 Answers

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?

like image 167
VoteyDisciple Avatar answered Sep 20 '22 07:09

VoteyDisciple