Multiplikation

[x₀,…]⋅[y₀,…] mathend000#,

• Schulmethode: x₀⋅y + 2⋅[x₁,…]⋅y mathend000# rekursiv

• Überläufe im Resultat früh erkennen, nur mit nötigen Stellen rechnen
• Karatsuba-Multiplikation:

  (p + qB)(r + sB) = pr + $\underbrace{{(ps+qr)}}_{{=t}}^{}\,$B + qsB² mathend000#

  berechne t = (p + q)(r + s) - pr - qs mathend000# mit nur 3 Multiplikationen.

SAT-Formeln für binäre Multiplikation sind sehr schwer: Resultatbit k mathend000# hängt von allen Eingabebits 0,..., k mathend000# ab.