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.
Przypisy
Linki zewnętrzne
Kategoria:Algorytmy Kategoria:Działania arytmetyczne