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ę.
Implementacja Pseudokod 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)
Przykład Chcemy obliczyć iloczyn liczb 1234 i 5678. W tym wypadku i Mamy
Złożoność 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