Natürlich können wir statt der Basis 10 des hier verwendeten Stellenwertsystems eine beliebige andere Basis wählen. Wenn wir 10 durch 2 ersetzen, bekommen wir:

def Mult2(a, b):
    p = 0
    while a > 0:
        p += (a % 2) * b
        a //= 2
        b *= 2
    return p

print(Mult2(102, 5))    

Jetzt nutzen wir die Tatsache, dass es im Binärsystem nur zwei Ziffern (0 und 1) gibt und optimieren die gelb unterlegte Zeile. a % 2 ist entweder 0 (dann brauchen wir zu p nichts zu addieren oder 1 (dann müssen wir 1 · b addieren). Damit ergibt sich:

def Mult2(a, b):
    p = 0
    while a > 0:
        if a % 2 == 1:
            p += b
        a //= 2
        b *= 2
    return p

print(Mult2(102, 5))    

Daraus ergibt sich das praktische Verfahren, das u.a. als russische Bauernmultiplikation bekannt ist: Wir halbieren a und verdoppeln b, solange a > 0. Alle b-Werte, bei denen a ungerade ist werden aufaddiert:

 a      b
─────────
102     5
 51    10
 25    20
 12    40
  6    80
  3   160
  1   320
─────────
      510

Dieses Verfahren lässt sich auch sehr effizient implementieren. Da auf dem Computer Zahlen binär dargestellt sind, lassen sich die Verdoppelungen bzw. Halbierungen durch Verschiebungen um ein Bit nach links bzw. rechts darstellen, die jeder Prozessor sehr schnell ausführen kann.

Fortsetzung: Parallele Multiplikation