Arithmetische Erklärung mit beliebiger Genauigkeit

StackOverflow https://stackoverflow.com/questions/1218149

  •  10-07-2019
  •  | 
  •  

Frage

Ich versuche C zu lernen und bin auf die Unfähigkeit gestoßen, mit WIRKLICH großen Zahlen (z. B. 100 Ziffern, 1000 Ziffern usw.) zu arbeiten.Mir ist bekannt, dass es dafür Bibliotheken gibt, aber ich möchte versuchen, es selbst zu implementieren.

Ich möchte nur wissen, ob jemand eine sehr detaillierte, vereinfachte Erklärung der Arithmetik mit beliebiger Genauigkeit hat oder liefern kann.

War es hilfreich?

Lösung

Es ist alles eine Frage der angemessenen Speicherung und der Algorithmen, um Zahlen als kleinere Teile zu behandeln.Nehmen wir an, Sie haben einen Compiler, in dem ein int kann nur 0 bis 99 sein und Sie möchten Zahlen bis 999999 verarbeiten (der Einfachheit halber kümmern wir uns hier nur um positive Zahlen).

Sie tun dies, indem Sie jeder Zahl drei geben ints und verwende die gleichen Regeln, die du schon in der Grundschule für Addition, Subtraktion und die anderen Grundoperationen gelernt hast (hätten solltest).

In einer Bibliothek mit beliebiger Genauigkeit gibt es keine feste Grenze für die Anzahl der Basistypen, die zur Darstellung unserer Zahlen verwendet werden, sondern nur für den Speicher, der gespeichert werden kann.

Ergänzung zum Beispiel: 123456 + 78:

12 34 56
      78
-- -- --
12 35 34

Vom unwichtigsten Ende aus arbeiten:

  • anfänglicher Übertrag = 0.
  • 56 + 78 + 0 Übertrag = 134 = 34 mit 1 Übertrag
  • 34 + 00 + 1 Übertrag = 35 = 35 mit 0 Übertrag
  • 12 + 00 + 0 Übertrag = 12 = 12 mit 0 Übertrag

Genauso funktioniert die Addition im Allgemeinen auf Bitebene in Ihrer CPU.

Die Subtraktion ist ähnlich (unter Verwendung der Subtraktion des Basistyps und des Entleihens anstelle des Übertrags), die Multiplikation kann mit wiederholten Additionen (sehr langsam) oder Kreuzprodukten (schneller) erfolgen und die Division ist schwieriger, kann aber durch Verschieben und Subtrahieren der Zahlen erfolgen beteiligt (die lange Division, die Sie als Kind gelernt hätten).

Ich habe tatsächlich Bibliotheken geschrieben, um solche Dinge mit den maximalen Zehnerpotenzen zu tun, die quadriert in eine ganze Zahl passen (um einen Überlauf bei der Multiplikation von zwei zu verhindern). ints zusammen, wie zum Beispiel ein 16-Bit int ist auf 0 bis 99 begrenzt, um quadriert 9.801 (<32.768) oder 32-Bit zu erzeugen int Verwendung von 0 bis 9.999 zur Generierung von 99.980.001 (<2.147.483.648)), was die Algorithmen erheblich vereinfachte.

Einige Tricks, auf die Sie achten sollten.

1/ Wenn Sie Zahlen addieren oder multiplizieren, reservieren Sie im Voraus den maximal benötigten Platz und reduzieren Sie ihn später, wenn Sie feststellen, dass es zu viel ist.Fügen Sie beispielsweise zwei 100-stellige Ziffern hinzu (wobei Ziffer eine ist int) Zahlen ergeben nie mehr als 101 Ziffern.Das Multiplizieren einer 12-stelligen Zahl mit einer 3-stelligen Zahl ergibt nie mehr als 15 Ziffern (addieren Sie die Ziffernanzahl).

2/ Um die Geschwindigkeit zu erhöhen, normalisieren Sie die Zahlen nur dann (reduzieren Sie den erforderlichen Speicher), wenn dies unbedingt erforderlich ist. In meiner Bibliothek gab es dies als separaten Aufruf, sodass der Benutzer zwischen Geschwindigkeits- und Speicherproblemen entscheiden kann.

3/ Die Addition einer positiven und einer negativen Zahl ist eine Subtraktion, und die Subtraktion einer negativen Zahl ist dasselbe wie die Addition der entsprechenden positiven Zahl.Sie können eine ganze Menge Code einsparen, indem Sie die Additions- und Subtraktionsmethoden nach dem Anpassen der Vorzeichen gegenseitig aufrufen.

4/ Vermeiden Sie es, große Zahlen von kleinen zu subtrahieren, da Sie am Ende immer Zahlen wie die folgenden erhalten:

         10
         11-
-- -- -- --
99 99 99 99 (and you still have a borrow).

Subtrahieren Sie stattdessen 10 von 11 und negieren Sie es dann:

11
10-
--
 1 (then negate to get -1).

Hier sind die Kommentare (in Text umgewandelt) von einer der Bibliotheken, für die ich dies tun musste.Der Code selbst ist leider urheberrechtlich geschützt, aber Sie können möglicherweise genügend Informationen heraussuchen, um die vier Grundoperationen durchzuführen.Gehen Sie im Folgenden davon aus -a Und -b stellen negative Zahlen dar und a Und b sind Null oder positive Zahlen.

Für Zusatz, wenn die Vorzeichen unterschiedlich sind, verwenden Sie die Subtraktion der Negation:

-a +  b becomes b - a
 a + -b becomes a - b

Für Subtraktion, wenn die Vorzeichen unterschiedlich sind, verwenden Sie die Addition der Negation:

 a - -b becomes   a + b
-a -  b becomes -(a + b)

Außerdem spezielle Handhabung, um sicherzustellen, dass wir kleine Zahlen von großen subtrahieren:

small - big becomes -(big - small)

Multiplikation verwendet Einstiegsmathematik wie folgt:

475(a) x 32(b) = 475 x (30 + 2)
               = 475 x 30 + 475 x 2
               = 4750 x 3 + 475 x 2
               = 4750 + 4750 + 4750 + 475 + 475

Dies wird dadurch erreicht, dass jede Ziffer von 32 einzeln (rückwärts) extrahiert und dann mithilfe von „add“ ein Wert berechnet wird, der zum Ergebnis addiert werden soll (anfangs Null).

ShiftLeft Und ShiftRight Operationen werden verwendet, um a schnell zu multiplizieren oder zu dividieren LongInt durch den Wrap-Wert (10 für „echte“ Mathematik).Im obigen Beispiel addieren wir 475 zweimal zu Null (die letzte Ziffer von 32), um 950 zu erhalten (Ergebnis = 0 + 950 = 950).

Dann verließen wir die Schicht 475, um 4750 zu erhalten, und wechselten nach rechts, 32, um 3 zu erhalten.Addiere 4750 dreimal zu Null, um 14250 zu erhalten, und addiere dann zum Ergebnis von 950, um 15200 zu erhalten.

Linksverschiebung 4750, um 47500 zu erhalten, Rechtsverschiebung 3, um 0 zu erhalten.Da die nach rechts verschobene 32 jetzt Null ist, sind wir fertig und tatsächlich entspricht 475 x 32 15200.

Aufteilung ist ebenfalls knifflig, basiert aber auf früher Arithmetik (der „gazinta“-Methode für „geht hinein“).Betrachten Sie die folgende lange Division für 12345 / 27:

       457
   +-------
27 | 12345    27 is larger than 1 or 12 so we first use 123.
     108      27 goes into 123 4 times, 4 x 27 = 108, 123 - 108 = 15.
     ---
      154     Bring down 4.
      135     27 goes into 154 5 times, 5 x 27 = 135, 154 - 135 = 19.
      ---
       195    Bring down 5.
       189    27 goes into 195 7 times, 7 x 27 = 189, 195 - 189 = 6.
       ---
         6    Nothing more to bring down, so stop.

daher 12345 / 27 Ist 457 mit Rest 6.Verifizieren:

  457 x 27 + 6
= 12339    + 6
= 12345

Dies wird implementiert, indem eine Drawdown-Variable (anfangs Null) verwendet wird, um die Segmente von 12345 nacheinander zu reduzieren, bis sie größer oder gleich 27 ist.

Dann subtrahieren wir einfach 27 davon, bis wir unter 27 kommen – die Anzahl der Subtraktionen ist das zur obersten Zeile addierte Segment.

Wenn es keine weiteren Segmente mehr gibt, die abgebaut werden müssen, haben wir unser Ergebnis.

Bedenken Sie, dass es sich hierbei um ziemlich einfache Algorithmen handelt.Es gibt weitaus bessere Möglichkeiten, komplexe Arithmetik durchzuführen, wenn Ihre Zahlen besonders groß sind.Sie können sich so etwas ansehen GNU Multiple Precision Arithmetic Library - Es ist wesentlich besser und schneller als meine eigenen Bibliotheken.

Es hat zwar das ziemlich unglückliche Manko, dass es einfach beendet wird, wenn ihm der Speicher ausgeht (meiner Meinung nach ein ziemlich schwerwiegender Fehler für eine Allzweckbibliothek), aber wenn man darüber hinwegsieht, ist es ziemlich gut in dem, was es tut.

Wenn Sie es aus Lizenzgründen nicht verwenden können (oder weil Sie nicht möchten, dass Ihre Anwendung einfach ohne ersichtlichen Grund beendet wird), können Sie von dort zumindest die Algorithmen zur Integration in Ihren eigenen Code erhalten.

Ich habe auch festgestellt, dass die Körper drüben sind MPIR (eine Abzweigung von GMP) sind für Diskussionen über mögliche Änderungen zugänglicher – sie scheinen eine entwicklerfreundlichere Gruppe zu sein.

Andere Tipps

Während das Rad neu zu erfinden, ist sehr gut für Ihre persönliche Erbauung und Lernen, es ist auch eine extrem große Aufgabe. Ich will dich nicht als eine wichtige Übung abzuhalten und eine, die ich selbst gemacht habe, aber Sie sollten sich bewusst sein, dass es subtile und komplexe Fragen bei der Arbeit, dass größere Pakete Adresse.

Zum Beispiel Multiplikation. Naiv, könnten Sie die ‚Schüler‘ Methode denken, das heißt schreiben eine Zahl über den anderen, dann lange Multiplikation tun, wie Sie in der Schule gelernt. Beispiel: 

      123
    x  34
    -----
      492
+    3690
---------
     4182

aber dieses Verfahren ist sehr langsam (O (n ^ 2), wobei n die Anzahl der Ziffern). Stattdessen verwenden moderne bignum Pakete entweder eine diskrete Fourier-Transformation oder eine numerische Transformation dieses in eine im wesentlichen O (n ln (n)) den Betrieb zu aktivieren.

Und das ist nur für ganze Zahlen. Wenn Sie in kompliziertere Funktionen auf irgendeine Art von realen Darstellung Nummer erhalten (log, sqrt, exp, etc.) die Dinge noch komplizierter.

Wenn Sie einigen theoretischen Hintergrund mögen, empfehle ich das erste Kapitel von Yap Buch zu lesen, "Grundprobleme der Algorithmic Algebra" . Wie bereits erwähnt, ist die gmp bignum Bibliothek eine ausgezeichnete Bibliothek. Für reelle Zahlen, die ich benutzt habe mpfr und mochte es.

Sie neu erfinden das Rad nicht: es könnte sich als quadratisch sein!

Verwenden Sie einen Dritten Bibliothek, wie GNU MP , dass versucht wird, und getestet.

Sie tun es grundsätzlich auf die gleiche Art und Weise Sie mit Bleistift und Papier zu tun ...

  • Die Zahl ist, die in einem Puffer (array) dargestellt werden können auf eine beliebige Größe nehmen (was bedeutet malloc und realloc verwendet) je nach Bedarf
  • Sie so viel wie möglich Grundrechen implementieren Strukturen unter Verwendung von Sprache unterstützt, und befassen sich mit trägt und das Bewegen des Radix-Punkt manuell
  • Sie scheuern Texte numerische Analyse effizient Argumente finden durch komplexere Funktion zu tun
  • Sie nur so viel implementieren, wie Sie benötigen.

Normalerweise werden Sie, wie Sie grundlegende Einheit der Berechnung verwenden

  • Bytes enthält, mit 0-99 oder 0-255
  • 16-Bit-Wörter contaning Widerrist 0-9999 oder 0--65.536
  • 32-Bit-Wort ...
  • ...

, wie von Ihrer Architektur diktiert wird.

Die Wahl der Base binär oder dezimal hängt von Dir wünscht, für eine maximale Raumausnutzung, die menschliche Lesbarkeit, und die Anwesenheit von Abwesenheit von Binary Coded Decimal (BCD) Mathe-Unterstützung auf Ihrem Chip.

Sie können es mit High-School-Niveau der Mathematik. Obwohl erweiterte Algorithmen sind in der Realität verwendet. So zum Beispiel hinzuzufügen, zwei 1024-Byte-Zahlen: 

unsigned char first[1024], second[1024], result[1025];
unsigned char carry = 0;
unsigned int  sum   = 0;

for(size_t i = 0; i < 1024; i++)
{
    sum = first[i] + second[i] + carry;
    carry = sum - 255;
}

Ergebnis wird durch one place im Fall der Zugabe größer sein zu kümmern Maximalwerte. Schauen Sie sich diese: 

9
   +
9
----
18

TTMath ist eine große Bibliothek, wenn Sie lernen möchten. Es wird unter Verwendung von C ++ gebaut. Das obige Beispiel war albern, aber das ist, wie Addition und Subtraktion wird im Allgemeinen getan!

Eine gute Referenz über das Thema ist Komplexitäts mathematischer Operationen . Es sagt Ihnen, wie viel Platz für jede Operation erforderlich ist, Sie implementieren möchten. Wenn Sie zwei N-digit Zahlen Zum Beispiel haben, dann müssen Sie 2N digits das Ergebnis der Multiplikation speichern.

Mitch sagte, ist es bei weitem keine leichte Aufgabe zu implementieren! Ich empfehle Ihnen, einen Blick auf TTMath nehmen, wenn Sie wissen, C ++.

Einer der ultimativen Referenzen (IMHO) ist Knuths TAOCP Volume II. Es erklärt viele Algorithmen für Zahlen und arithmetische Operationen auf diesen Darstellungen darstellt. 

@Book{Knuth:taocp:2,
   author    = {Knuth, Donald E.},
   title     = {The Art of Computer Programming},
   volume    = {2: Seminumerical Algorithms, second edition},
   year      = {1981},
   publisher = {\Range{Addison}{Wesley}},
   isbn      = {0-201-03822-6},
}

Unter der Annahme, dass Sie mögen einen großen Integer-Code selbst schreiben, kann dies überraschend einfach sein, wie jemand gesprochen zu tun, die sie vor kurzem haben hier einige der Tricks, die ich verwenden (obwohl in MATLAB.):

  • ich jede einzelne Dezimalziffer als Doppelnummer gespeichert. Das macht viele Operationen einfach, vor allem Ausgabe. Während es mehr Speicherplatz in Anspruch nimmt, als Sie vielleicht wünschen, ist die Erinnerung hier billig, und es macht Multiplikation sehr effizient, wenn Sie effizient ein Paar von Vektoren convolve können. Alternativ können Sie auch in einem Doppel mehrere Dezimalstellen speichern, aber passen Sie dann die Faltung die Multiplikation zu tun, kann auf eine sehr große Zahl numerischen Problemen führen.

  • Speicher ein Vorzeichenbit getrennt.

  • Addition zweier Zahlen ist vor allem eine Frage der Ziffern der Zugabe, dann überprüfen Sie für einen Übertrag bei jedem Schritt.

  • Die Multiplikation eines Paar von Zahlen ist am besten als Faltung von einem Übertragsschritt getan, zumindest wenn man einen schnellen Faltungscode vom Fass.

  • Auch wenn Sie speichern die Zahlen als Folge von einzelnen Dezimalstellen, Division (auch mod / rem ops) können etwa 13 Dezimalstellen erfolgen im Ergebnis zu einer Zeit zu gewinnen. Das ist viel effizienter als eine Kluft, die nur 1 Nachkommastelle zu einer Zeit arbeitet an.

  • Um eine ganzzahlige Potenz einer ganzen Zahl zu berechnen, die binäre Darstellung des Exponenten berechnen. verwenden wiederholt quadriert Operationen dann die Kräfte zu berechnen, je nach Bedarf.

  • Viele Operationen (Factoring, Primzahltests, etc.) werden von einem PowerMod Betrieb profitieren. Das heißt, wenn man mod (a ^ p, N) berechnet, reduziert das Ergebnis mod N bei jedem Schritt der Potenzierung wobei p hat in einer binären Form exprimiert. Berechnen Sie keine ^ p zuerst, und dann versuchen, es mod N zu reduzieren.

Hier ist ein einfaches (naive) Beispiel, das ich in PHP getan hat.

I „Add“ und „Multiplizieren“ implementiert und verwenden, dass für einen Exponenten Beispiel.

http://adevsoft.com/simple-php -arbitrary Präzisions-integer-big-num-Beispiel /

Code-Schnipsel 

// Add two big integers
function ba($a, $b)
{
    if( $a === "0" ) return $b;
    else if( $b === "0") return $a;

    $aa = str_split(strrev(strlen($a)>1?ltrim($a,"0"):$a), 9);
    $bb = str_split(strrev(strlen($b)>1?ltrim($b,"0"):$b), 9);
    $rr = Array();

    $maxC = max(Array(count($aa), count($bb)));
    $aa = array_pad(array_map("strrev", $aa),$maxC+1,"0");
    $bb = array_pad(array_map("strrev", $bb),$maxC+1,"0");

    for( $i=0; $i<=$maxC; $i++ )
    {
        $t = str_pad((string) ($aa[$i] + $bb[$i]), 9, "0", STR_PAD_LEFT);

        if( strlen($t) > 9 )
        {
            $aa[$i+1] = ba($aa[$i+1], substr($t,0,1));
            $t = substr($t, 1);
        }

        array_unshift($rr, $t);
     }

     return implode($rr);
}
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top