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

15

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.

Malwa
źródło
1
Pierwszą rzeczą, która przychodzi mi na myśl, jest BigInteger Javy: docs.oracle.com/javase/6/docs/api/java/math/BigInteger.html
Ivan
Czy jest to język, który każdy może tu znać i może wydawać konkretne zalecenia, czy jest to coś niejasnego i zastrzeżonego?
FrustratedWithFormsDesigner
Nie wiem jeszcze, dla którego języka chciałbym tego. Najbardziej znam php, ale nie chcę tego robić w tym języku. Lisp jest atrakcyjny, ponieważ z tego, co przeczytałem, nie ma żadnych ograniczeń długości. Jednak moja osobista wada, że ​​chcę wiedzieć, jak to działa, sprawia, że ​​chcę mieć swobodę robienia tego w qbasic, jeśli utknę na wyspie. (To także dla zabawy, zawsze myślę o obliczaniu dużych liczb, a niektóre kalkulatory internetowe są zbyt kłopotliwe do wykonania tego zadania.)
Mallow

Odpowiedzi:

25

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.

Daniel Scocco
źródło
5
oczywiście „cyfra” jest względna, wiele bibliotek bignum używa cyfr w bazie 256 (bajt bez znaku []) do 2 ^ 64 (długi bez znaku [])
maniak ratchet
1
Tylko upewniając się, że zrozumiałem, „cyfra” może być tablicą podstawowych 256 cyfr? Wydaje mi się, że się mylę, wykonywanie matematyki na bazie 256 jest łatwiejsze niż na bazie 88, ale wciąż jest dość zadaniem ... (Przynajmniej kiedy zrobiłem to wczoraj na kartce papieru haha)
Mallow
1
„Wykonywanie matematyki na podstawie 256 jest łatwiejsze niż na podstawie 88”. Fałszywy. Są równie łatwe.
S.Lott,
2
@ S.Lott: um ... kiedy masz dostępne operacje bitowe, wykonywanie matematyki na bazie 256 jest zdecydowanie łatwiejsze niż na bazie 88.
Jason S
1
Budowanie własnego dodawania / odejmowania / mnożenia jest dość proste. Podział jest trudny, chyba że zastosujesz go w systemie binarnym, gdzie stanie się ćwiczeniem polegającym na warunkowym odejmowaniu i przesuwaniu bitów.
Jason S
13

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.

jgomo3
źródło
6

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ć.

Jon Raynor
źródło
Chłodny!! Dzięki pomaga to uporać się z resztkami, które skomplikowałbym tak bardzo.
Mallow
-2

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();
        }
Andranik Sargsyan
źródło
2
Ta strona jest o koncepcyjnych pytania i oczekuje odpowiedzi, aby wyjaśnić rzeczy. Rzucanie zrzutów kodu zamiast objaśnień przypomina kopiowanie kodu z IDE na tablicę: może wyglądać znajomo, a czasem nawet być zrozumiałe, ale wydaje się dziwne ... po prostu dziwne. Tablica nie ma kompilatora
gnat
Ta strona jest WYMIANA, dlatego staramy się pomagać sobie nawzajem, jak możemy. Może powinienem zrobić takie komentarze w StackOverflow, ale starałem się pomóc w moim podejściu. Jeśli ktoś nadal potrzebuje wyjaśnienia, poprosi o to. Robię tutaj standardowy matematyczny dodatek cyfra po cyfrze, zaczynając od końca.
Andranik Sargsyan
Zgadzam się z komarem. Przynajmniej wyjaśnij algorytm przed zrzuceniem kodu.
Frank Hileman
Sam zrzut kodu bez żadnego wyjaśnienia jest jak zachęcanie do kopiowania i usuwania. Nie rozumiem, jak to może być przydatne w SoftwareEngineering. Może w StackOverflow jest, ale obie strony mają zupełnie inne cele.
Laiv