Karatsuba-Multiplikation

• A. Karatsuba, Yu. Ofman 1962
• (p + qB)(r + sB) = pr + (ps + qr)B + qsB²

  = pr + ((p + q)(r + s) - pq - rs)B + qsB²

• K(w) = Anzahl elementarer Operationen (Plus, Mal) für Multiplikation w-stelliger Zahlen nach diesem Verfahren

  K(1) = 1, K(w) = 3⋅K(w/2) + 5⋅w

  (eine Multiplikation weniger, drei Additionen mehr)

• asymptotisch mit Ansatz K(w) $\approx$ C⋅w^e

  C⋅w^e = 3Cw^e/2^e + 5w ⇒ 1 $\approx$ 3/2^e, also e = log₂3 $\approx$ 1.58

• explizite Werte für w = 2^k,

  ab wann besser als Schulmethode?