Karatsuba-Multiplikation

(10ⁿa + b)(10ⁿc + d )= 10²ⁿab + 10ⁿ(ad + bc) + bd

Idee: Anzahl der Multiplikationen verringern

(auf Kosten der Additionen).

Berechne ac, bd und (a + b)(c + d )= ac + (ad + bd )+ bd,

ergibt (ad + bc) = (a + b)(c + d )- ac - bd.

Statt 4 Mult und 3 Add: 3 Mult. und 7 Add/Sub.

Rechenzeit: T(n) = 3T(n/2) + c ^. n. Ansatz T(n) = n^x.

http://mathworld.wolfram.com/KaratsubaMultiplication.html