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

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.

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.

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.

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.

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();
        }