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

Question

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

Целью было взятие двух структур (N1 и N2) по значению и сохранение разности в структуре, переданной посредством ссылки (N3). Нам разрешили предположить, что N3 был начат со всех «0». Размер MAX может быть любым, поэтому решение по-прежнему должно работать, если цифры более 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 в большинстве классов Computer Science предназначена для того, чтобы заставить вас выполнять арифметику «вручную» точно так же, как вы описываете: конвертировать каждый символ в целое, вычитать и брать там, где это необходимо.

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

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

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

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