Zajęcia 7: liczby całkowite i rzeczywiste

Liczby całkowite

Wyczerpujący tutorial na ten temat autorstwa Miso Foriska można znaleźć w serwisie TopCoder. Na zajęciach nie wchodziliśmy w to aż tak dokładnie.

Liczby rzeczywiste

Tym razem odwoływaliśmy się do końcówki ww. tutorialu, a także do jego drugiej części.

Mnożenie liczb całkowitych

Czasem musimy użyć liczb całkowitych o większym zakresie niż wbudowane 64-bitowe czy tam 128-bitowe. Wtedy trzeba się posłużyć implementacją liczb całkowitych z dużego zakresu. Łatwiej jest, jeśli możemy posłużyć się językiem programowania, w którym to jest gotowe (np. Java). Jeśli nie, to czeka nas przyjemność implementacji własnej arytmetyki wielkich liczb. Więcej na ten temat można przeczytać w kursie algorytmiki na MAIN-ie, patrz także druga część tej lekcji. Na zajęciach nie wchodziliśmy w to tak głęboko, tylko zajęliśmy się problemem mnożenia dużych liczb, reprezentowanych jako ciągi cyfr o podstawie M, np. M=10⁸. Są co najmniej cztery takie algorytmy:

• mnożenie pisemne: czas mnożenia liczb długości n to O(n²);
• mnożenie rosyjskich chłopów: czas to także O(n²);
• mnożenie Karatsuby: czas O(n^log₂3) ≈ O(n^1.58);
• algorytm FFT, szybka transformata Fouriera: czas O(n ⋅ log(n)).

Opisy i przykładowe implementacje pierwszych trzech z powyższych algorytmów można znaleźć w podanych już odnośnikach do MAIN-a: mnożenie pisemne w pierwszej części lekcji, a mnożenie rosyjskich chłopów i mnożenie Karatsuby w drugiej części. Z kolei algorytm FFT i jego zastosowania są podane w wykładzie Tomka Idziaszka na WAS-ie. Jeśli musielibyśmy rzeczywiście zaimplementować jakiś algorytm mnożenia pisemnego, to tak: Mnożenie pisemne jest najprostsze koncepcyjnie, niezbyt miłe w zapisie, ale dosyć efektywne. Mnożenie rosyjskich chłopów jest trochę wolniejsze niż pisemne (koszt czasowy zależy od iloczynu długości jednej liczby w zapisie przy podstawie M, ale druga jest brana przy podstawie 2), ale proste w implementacji, jeśli mamy zaimplementowane proste operacje, takie jak dodawanie oraz mnożenie i dzielenie przez 2. Jeśli potrzebujemy czegoś naprawdę efektywnego, to mnożenia Karatsuby nie należy raczej implementować, lepiej od razu użyć algorytmu FFT. Algorytm FFT ma niestety dosyć dużą stałą (używa się liczb zespolonych implementowanych z użyciem long double), działa rozsądnie dla liczb w okolicach 10⁵ – trzeba pamiętać, że uzupełniamy zapisy dziesiętne tak, żeby były potęgami dwójki, a ze względu na ograniczoną dokładność typów rzeczywistych za podstawę możemy przyjąć maksymalnie M=10⁶.

W kontekście tych zajęć warto wspomnieć o zastosowaniu algorytmu mnożenia rosyjskich chłopów do mnożenia liczb wbudowanego typu. Powiedzmy, że dla dwóch liczb 64-bitowych a i b chcemy obliczyć ich iloczyn modulo pewna liczba 64-bitowa p. Wiadomo, że wynik zmieści się w typie 64-bitowym, ale wynik mnożenia a * b nie mieści się już w tym typie. Jeśli nie zależy nam jakoś strasznie na efektywności, możemy wykorzystać mnożenie rosyjskich chłopów, w którym liczba operacji będzie rzędu 64:

long long mnoz(long long a, long long b, long long p) {
  long long w = 0;
  while (b) {
    if (b % 2 == 1)
      w = (w + a) % p;
    b /= 2;
    a = (2 * a) % p;
  }
  return w;
}

Zadanie domowe

Zadanie domowe: zadanie Zagroda na ASD-SIO.