Rekursive Multiplikation

• anstatt „Schulmethode``: rekursive Multiplikation

  (p + qB)(r + sB) = pr + (ps + qr)B + qsB²

  Bsp. B = 100, (12 + 34⋅100)(56 + 78⋅100) = 12⋅56 + ...

  (1 + 2⋅10)(5 + 6⋅10) = 1⋅2 + ...

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

  M(1) = 1, M(w) = 4⋅M(w/2) + 2⋅w

  M(2^k) = 3⋅4^k -2^k+1, also M(w)∈Θ(w²)

• also wie bei Schulmethode, aber das läßt sich verbessern, und darauf muß man erstmal kommen