Mit extrem großen Zahlen in einer Sprache umgehen, die es nicht kann?

15

Ich versuche darüber nachzudenken, wie ich mit extrem großen Zahlen rechnen würde (bis unendlich - keine Fließkommazahlen), wenn das Sprachkonstrukt keine Zahlen verarbeiten kann, die größer als ein bestimmter Wert sind.

Ich bin sicher, dass ich nicht der Erste oder der Letzte bin, der diese Frage stellt, aber die Suchbegriffe, die ich verwende, geben mir keinen Algorithmus, um mit diesen Situationen umzugehen. Eher bieten die meisten Vorschläge einen Sprach- oder Variablenwechsel an oder sprechen über Dinge, die für meine Suche irrelevant erscheinen. Also brauche ich eine kleine Anleitung.

Ich würde einen Algorithmus wie diesen skizzieren:

  1. Bestimmen Sie die maximale Länge der Ganzzahlvariablen für die Sprache.

  2. Wenn eine Zahl länger als die Hälfte der maximalen Länge der Variablen ist, wird sie in einem Array aufgeteilt. (Gib ein kleines Spielzimmer)

  3. Array-Reihenfolge [0] = die Zahlen ganz rechts [n-max] = die Zahlen ganz links

    Ex. Num: 29392023 Array [0]: 23, Array [1]: 20, Array [2]: 39, Array [3]: 29

Da ich die halbe Länge der Variablen als Markierungspunkt festgelegt habe, kann ich dann die Einsen, Zehntel, Hundertstel usw. berechnen. Platzieren Sie die Variable über die Zwischenmarke, sodass ich das weiß, wenn die maximale Länge einer Variablen 10 Stellen von 0 bis 9999999999 beträgt Indem ich das auf fünf Ziffern halbiere, bekomme ich etwas Spielraum.

Wenn ich also addiere oder multipliziere, kann ich eine variable Prüffunktion haben, die feststellt, dass die sechste Stelle (von rechts) von Array [0] mit der ersten Stelle (von rechts) von Array [1] identisch ist.

Teilen und Subtrahieren haben ihre eigenen Probleme, über die ich noch nicht nachgedacht habe.

Ich würde gerne wissen, welche Implementierungen für die Unterstützung größerer Zahlen am besten geeignet sind als das Programm.

Malve
quelle
1
Das erste, was mir einfällt, ist Javas BigInteger: docs.oracle.com/javase/6/docs/api/java/math/BigInteger.html
Ivan,
Ist dies eine Sprache, die jeder hier kennen und die in der Lage ist, spezifische Empfehlungen abzugeben, oder ist sie etwas Dunkles und Eigenartiges?
FrustratedWithFormsDesigner
Ich weiß noch nicht, für welche Sprache ich das haben möchte. Ich kenne PHP am besten, aber ich möchte es nicht in dieser Sprache machen. Lisp ist attraktiv, da es, wie ich gelesen habe, keine Längenbeschränkungen gibt. Mein persönlicher Fehler, wissen zu wollen, wie es funktioniert, lässt mich jedoch die Freiheit haben, es in qbasic zu tun, wenn ich auf einer Insel festsitze. (Es ist auch zum Spaß, ich denke immer über das Berechnen von großen Zahlen nach und einige Online-Rechner sind zu umständlich für die Aufgabe.)
Mallow

Antworten:

25

Sie suchen eine Arithmetikbibliothek mit willkürlicher Genauigkeit (auch "multiple precision" oder "big num" genannt) für die Sprache, mit der Sie arbeiten. Wenn Sie zum Beispiel mit C arbeiten, können Sie die GNU Bignum Library verwenden -> http://gmplib.org/

Wenn Sie verstehen möchten, wie es funktioniert, können Sie auch Ihre eigene Big Num-Bibliothek schreiben und diese verwenden. Am einfachsten geht das mit Arrays, bei denen jedes Element eine Ziffer der Zahl ist, mit der Sie arbeiten. Danach müssen Sie alle Funktionen implementieren, um zu addieren, zu subtrahieren, zu multiplizieren, zu dividieren, zu potenzieren und so weiter.

Daniel Scocco
quelle
5
Natürlich ist "digit" relativ, viele Bignum-Bibliotheken verwenden Ziffern in der Basis 256 (unsigned byte []) bis 2 ^ 64 (unsigned long [])
Ratschenfreak
1
Nur um sicherzugehen, dass ich verstanden habe, dass 'digit' ein Array von 256 Stellen sein kann? Ich glaube, ich könnte mich irren, Mathe auf Basis 256 ist einfacher als Basis 88, aber immer noch eine ziemliche Aufgabe ... (Zumindest als ich es letzte Nacht auf einem Blatt Papier getan habe, haha)
Mallow
1
msgstr "Mathe auf Basis 256 ist einfacher als auf Basis 88". Falsch. Sie sind genauso einfach.
S.Lott
2
@ S.Lott: ähm ... wenn bitweise Operationen verfügbar sind, ist es definitiv einfacher, auf Basis 256 zu rechnen als auf Basis 88.
Jason S
1
Das Bauen eines eigenen Addierens / Subtrahierens / Multiplizierens ist ziemlich einfach. Die Division ist jedoch schwierig, es sei denn, Sie implementieren sie in Binärform, wo sie zu einer Übung für bedingte Subtraktion und Bitverschiebung wird.
Jason S
13

Es ist ein bekanntes Problem: Arithmetik mit beliebiger Genauigkeit

Wenn die von Ihnen verwendete Sprache dieses Problem nicht behebt, suchen Sie zunächst eine Drittanbieter-Bibliothek, die dies tut. Wenn Sie es nicht finden oder neugierig sind, versuchen Sie es umzusetzen. Der Wikipedia-Artikel enthält gute Verweise auf klassische Implementierungen.

jgomo3
quelle
6

Im Umgang mit großen Zahlen ist wahrscheinlich eine der grundlegendsten Entwurfsentscheidungen, wie ich die große Zahl darstellen werde.

Handelt es sich um eine Zeichenfolge, ein Array, eine Liste oder eine benutzerdefinierte (hausgemachte) Speicherklasse?

Nachdem diese Entscheidung getroffen wurde, können die tatsächlichen mathematischen Operationen in kleinere Teile zerlegt und dann mit Muttersprachentypen wie int oder integer ausgeführt werden.

Ich habe ein sehr rudimentäres ADDITION-Beispiel in C # .Net eingefügt, in dem die resultierende große Zahl als Zeichenfolge gespeichert wird. Eingehende "Zahlen" sind ebenfalls Zeichenfolgen, daher sollte man in der Lage sein, sehr "große" Zahlen einzusenden. Denken Sie daran, dass das Beispiel nur für ganze Zahlen gedacht ist, um es einfach zu halten.

Auch bei Strings gibt es eine Begrenzung der Anzahl von Zeichen oder "Zahlen" in der Anzahl, wie hier angegeben:

Was ist die maximal mögliche Länge eines .NET-Strings?

Sie können jedoch einige wirklich große Zahlen hinzufügen, die weit über die nativen Typen int32 oder int64 für .Net hinausgehen.

Wie auch immer, hier ist eine String-Speicherimplementierung.

/// <summary>
/// Adds two "integers".  The integers can be of any size string.
/// </summary>
/// <param name="BigInt1">The first integer</param>
/// <param name="BigInt2">The second integer</param>
/// <returns>A string that is the addition of the two integers passed.</returns>
/// <exception cref="Exception">Can throw an exception when parsing the individual parts     of the number.  Callers should handle. </exception>
public string AddBigInts(string BigInt1, string BigInt2)
{
    string result = string.Empty;

    //Make the strings the same length, pre-pad the shorter one with zeros
    int length = (BigInt1.Length > BigInt2.Length ? BigInt1.Length : BigInt2.Length);
    BigInt1 = BigInt1.PadLeft(length, '0');
    BigInt2 = BigInt2.PadLeft(length, '0');

    int remainder = 0;

    //Now add them up going from right to left
    for (int i = (BigInt1.Length - 1); i >= 0; i--)
    {
        //If we don't encounter a number, this will throw an exception as indicated.
        int int1 = int.Parse(BigInt1[i].ToString());
        int int2 = int.Parse(BigInt2[i].ToString());

        //Add
        int add = int1 + int2 + remainder;

        //Check to see if we need a remainder;
        if (add >= 10)
        {
            remainder = 1;
            add = add % 10;
        }
        else
        {
            remainder = 0;
        }

        //Add this to our "number"
        result = add.ToString() + result;
    }

    //Handle when we have a remainder left over at the end
    if (remainder == 1)
    {
        result = remainder + result;
    }

    return result;
}

Ich hoffe, das gibt Ihnen einige Anregungen für Ihre eigene Implementierung. Bitte beachten Sie, dass der Beispielcode wahrscheinlich nicht optimiert ist. Es soll einige Ideen geben, wie es getan werden könnte.

Jon Raynor
quelle
Cool!! Vielen Dank, es hilft, die Dinge mit Resten zu klären, die ich über das zusätzliche bisschen kompliziert hätte.
Mallow
-2

Dieser arbeitet bei mir schneller:

static string Add(string a, string b)
        {
            string c = null;

            if (Compare(a, b) < 0)
            {
                c = a;
                a = b;
                b = c;
            }

            StringBuilder sb = new StringBuilder();

            b = b.PadLeft(a.Length, '0');

            int r = 0;

            for (int i = a.Length - 1; i >= 0; i--)
            {
                int part = a[i] + b[i] + r - 96;

                if (part <= 9)
                {
                    sb.Insert(0, part);

                    r = 0;
                }
                else
                {
                    sb.Insert(0, part - 10);

                    r = 1;
                }
            }

            if (r == 1)
            {
                sb.Insert(0, "1");
            }

            return sb.ToString();
        }
Andranik Sargsyan
quelle
2
Auf dieser Website geht es um konzeptionelle Fragen, und von Antworten wird erwartet, dass sie die Dinge erklären. Das Werfen von Code-Dumps anstelle von Erklärungen ist wie das Kopieren von Code von IDE auf Whiteboard: Es mag vertraut und manchmal sogar verständlich erscheinen, aber es fühlt sich seltsam an ... einfach seltsam. Whiteboard hat keinen Compiler
Mücke
Diese Seite ist EXCHANGE, deshalb versuchen wir, uns gegenseitig so gut wie möglich zu helfen. Vielleicht sollte ich solche Kommentare in StackOverflow machen, aber ich habe versucht, mit meinem Ansatz zu helfen. Wenn jemand noch eine Erklärung braucht, wird er danach fragen. Ich mache hier eine mathematische Standardaddition Ziffer für Ziffer, beginnend am Ende.
Andranik Sargsyan
Stimmen Sie mit Mücke überein. Erklären Sie zumindest den Algorithmus, bevor Sie den Code ausgeben.
Frank Hileman
Nur Code ohne Erklärung zu entleeren, ist wie das Copy-Past-and-Go zu fördern. Ich sehe nicht, wie das in SoftwareEngineering nützlich sein könnte. Vielleicht bei StackOverflow, aber beide Seiten haben eigentlich ganz unterschiedliche Zwecke.
Laiv