Multiplikation

[x₀,...] ^. [y₀,...],

• Schulmethode: x₀ ^. y + tail(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: jedes Resultatbits hängt von allen Eingabebits ab.