Wie man big int in C++ implementiert

Ich möchte als Programmierübung eine große int-Klasse in C++ implementieren – eine Klasse, die mit Zahlen umgehen kann, die größer als ein langer int sind. Ich weiß, dass es bereits mehrere Open-Source-Implementierungen gibt, aber ich würde gerne meine eigene schreiben. Ich versuche, ein Gefühl dafür zu bekommen, was der richtige Ansatz ist.

Ich verstehe, dass die allgemeine Strategie darin besteht, die Zahl als Zeichenfolge zu erhalten und sie dann in kleinere Zahlen (z. B. einzelne Ziffern) aufzuteilen und sie in einem Array zu platzieren. An dieser Stelle sollte es relativ einfach sein, die verschiedenen Vergleichsoperatoren zu implementieren. Meine Hauptsorge ist, wie ich Dinge wie Addition und Multiplikation implementieren würde.

Ich suche nach einem allgemeinen Ansatz und Ratschlägen im Gegensatz zum eigentlichen Arbeitscode.

Eine lustige Herausforderung. 🙂

Ich gehe davon aus, dass Sie ganze Zahlen beliebiger Länge wollen. Ich schlage folgende Vorgehensweise vor:

Betrachten Sie die binäre Natur des Datentyps “int”. Denken Sie darüber nach, einfache binäre Operationen zu verwenden, um zu emulieren, was die Schaltkreise in Ihrer CPU tun, wenn sie Dinge hinzufügen. Falls Sie tiefergehend interessiert sind, lesen Sie weiter Dieser Wikipedia-Artikel über Halbaddierer und Volladdierer. Sie werden etwas Ähnliches tun, aber Sie können so weit nach unten gehen – aber da ich faul bin, dachte ich, ich würde einfach darauf verzichten und eine noch einfachere Lösung finden.

Aber bevor wir uns mit algorithmischen Details zum Addieren, Subtrahieren und Multiplizieren befassen, wollen wir eine Datenstruktur finden. Eine einfache Möglichkeit besteht natürlich darin, Dinge in einem std::vector zu speichern.

template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};

Sie sollten überlegen, ob Sie den Vektor mit einer festen Größe erstellen und ihn vorbelegen möchten. Der Grund dafür ist, dass Sie für verschiedene Operationen jedes Element des Vektors – O (n) – durchlaufen müssen. Vielleicht möchten Sie sofort wissen, wie komplex eine Operation sein wird, und ein festes n tut genau das.

Aber nun zu einigen Algorithmen zur Bearbeitung der Zahlen. Sie könnten es auf logischer Ebene tun, aber wir verwenden diese magische CPU-Leistung, um Ergebnisse zu berechnen. Aber was wir von der logischen Darstellung von Halb- und Volladdierern übernehmen, ist die Art und Weise, wie sie mit Überträgen umgeht. Überlegen Sie als Beispiel, wie Sie die implementieren würden += Operator. Für jede Zahl in BigInt<>::value_ würden Sie diese addieren und sehen, ob das Ergebnis eine Art Übertrag erzeugt. Wir werden es nicht bitweise tun, sondern verlassen uns auf die Natur unseres Basistyps (sei es lang oder int oder kurz oder was auch immer): Es läuft über.

Wenn Sie zwei Zahlen addieren, muss das Ergebnis sicherlich größer sein als die größere dieser Zahlen, oder? Wenn dies nicht der Fall ist, ist das Ergebnis übergelaufen.

template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand)
{
  BT count, carry = 0;
  for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
  {
    BT op0 = count < value_.size() ? value_.at(count) : 0, 
       op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
    BT digits_result = op0 + op1 + carry;
    if (digits_result-carry < std::max(op0, op1)
    {
      BT carry_old = carry;
      carry = digits_result;
      digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
    }
    else carry = 0;
  }

  return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
//         not, then you must restrict BaseType to be the second biggest type 
//         available, i.e. a 32-bit int when you have a 64-bit long. Then use
//         a temporary or a cast to the mightier type and retrieve the upper bits. 
//         Or you do it bitwise. ;-)

Die anderen Rechenoperationen gehen analog. Verdammt, Sie könnten sogar die stl-Funktoren std::plus und std::minus, std::times und std::divides verwenden, …, aber achten Sie auf den Übertrag. 🙂 Sie können auch Multiplikation und Division implementieren, indem Sie Ihre Plus- und Minus-Operatoren verwenden, aber das ist sehr langsam, da dies Ergebnisse neu berechnen würde, die Sie bereits in vorherigen Aufrufen von Plus und Minus in jeder Iteration berechnet haben. Es gibt viele gute Algorithmen für diese einfache Aufgabe, verwenden Wikipedia oder das Netz.

Und natürlich sollten Sie Standardoperatoren wie implementieren operator<< (Verschieben Sie einfach jeden Wert in value_ um n Bits nach links, beginnend bei der value_.size()-1… oh und denk an das tragen :), operator< – Sie können hier sogar ein wenig optimieren, indem Sie die ungefähre Anzahl der Stellen mit überprüfen size() Erste. Und so weiter. Dann machen Sie Ihre Klasse nützlich, indem Sie std::ostream anfreunden operator<<.

Hoffe, dieser Ansatz ist hilfreich!

Dinge, die für eine große int-Klasse zu beachten sind:

1. Mathematische Operatoren: +, -, /, *, % Vergessen Sie nicht, dass Ihre Klasse auf beiden Seiten des Operators stehen kann, dass die Operatoren verkettet werden können, dass einer der Operanden ein Int, Float, Double usw. sein kann .

2. I/O-Operatoren: >>, << Hier finden Sie heraus, wie Sie Ihre Klasse richtig aus Benutzereingaben erstellen und sie auch für die Ausgabe formatieren.

3. Konvertierungen/Umwandlungen: Finden Sie heraus, in welche Typen/Klassen Ihre große int-Klasse konvertierbar sein sollte und wie Sie die Konvertierung richtig handhaben. Eine schnelle Liste würde Double und Float enthalten und kann Int (mit ordnungsgemäßer Überprüfung der Grenzen) und Complex (vorausgesetzt, sie kann den Bereich verarbeiten) enthalten.

Dazu gibt es einen kompletten Abschnitt: [The Art of Computer Programming, vol.2: Seminumerical Algorithms, section 4.3 Multiple Precision Arithmetic, pp. 265-318 (ed.3)]. Vielleicht finden Sie weiteres interessantes Material in Kapitel 4, Arithmetik.

Wenn Sie sich wirklich keine andere Implementierung ansehen möchten, haben Sie darüber nachgedacht, was Sie lernen möchten? Es gibt unzählige Fehler zu machen und diese aufzudecken ist lehrreich und auch gefährlich. Es gibt auch Herausforderungen beim Identifizieren wichtiger Recheneinsparungen und beim Vorhandensein geeigneter Speicherstrukturen zum Vermeiden schwerwiegender Leistungsprobleme.

Eine Herausforderungsfrage für Sie: Wie beabsichtigen Sie, Ihre Implementierung zu testen, und wie schlagen Sie vor, zu demonstrieren, dass ihre Arithmetik korrekt ist?

Vielleicht möchten Sie eine andere Implementierung testen (ohne zu sehen, wie sie das macht), aber es braucht mehr als das, um verallgemeinern zu können, ohne ein qualvolles Testniveau zu erwarten. Vergessen Sie nicht, Fehlermodi in Betracht zu ziehen (Probleme mit zu wenig Speicher, zu wenig Stack, zu lange Ausführung usw.).

Habe Spaß!

Die Addition müsste wahrscheinlich im standardmäßigen linearen Zeitalgorithmus erfolgen
aber für die Multiplikation könntest du es versuchen http://en.wikipedia.org/wiki/Karatsuba_algorithm

Sobald Sie die Ziffern der Zahl in einem Array haben, können Sie genau so addieren und multiplizieren, wie Sie es von Hand tun würden.

Vergessen Sie nicht, dass Sie sich nicht auf 0-9 als Ziffern beschränken müssen, dh verwenden Sie Bytes als Ziffern (0-255) und Sie können immer noch lange Handarithmetik machen, genauso wie Sie es mit Dezimalziffern tun würden. Sie könnten sogar ein Array von long verwenden.

Ich bin nicht davon überzeugt, dass die Verwendung eines Strings der richtige Weg ist – obwohl ich selbst nie Code geschrieben habe, denke ich, dass die Verwendung eines Arrays eines numerischen Basistyps eine bessere Lösung sein könnte. Die Idee ist, dass Sie einfach das erweitern, was Sie bereits haben, genauso wie die CPU ein einzelnes Bit in eine ganze Zahl erweitert.

Zum Beispiel, wenn Sie eine Struktur haben

typedef struct {
    int high, low;
} BiggerInt;

Sie können dann native Operationen für jede der “Ziffern” (in diesem Fall hoch und niedrig) manuell ausführen, wobei Sie auf Überlaufbedingungen achten müssen:

BiggerInt add( const BiggerInt *lhs, const BiggerInt *rhs ) {
    BiggerInt ret;

    /* Ideally, you'd want a better way to check for overflow conditions */
    if ( rhs->high < INT_MAX - lhs->high ) {
        /* With a variable-length (a real) BigInt, you'd allocate some more room here */
    }

    ret.high = lhs->high + rhs->high;

    if ( rhs->low < INT_MAX - lhs->low ) {
        /* No overflow */
        ret.low = lhs->low + rhs->low;
    }
    else {
        /* Overflow */
        ret.high += 1;
        ret.low = lhs->low - ( INT_MAX - rhs->low ); /* Right? */
    }

    return ret;
}

Es ist ein etwas vereinfachtes Beispiel, aber es sollte ziemlich offensichtlich sein, wie man es auf eine Struktur erweitert, die eine variable Zahl der von Ihnen verwendeten numerischen Basisklasse hat.