Aufteilung der großen Zahlen

Question

Ich brauche Divisionsalgorithmus, die große Zahlen (128 Bit) verarbeiten kann. Ich habe schon gefragt, wie es über Bitverschieben Betreiber zu tun. Allerdings ist meine aktuelle Implementierung scheint für einen besseren Ansatz zu stellen

Im Grunde ist speichern Zahlen als zwei long long unsigned int sind im Format

A * 2 ^ 64 + B mit B < 2 ^ 64.

Diese Zahl ist teilbar durch 24 und ich möchte es teilen, indem er 24.

Mein aktueller Ansatz ist es zu transformieren, wie

A * 2 ^ 64 + B     A             B
--------------  = ---- * 2^64 + ----
      24           24            24

           A               A mod 24                    B         B mod 24
= floor( ---- ) * 2^64 +  ---------- * 2^64 + floor( ---- ) +   ----------
           24               24.0                      24           24.0

Dies ist jedoch fehlerhaft.

(Beachten Sie, dass Boden A / 24 ist und dass mod ist A % 24. Die normalen Divisionen in long double gespeichert sind, werden die ganzen Zahlen in long long unsigned int gespeichert.

Da 24 gleich binär 11000, der zweite Summand soll nicht etwas im Bereich des vierten Summanden ändern, da es 64 Bits nach links verschoben wird.

Also, wenn A * 2 ^ 64 + B durch 24 teilbar ist, und B ist nicht, es zeigt einfach, dass es Fehler, da es einige nicht-ganzzahlige Zahl zurückgibt.

Was ist der Fehler in meiner Implementierung?

Answer 1

Der einfachste Weg, von dem ich denken kann, dies zu tun ist, um die 128-Bit-Zahlen als vier 32-Bit-Zahlen zu behandeln:

A_B_C_D = A*2^96 + B*2^64 + C*2^32 + D

Und dann tut lange Teilung durch 24:

E = A/24 (with remainder Q)
F = Q_B/24 (with remainder R)
G = R_C/24 (with remainder S)
H = S_D/24 (with remainder T)

Wo X_Y bedeutet X*2^32 + Y. Dann wird die Antwort mit Rest E_F_G_H T. An jedem Punkt müssen Sie nur Teilung von 64-Bit-Zahlen, so sollte dies nur mit Integer-Operationen machbar sein.

Answer 2

Könnte dies möglicherweise mit inverser Multiplikation gelöst werden? Das erste, was zu beachten ist, dass 24 == 8 * 3 so das Ergebnis des

a / 24 == (a >> 3) / 3

Lassen Sie x = (a >> 3) dann das Ergebnis der Division 8 * (x / 3) ist. Jetzt gilt es noch den Wert von x / 3 zu finden.

Modulare Arithmetik besagt, dass es existiert eine Reihe n so dass n * 3 == 1 (mod 2^128). Dies ergibt:

x / 3 = (x * n) / (n * 3) = x * n

Es bleibt die Konstante n zu finden. Es gibt eine Erklärung, wie dies zu tun auf wikipedia . Sie werden auch Funktionalität implementieren müssen, um 128-Bit-Zahlen zu multiplizieren.

Hope, das hilft.

/A.B.

Answer 3

Sie sollten nicht long double für Ihre „normalen Divisionen“ aber ganzen Zahlen auch dort sein werden. long double nicht genug signifikante Zahlen hat die Antwort richtig zu machen (und sowieso der ganze Punkt ist dies mit Integer-Operationen zu tun, nicht wahr?).

Answer 4

  

Seit 24 gleich 11000 binär, der zweite Summand soll nicht etwas im Bereich des vierten Summanden ändern, da es 64 Bits nach links verschoben wird.

Ihre Formel ist in reellen Zahlen geschrieben. (A mod 24) / 24 kann eine beliebige Anzahl von Dezimalstellen haben (24.1 ist zum Beispiel 0,041666666 ...) und kann daher mit dem vierten Term in Ihrer Zersetzung stören, auch einmal multipliziert mit 2 ^ 64.

Die Eigenschaft, die Y * 2 ^ 64 interferiert nicht mit den unteren Gewicht Binärziffern in einer Additions funktioniert nur, wenn Y eine ganze Zahl ist.

Answer 5

Sie nicht.

Gehen Sie eine Bibliothek greifen diese Dinge zu tun -. Sie unglaublich dankbar sein, werden Sie wählten, wenn seltsame Fehler Debuggen

Snippets.org hatte eine C / C ++ BigInt Bibliothek auf seiner Website eine Weile her, Google erschienen auch die folgenden: http://mattmccutchen.net/bigint/