Вычитание большого числа в C

Question

Я только что закончил свой экзамен на вводном курсе C около 20 минут назад. Первый вопрос на экзамене застал меня врасплох и заключался в том, чтобы найти разницу в двух больших числах.

Цель состояла в том, чтобы взять две структуры (N1 и N2) по значению и сохранить разницу в структуре, переданной по ссылке (N3). Нам разрешили предположить, что N3 был инициирован со всеми нулями. Максимальный размер может быть любым, поэтому решение все равно должно работать, если числа превышают 100 цифр.

Вот базовый код (оригинал может немного отличаться, это из памяти)

#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' }
*/

Проблема не в том, чтобы найти решение этой проблемы, а в том, что для полного ответа было предоставлено всего около 20 строк. Мой метод решения состоял в том, чтобы вычитать цифры по одному после преобразования в целые числа, а затем делать соответствующие переносы, если результат был отрицательным. Это заняло значительно больше места, чем было предоставлено.

Исходя из небольшого количества оценок и места, предоставленного для этого вопроса, я считаю, что есть довольно тривиальное решение, которое я не вижу. Что это? Я уже закончил курс, но этот вопрос все еще беспокоит меня!

Полное решение не требуется, только внутренняя работа функции difference,

Никакие побитовые операторы не должны использоваться, на всякий случай.

Answer 1

Это должно работать, если N1 >= N2, Это также предполагает, что массивы расположены как 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 2

Задача BigNumber в большинстве классов по информатике разработана таким образом, чтобы вам приходилось выполнять арифметику "вручную" в точности так, как вы ее описываете: конвертировать каждый символ в целое число, вычитать и заимствовать, где это необходимо.

Ваш план атаки, как вы его описали, должен состоять всего из нескольких строк. В псевдокоде что-то вроде этого:

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;

(Плюс немного больше хлопот, чтобы применить ту же логику и к десятичным цифрам.)

Похоже, у вас была правильная идея, и, возможно, вы просто обдумали реализацию?

Answer 3

Уважаемый профессор, вычитание должно быть определено в терминах сложения. Я перегружал унарный оператор "-" и определил подпрограмму добавления bignum в другом месте. Я использую 9-е дополнение, чтобы упростить / ускорить добавление (не надоедливого переноса!) С помощью поиска ответов на основе таблицы (зачем вычислять суммы, когда их всего 10?). Процедура вычитания bigNum (согласно вашим спецификациям) следующая:

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