Algorytm Karatsuby

Z Wikipedii

Algorytm Karatsuby - algorytm szybkiego mnożenia dużych liczb całkowitych, opracowany przez A. Karatsubę w 1960 i opublikowany razem z Yu. Ofmanem w 1962 roku. Jego złożoność obliczeniowa wynosi Θ. Jest to lepszy rezultat od algorytmu klasycznego Θ(n²), chociaż dla niewielkich liczb jest mniej praktyczny.

Spis treści 1 Algorytm 2 Przykład 3 Złożoność 4 Przypisy 5 Linki zewnętrzne

[edytuj] Algorytm

Do pomnożenia dwóch n-cyfrowych liczb x i y przy podstawie B, gdzie n=2m (jeśli n jest nieparzyste, albo x ma różną liczbę cyfr niż y, można to naprawić dodając zera po lewej stronie tych liczb), rozpisujemy je jako:

x = x₁ B^m + x₂

y = y₁ B^m + y₂

gdzie x₂ i y₂ są mniejsze niż B^m. Wynik mnożenia wynosi wtedy:

xy = (x₁B^m + x₂)(y₁B^m + y₂)

= x₁y₁B^2m + (x₁y₂ + x₂y₁)B^m + x₂y₂

Standardową metodą byłoby pomnożenie czterech czynników osobno i dodanie ich po odpowiednim przesunięciu. Daje to algorytm działający w czasie O(n²). Karatsuba zauważył że możemy ten sam wynik uzyskać wykonując tylko trzy mnożenia:

X = x₁y₁

Y = x₂y₂

Z = (x₁ + x₂)(y₁ + y₂) - X - Y

Dostajemy wtedy

Z = (x₁y₁ + x₁y₂ + x₂y₁ + x₂y₂) - x₁y₁ - x₂y₂

= x₁y₂ + x₂y₁

A zatem xy = X B^2m + Y + Z B^m; tym samym kosztem kilku dodawań i odejmowań zmniejszyliśmy liczbę mnożeń z czterech do trzech.

Każde z tych mnożeń m-cyfrowych liczb możemy znów wykonać za pomocą algorytmu Karatsuby, wykorzystując rekurencję.

[edytuj] Przykład

Chcemy policzyć iloczyn liczb 1234 i 5678. W tym wypadku B = 10 i m = 2. Mamy

12 34 = 12 ⋅ 10² + 34

56 78 = 56 ⋅ 10² + 78

X = 12 ⋅ 56 = 672

Y = 34 ⋅ 78 = 2652

Z = (12 + 34)(56 + 78) - X - Y = 46 ⋅ 134 - 672 - 2652 = 2840

X 10^2⋅2 + Y + Z 10² = 672 0000 + 2652 + 2840 00 = 7006652 = 1234 ⋅ 5678

[edytuj] Złożoność

Niech T(n) oznacza liczbę operacji potrzebnych do pomnożenia dwóch n-cyfrowych liczb za pomocą algorytmu Karatsuby. Dostajemy równanie rekurencyjne:

T(n) = 3 T(n/2) + cn + d

dla pewnych stałych c i d. Jego rozwiązaniem jest funkcja rzędu Θ(n^{log(3)/log(2)}).

log(3)/log(2) wynosi w przybliżeniu 1.585, a więc dla dużych n funkcja ta ma mniejszą wartość od funkcji kwadratowej. Z powodu kosztów wywołań rekurencyjnych algorytm ten nie jest opłacalny dla małych n. Zwykle przyjmuje się że zaczyna być on opłacalny dla liczb kilkusetbitowych.

Pomysł dzielenia czynników na mniejsze części można uogólnić. Dzieląc każdy z czynników na 3 fragmenty, można zamiast 9 mnożeń wykonać 5, osiągając algorytm o złożoności Θ(n^{log(5)/log(3)}). Dalsze zwiększanie liczby części również daje pewien zysk (kosztem znacznego skomplikowania algorytmu), ale jeszcze lepsze wyniki można uzyskać wykorzystując szybką transformatę Fouriera. Daje to najszybszy znany algorytm mnożenia - algorytm Schönhage-Strassena, który jest stosowany do mnożenia liczb złożonych z dziesiątek tysięcy bitów.

[edytuj] Przypisy

• A. Karatsuba and Yu Ofman, "Multiplication of Many-Digital Numbers by Automatic Computers." Doklady Akad. Nauk SSSR Vol. 145 (1962), pp. 293–294. Translation in Physics-Doklady 7 (1963), pp. 595–596.
• Karacuba A. A. Berechnungen und die Kompliziertheit von Beziehungen (German) // Elektron. Informationsverarb. Kybernetik, 11, 603–606 (1975).
• Karatsuba A. A. The complexity of computations // Proc. Steklov Inst. Math., 211, 169–183 (1995); translation from Trudy Mat. Inst. Steklova, 211, 186–202 (1995).
• Knuth D. E. The Art of Computer Programming. v.2 Addison-Wesley Publ.Co., 724 pp., Reading (1969).
• Karatsuba Multiplication on MathWorld
• Bernstein, D. J., "Multidigit multiplication for mathematicians". Covers Karatsuba and many other multiplication algorithms.
• Karatsuba Multiplication on Fast Algorithms and the FEE

[edytuj] Linki zewnętrzne

• przykład implementacji w Delphi