Multiplikation

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

• Schulmethode: x₀⋅y + 2⋅[x₁,…]⋅y 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²

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

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