Obsługa bardzo dużych liczb w języku, który nie jest w stanie?

Próbuję myśleć o tym, jak bym zrobił obliczenia na bardzo dużych liczbach (do nieskończoności - intergeruje brak liczb zmiennoprzecinkowych), jeśli konstrukcja języka nie jest w stanie obsłużyć liczb większych niż pewna wartość.

Jestem pewien, że nie jestem pierwszym ani ostatnim, który zadałby to pytanie, ale wyszukiwane hasła nie dają mi algorytmu do obsługi takich sytuacji. Raczej większość sugestii oferuje zmianę języka lub zmianę zmiennej lub mówi o rzeczach, które wydają się nieistotne dla mojego wyszukiwania. Potrzebuję więc trochę przewodnictwa.

Naszkicowałbym taki algorytm:

1. Określ maksymalną długość zmiennej całkowitej dla języka.

2. Jeśli liczba jest większa niż połowa długości maksymalnej długości zmiennej, podziel ją na tablicę. (daj trochę pokoju do zabawy)

3. Kolejność tablic [0] = liczby najbardziej po prawej [n-max] = liczby najbardziej po lewej

   Dawny. Num: 29392023 Tablica [0]: 23, Tablica [1]: 20, tablica [2]: 39, tablica [3]: 29

Ponieważ ustaliłem połowę długości zmiennej jako punkt odcięcia, mogę następnie obliczyć te, dziesiąte, setne itd. Umieścić za pomocą znacznika w połowie, aby jeśli maksymalna zmienna długość wynosiła 10 cyfr od 0 do 9999999999, to wiem, że zmniejszając to do pięciu cyfr, daj mi trochę pokoju do zabawy.

Więc jeśli dodam lub pomnożę, mogę mieć funkcję sprawdzania zmiennych, która zobaczy, że szósta cyfra (z prawej) tablicy [0] to to samo miejsce, co pierwsza cyfra (z prawej) tablicy [1].

Dzielenie i odejmowanie ma swoje własne problemy, o których jeszcze nie myślałem.

Chciałbym wiedzieć o najlepszych implementacjach obsługi większych liczb niż program może.

Szukasz biblioteki arytmetyki o dowolnej precyzji (zwanej także „wielokrotną precyzją” lub „dużą liczbą”) dla języka, z którym pracujesz. Na przykład, jeśli pracujesz z C, możesz użyć Biblioteki GNU Bignum -> http://gmplib.org/

Jeśli chcesz zrozumieć, jak to działa, możesz także napisać własną bibliotekę dużych liczb i korzystać z niej. Najprostszym sposobem na poradzenie sobie z tym jest użycie tablic, w których każdy element jest cyfrą liczby, z którą pracujesz. Następnie musisz zaimplementować wszystkie funkcje, aby dodać, odjąć, pomnożyć, podzielić, potęgować i tak dalej.

Jest to dobrze znany problem: arytmetyka precyzji arbitralnej

Gdy używany język nie rozwiąże tego problemu, najpierw spróbuj znaleźć bibliotekę innej firmy, która to rozwiązuje. Jeśli nie możesz go znaleźć lub jesteś ciekawy, spróbuj go zaimplementować; artykuł w Wikipedii zawiera dobre odniesienia do klasycznych realizacji.

Kiedy mamy do czynienia z dużymi liczbami, prawdopodobnie jedną z najbardziej fundamentalnych decyzji projektowych jest to, jak mam reprezentować dużą liczbę?

Czy będzie to ciąg znaków, tablica, lista lub niestandardowa (własna) klasa pamięci.

Po podjęciu tej decyzji rzeczywiste operacje matematyczne można podzielić na mniejsze części, a następnie wykonać z rodzimymi typami języka, takimi jak int lub integer.

W C # .Net umieściłem bardzo podstawowy przykład DODATKU, który przechowuje wynikową dużą liczbę jako ciąg. Przychodzące „liczby” są również ciągami, więc należy móc wysyłać bardzo „duże” liczby. Należy pamiętać, że przykład dotyczy wyłącznie liczb całkowitych, aby było to proste.

Nawet w przypadku ciągów istnieje ograniczenie liczby znaków lub „liczb” w liczbie, jak wskazano tutaj:

Jaka jest maksymalna możliwa długość łańcucha .NET?

Ale możesz dodać kilka naprawdę dużych liczb, znacznie wykraczających poza natywne typy int32 lub int64 dla .Net.

Tak czy inaczej, oto implementacja przechowywania ciągów.

/// <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;
}

Mam nadzieję, że daje to kilka pomysłów na własne wdrożenie. Pamiętaj, że przykładowy kod prawdopodobnie nie jest zoptymalizowany lub coś podobnego. Ma on dać kilka pomysłów, jak można to zrobić.

Ten działa dla mnie szybciej:

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