Subtraktion großer Zahlen in C

Question

Ich habe gerade vor 20 Minuten meine Prüfung in einem C-Einführungskurs beendet. Die erste Frage in der Prüfung hat mich etwas überrascht. Es ging darum, die Differenz zweier großer Zahlen zu finden.

Ziel war es, zwei Strukturen (N1 und N2) als Wert zu nehmen und die Differenz in einer als Referenz übergebenen Struktur (N3) zu speichern. Wir durften annehmen, dass N3 mit allen '0's begonnen wurde. Die MAX-Größe kann beliebig sein, so dass die Lösung auch dann noch funktioniert, wenn die Zahlen mehr als 100 Ziffern haben.

Hier ist der Basiscode (das Original kann etwas anders sein, dies ist aus dem Gedächtnis)

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

Das Problem besteht nicht so sehr darin, eine Lösung für dieses Problem zu finden, sondern darin, dass nur etwa 20 Zeilen für die vollständige Antwort zur Verfügung gestellt wurden. Meine Methode zur Lösung bestand darin, die Ziffern nach der Umwandlung in ganze Zahlen einzeln zu subtrahieren und dann entsprechende Überträge vorzunehmen, wenn das Ergebnis negativ war. Dies nahm wesentlich mehr Platz in Anspruch als vorgesehen war.

Angesichts der geringen Anzahl von Punkten und des für diese Frage zur Verfügung stehenden Platzes habe ich den Eindruck, dass es eine ziemlich triviale Lösung gibt, die ich nicht sehe. Wie lautet sie? Ich habe den Kurs jetzt beendet, aber diese Frage beschäftigt mich immer noch!

Eine vollständige Lösung ist nicht erforderlich, sondern nur das Innenleben der Funktion difference .

Es dürfen keine bitweisen Operatoren verwendet werden, nur für den Fall.

Answer 1

Das BigNumber-Problem in den meisten Informatikkursen ist so konzipiert, dass Sie die Arithmetik "von Hand" durchführen müssen, und zwar genau so, wie Sie es beschreiben: jedes Zeichen in eine ganze Zahl umwandeln, subtrahieren und gegebenenfalls ausleihen.

Ihr Angriffsplan, so wie Sie ihn beschrieben haben, sollte nur ein paar Zeilen lang sein. In Pseudocode ausgedrückt, etwa so:

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;

(Außerdem ist es etwas mühsam, die gleiche Logik auch auf die Dezimalstellen anzuwenden).

Es klingt, als hätten Sie die richtige Idee gehabt und vielleicht nur zu viel über die Umsetzung nachgedacht?

Answer 2

Dies sollte funktionieren, wenn N1 >= N2 . Dies setzt auch voraus, dass die Arrays wie folgt angeordnet sind 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 3

Sehr geehrter Herr Professor, die Subtraktion sollte im Zusammenhang mit der Addition definiert werden. Ich habe den unären Operator "-" überladen und die Bignum-Additionsroutine an anderer Stelle definiert. Ich verwende 9er-Komplement um die Addition zu vereinfachen/beschleunigen (kein lästiger Übertrag erforderlich!) mit einer tabellenbasierten Antwortsuche (warum die Summen berechnen, wenn es nur 10 davon gibt?). Die bigNum-Subtraktionsroutine (nach Ihren Vorgaben) folgt:

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