Loading AI tools
Z Wikipedii, wolnej encyklopedii
Algorytm Karacuby – algorytm szybkiego mnożenia dużych liczb całkowitych, opracowany przez Anatolija Karacubę w 1960 i opublikowany razem z Jurijem Ofmanem w 1962[1][2][3] roku. Jego złożoność obliczeniowa wynosi Θ w przypadku mnożenia dwóch liczb składających się z n cyfr. Jest on zatem szybszy od algorytmu klasycznego dla odpowiednio dużych wartości n. Mnożenie niewielkich liczb jest szybsze przy pomocy mniej skomplikowanego algorytmu klasycznego.
Rodzaj | |
---|---|
Struktura danych | |
Złożoność | |
Czasowa |
|
Do pomnożenia dwóch -cyfrowych liczb i przy podstawie gdzie (jeśli jest nieparzyste, albo ma różną liczbę cyfr niż można to naprawić, dodając zera po lewej stronie tych liczb), rozpisujemy je jako:
gdzie i są mniejsze niż Wynik mnożenia wynosi wtedy:
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 Karacuba zauważył, że możemy ten sam wynik uzyskać, wykonując tylko trzy mnożenia:
Dostajemy wtedy
A zatem tym samym kosztem kilku dodawań i odejmowań zmniejszyliśmy liczbę mnożeń z czterech do trzech.
Każde z tych mnożeń -cyfrowych liczb możemy znów wykonać za pomocą algorytmu Karacuby, wykorzystując rekurencję.
procedure karatsuba(num1, num2)
if (num1 < 10) or (num2 < 10)
return num1 * num2
/* Obliczanie długości liczb */
n = max(size_base10(num1), size_base10(num2))
m = n / 2
/* Podział sekwencji cyfr na pół*/
high1, low1 = split_at(num1, m)
high2, low2 = split_at(num2, m)
/* 3 wywołania dla liczb o długości w przybliżeniu mniejszych o połowę */
X = karatsuba(high1, high2)
Y = karatsuba(low1, low2)
Z = karatsuba((low1 + high1), (low2 + high2)) - X - Y
return (X * 10 ^ (2 * m)) + ((Z) * 10 ^ (m)) + (Y)
Chcemy obliczyć iloczyn liczb 1234 i 5678. W tym wypadku i Mamy
Niech oznacza liczbę operacji potrzebnych do pomnożenia dwóch -cyfrowych liczb za pomocą algorytmu Karacuby. Dostajemy równanie rekurencyjne:
dla pewnych stałych i Jego rozwiązaniem jest funkcja rzędu
wynosi w przybliżeniu 1.585, a więc dla dużych funkcja ta ma mniejszą wartość od funkcji kwadratowej. Z powodu kosztów wywołań rekurencyjnych algorytm ten nie jest opłacalny dla małych 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 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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.