Arytmetyka o dowolnej precyzji Wyjaśnienie

Próbuję się nauczyć C i natknąłem się na niemożność pracy z NAPRAWDĘ dużymi liczbami (tj. 100 cyfr, 1000 cyfr itp.). Zdaję sobie sprawę, że istnieją biblioteki, które to robią, ale chcę spróbować wdrożyć to samodzielnie.

Chcę tylko wiedzieć, czy ktoś ma lub może podać bardzo szczegółowe, głupie wyjaśnienie arytmetyki z arbitralną precyzją.

Wszystko zależy od odpowiedniego przechowywania i algorytmów traktowania liczb jako mniejszych części. Załóżmy, że masz kompilator, w którym a intmoże wynosić tylko od 0 do 99 i chcesz obsługiwać liczby do 999999 (będziemy się tutaj martwić tylko o liczby dodatnie, aby było to proste).

Robisz to, dając każdej cyfrze trzy intsi używając tych samych zasad, których (powinieneś) nauczyć się w szkole podstawowej, dotyczących dodawania, odejmowania i innych podstawowych operacji.

W bibliotece o dowolnej precyzji nie ma stałego limitu liczby typów podstawowych używanych do reprezentowania naszych liczb, tylko tyle, ile może pomieścić pamięć.

Dodatek na przykład 123456 + 78:

12 34 56
      78
-- -- --
12 35 34

Praca od najmniej znaczącego końca:

• początkowe przeniesienie = 0.
• 56 + 78 + 0 noszenia = 134 = 34 z 1 noszeniem
• 34 + 00 + 1 przeniesienie = 35 = 35 z 0 przeniesieniem
• 12 + 00 + 0 przeniesienia = 12 = 12 z 0 przeniesieniem

Tak właśnie działa dodawanie na poziomie bitów wewnątrz procesora.

Odejmowanie jest podobne (używając odejmowania typu podstawowego i pożyczania zamiast przenoszenia), mnożenie można wykonać za pomocą powtarzających się dodawań (bardzo wolno) lub iloczynów krzyżowych (szybciej), a dzielenie jest trudniejsze, ale można to zrobić poprzez przesuwanie i odejmowanie liczb zaangażowany (długi podział, którego nauczyłeś się jako dziecko).

Właściwie napisałem biblioteki, aby robić tego rodzaju rzeczy, używając maksymalnych potęg dziesięciu, które można dopasować do liczby całkowitej do kwadratu (aby zapobiec przepełnieniu podczas mnożenia dwóch ints, takich jak 16-bitowe intograniczenie od 0 do 99 do generuje 9,801 (<32768) po intpodniesieniu do kwadratu lub 32-bitowe, używając od 0 do 9 999, aby wygenerować 99 980 001 (<2 147 483 648)), co znacznie uprościło algorytmy.

Kilka sztuczek, na które trzeba uważać.

1 / Podczas dodawania lub mnożenia liczb przydziel wstępnie maksymalną potrzebną przestrzeń, a następnie zmniejsz ją później, jeśli uznasz, że jest za dużo. Na przykład dodanie dwóch 100-cyfrowych intliczb (gdzie cyfra jest ) nigdy nie da więcej niż 101 cyfr. Pomnożenie 12-cyfrowej liczby przez 3-cyfrową liczbę nigdy nie wygeneruje więcej niż 15 cyfr (dodaj liczbę cyfr).

2 / Aby zwiększyć szybkość, normalizuj (zmniejsz ilość wymaganej pamięci) tylko wtedy, gdy jest to absolutnie konieczne - moja biblioteka miała to jako oddzielne wezwanie, aby użytkownik mógł zdecydować między szybkością a kwestiami dotyczącymi pamięci.

3 / Dodawanie liczby dodatniej i ujemnej jest odejmowaniem, a odejmowanie liczby ujemnej jest tym samym, co dodawanie równoważnej liczby dodatniej. Możesz zaoszczędzić sporo kodu, wywołując nawzajem metody add i subtract po dostosowaniu znaków.

4 / Unikaj odejmowania dużych liczb od małych, ponieważ niezmiennie otrzymujesz liczby takie jak:

         10
         11-
-- -- -- --
99 99 99 99 (and you still have a borrow).

Zamiast tego odejmij 10 od 11, a następnie zaneguj to:

11
10-
--
 1 (then negate to get -1).

Oto komentarze (zamienione na tekst) z jednej z bibliotek, dla których musiałem to zrobić. Sam kod jest niestety objęty prawem autorskim, ale możesz wybrać wystarczającą ilość informacji, aby obsłużyć cztery podstawowe operacje. Zakładamy, w następstwie tego -ai -breprezentują liczby ujemne, a ai bto zero lub liczby dodatnie.

Dla Dodatkowo , jeśli objawy są różne, zastosowanie odejmowanie negacji:

-a +  b becomes b - a
 a + -b becomes a - b

Do odejmowania , jeśli znaki są różne, użyj dodania negacji:

 a - -b becomes   a + b
-a -  b becomes -(a + b)

Również specjalna obsługa zapewniająca odejmowanie małych liczb od dużych:

small - big becomes -(big - small)

Mnożenie wykorzystuje matematykę dla początkujących w następujący sposób:

475(a) x 32(b) = 475 x (30 + 2)
               = 475 x 30 + 475 x 2
               = 4750 x 3 + 475 x 2
               = 4750 + 4750 + 4750 + 475 + 475

Sposób, w jaki to jest osiągane, polega na wyodrębnieniu każdej z cyfr 32 po jednej naraz (wstecz), a następnie użyciu funkcji add do obliczenia wartości, która ma zostać dodana do wyniku (początkowo zero).

ShiftLefta ShiftRightoperacje są używane do szybkiego mnożenia lub dzielenia a LongIntprzez wartość zawijania (10 dla "prawdziwej" matematyki). W powyższym przykładzie 2 razy dodajemy 475 do zera (ostatnia cyfra 32), aby uzyskać 950 (wynik = 0 + 950 = 950).

Następnie przesuwamy w lewo 475, aby uzyskać 4750, i prawe przesunięcie 32, aby uzyskać 3. Dodaj 4750 do zera 3 razy, aby uzyskać 14250, a następnie dodaj do wyniku 950, aby uzyskać 15200.

Przesunięcie w lewo 4750, aby uzyskać 47500, przesunięcie w prawo 3, aby uzyskać 0. Ponieważ 32 przesunięte w prawo wynosi teraz zero, skończyliśmy i faktycznie 475 x 32 równa się 15200.

Dzielenie jest również trudne, ale opiera się na wczesnej arytmetyce (metoda „gazinty” dla „idzie w”). Rozważ następujący długi podział dla 12345 / 27:

       457
   +-------
27 | 12345    27 is larger than 1 or 12 so we first use 123.
     108      27 goes into 123 4 times, 4 x 27 = 108, 123 - 108 = 15.
     ---
      154     Bring down 4.
      135     27 goes into 154 5 times, 5 x 27 = 135, 154 - 135 = 19.
      ---
       195    Bring down 5.
       189    27 goes into 195 7 times, 7 x 27 = 189, 195 - 189 = 6.
       ---
         6    Nothing more to bring down, so stop.

Dlatego 12345 / 27jest 457z resztą 6. Zweryfikować:

  457 x 27 + 6
= 12339    + 6
= 12345

Jest to realizowane za pomocą zmiennej draw-down (początkowo zero), aby obniżyć segmenty 12345 pojedynczo, aż będzie większa lub równa 27.

Następnie po prostu odejmujemy od tego 27, aż uzyskamy poniżej 27 - liczba odejmowań to odcinek dodany do górnej linii.

Kiedy nie ma już segmentów do obalenia, mamy swój wynik.

Pamiętaj, że są to dość podstawowe algorytmy. Jeśli twoje liczby będą szczególnie duże, są znacznie lepsze sposoby wykonywania skomplikowanych działań arytmetycznych. Możesz zajrzeć do czegoś w rodzaju biblioteki arytmetycznej GNU Multiple Precision - jest znacznie lepsza i szybsza niż moje własne biblioteki.

Ma raczej niefortunną wadę, ponieważ po prostu wyjdzie, jeśli zabraknie jej pamięci (moim zdaniem, raczej fatalna wada dla biblioteki ogólnego przeznaczenia), ale jeśli możesz spojrzeć poza to, jest całkiem niezły w tym, co robi.

Jeśli nie możesz go użyć ze względów licencyjnych (lub ponieważ nie chcesz, aby Twoja aplikacja została zamknięta bez wyraźnego powodu), możesz przynajmniej pobrać stamtąd algorytmy do integracji z własnym kodem.

Odkryłem również, że osoby z MPIR (rozwidlenia GMP) są bardziej podatne na dyskusje na temat potencjalnych zmian - wydają się bardziej przyjazne dla programistów.

Ponowne wynalezienie koła jest niezwykle dobre dla twojego osobistego rozwoju i nauki, ale jest to również niezwykle duże zadanie. Nie chcę cię odradzać, ponieważ jest to ważne ćwiczenie, które wykonałem samodzielnie, ale powinieneś mieć świadomość, że w pracy występują subtelne i złożone problemy, które dotyczą większych pakietów.

Na przykład mnożenie. Naiwnie, możesz pomyśleć o metodzie „uczniowskiej”, tj. Napisz jedną liczbę nad drugą, a następnie wykonaj długie mnożenie, tak jak nauczyłeś się w szkole. przykład:

      123
    x  34
    -----
      492
+    3690
---------
     4182

ale ta metoda jest bardzo powolna (O (n ^ 2), gdzie n to liczba cyfr). Zamiast tego, nowoczesne pakiety bignum używają dyskretnej transformaty Fouriera lub transformacji numerycznej, aby przekształcić ją w zasadniczo operację O (n ln (n)).

Dotyczy to tylko liczb całkowitych. Kiedy wchodzisz w bardziej skomplikowane funkcje na jakiejś rzeczywistej reprezentacji liczby (log, sqrt, exp itp.), Sprawy stają się jeszcze bardziej skomplikowane.

Jeśli chcesz mieć podstawy teoretyczne, gorąco polecam przeczytanie pierwszego rozdziału książki Yap, „Fundamental Problems of Algebra Algebra” . Jak już wspomniano, biblioteka gmp bignum to doskonała biblioteka. W przypadku liczb rzeczywistych użyłem mpfr i podobało mi się.

Nie odkrywaj na nowo koła: może się okazać, że jest kwadratowe!

Użyj biblioteki innej firmy, takiej jak GNU MP , która jest wypróbowana i przetestowana.

Robisz to w zasadzie w taki sam sposób, jak za pomocą ołówka i papieru ...

• Liczba ma być reprezentowana w buforze (tablicy), który może przyjąć dowolny rozmiar (co oznacza użycie malloci realloc) w razie potrzeby
• implementujesz podstawową arytmetykę tak często, jak to możliwe, używając struktur obsługiwanych przez język i zajmujesz się przenoszeniem i przenoszeniem punktu radix ręcznie
• Przeszukujesz teksty analiz numerycznych, aby znaleźć skuteczne argumenty przemawiające za bardziej złożonymi funkcjami
• wdrażasz tylko tyle, ile potrzebujesz.

Zwykle będziesz używać podstawowej jednostki obliczeniowej

• bajty zawierające 0-99 lub 0-255
• 16-bitowe słowa zawierające więdną 0-9999 lub 0-65536
• 32-bitowe słowa zawierające ...
• ...

zgodnie z twoją architekturą.

Wybór bazy binarnej lub dziesiętnej zależy od twoich pragnień dotyczących maksymalnej wydajności miejsca, czytelności dla ludzi i obecności braku obsługi matematyki Binary Coded Decimal (BCD) na twoim chipie.

Możesz to zrobić z matematyką na poziomie szkoły średniej. Chociaż w rzeczywistości używane są bardziej zaawansowane algorytmy. Na przykład, aby dodać dwie liczby 1024-bajtowe:

unsigned char first[1024], second[1024], result[1025];
unsigned char carry = 0;
unsigned int  sum   = 0;

for(size_t i = 0; i < 1024; i++)
{
    sum = first[i] + second[i] + carry;
    carry = sum - 255;
}

wynik będzie musiał być większy o one placew przypadku dodawania, aby zadbać o maksymalne wartości. Spójrz na to :

9
   +
9
----
18

TTMath to świetna biblioteka, jeśli chcesz się uczyć. Jest zbudowany przy użyciu C ++. Powyższy przykład był głupi, ale tak ogólnie odbywa się dodawanie i odejmowanie!

Dobrą referencją na ten temat jest złożoność obliczeniowa operacji matematycznych . Informuje, ile miejsca potrzeba na każdą operację, którą chcesz zaimplementować. Na przykład, jeśli masz dwie N-digitliczby, musisz 2N digitszapisać wynik mnożenia.

Jak powiedział Mitch , zdecydowanie nie jest to łatwe zadanie do wykonania! Jeśli znasz C ++, polecam przyjrzeć się TTMath.

Jednym z ostatecznych odniesień (IMHO) jest tom II TAOCP Knutha. Wyjaśnia wiele algorytmów do przedstawiania liczb i operacji arytmetycznych na tych reprezentacjach.

@Book{Knuth:taocp:2,
   author    = {Knuth, Donald E.},
   title     = {The Art of Computer Programming},
   volume    = {2: Seminumerical Algorithms, second edition},
   year      = {1981},
   publisher = {\Range{Addison}{Wesley}},
   isbn      = {0-201-03822-6},
}

Zakładając, że chcesz sam napisać duży kod całkowitoliczbowy, może to być zaskakująco proste, mówiąc jak ktoś, kto zrobił to niedawno (choć w MATLAB-ie). Oto kilka sztuczek, których użyłem:

• Zapisałem każdą pojedynczą cyfrę dziesiętną jako liczbę podwójną. Ułatwia to wiele operacji, zwłaszcza drukowanie. Chociaż zajmuje więcej miejsca, niż byś sobie życzył, pamięć jest tutaj tania i sprawia, że ​​mnożenie jest bardzo wydajne, jeśli możesz wydajnie splatać parę wektorów. Alternatywnie, możesz zapisać kilka cyfr dziesiętnych w podwójnym, ale uważaj wtedy, że splot w celu wykonania mnożenia może powodować problemy numeryczne na bardzo dużych liczbach.

• Przechowuj nieco znak osobno.

• Dodanie dwóch liczb polega głównie na dodaniu cyfr, a następnie sprawdzeniu przeniesienia na każdym kroku.

• Mnożenie pary liczb najlepiej wykonywać jako splot, po którym następuje krok przenoszenia, przynajmniej jeśli masz szybki kod splotu.

• Nawet jeśli przechowujesz liczby jako ciąg pojedynczych cyfr dziesiętnych, można wykonać dzielenie (również operacje mod / rem), aby uzyskać w wyniku około 13 cyfr dziesiętnych naraz. Jest to znacznie wydajniejsze niż dzielenie, które działa tylko na 1 cyfrze dziesiętnej naraz.

• Aby obliczyć całkowitą potęgę liczby całkowitej, oblicz binarną reprezentację wykładnika. Następnie użyj powtarzających się operacji do kwadratu, aby obliczyć wymagane potęgi.

• Wiele operacji (faktoring, testy pierwszorzędności itp.) Odniesie korzyści z operacji na module powermod. Oznacza to, że kiedy obliczasz mod (a ^ p, N), zmniejsz wynikowy mod N na każdym kroku potęgowania, w którym p zostało wyrażone w postaci binarnej. Nie obliczaj najpierw ^ p, a następnie spróbuj zmniejszyć go mod N.

Oto prosty (naiwny) przykład, który zrobiłem w PHP.

Zaimplementowałem "Dodaj" i "Pomnóż" i użyłem tego jako przykładu wykładnika.

http://adevsoft.com/simple-php-arbitrary-precision-integer-big-num-example/

Fragment kodu

// Add two big integers
function ba($a, $b)
{
    if( $a === "0" ) return $b;
    else if( $b === "0") return $a;

    $aa = str_split(strrev(strlen($a)>1?ltrim($a,"0"):$a), 9);
    $bb = str_split(strrev(strlen($b)>1?ltrim($b,"0"):$b), 9);
    $rr = Array();

    $maxC = max(Array(count($aa), count($bb)));
    $aa = array_pad(array_map("strrev", $aa),$maxC+1,"0");
    $bb = array_pad(array_map("strrev", $bb),$maxC+1,"0");

    for( $i=0; $i<=$maxC; $i++ )
    {
        $t = str_pad((string) ($aa[$i] + $bb[$i]), 9, "0", STR_PAD_LEFT);

        if( strlen($t) > 9 )
        {
            $aa[$i+1] = ba($aa[$i+1], substr($t,0,1));
            $t = substr($t, 1);
        }

        array_unshift($rr, $t);
     }

     return implode($rr);
}