Es wäre sicher interessant, wenn man die Anzahl der täglich weltweit von Computern durchgeführten Multiplikationen erfahren könnte. Diese Zahl dürfte sich zur Zeit wahrscheinlich irgendwo zwischen 10¹⁵ und 10²⁰ bewegen. Bei den meisten Computern benötigt die Multiplikation nur einige wenige Mikrosekunden. Die Multiplikationsschaltkreise sind bereits so optimiert, daß sie das Produkt zweier z.B. 32-Bit-Zahlen in der kürzest möglichen Zeit durchführen. Die Verfügbarkeit schneller Hardware-Lösungen für die Aufgabe, zwei 32-Bit-Zahlen zu multiplizieren, verstellt jedoch leicht den Blick auf eine sehr allgemeine Frage, die von mehr als nur theoretischer Bedeutung sein kann: Wie schnell können zwei n-Bit-Zahlen multipliziert werden? Anstatt zu versuchen, ein generalisiertes Hardware-Schema für schnelle Multiplikation zu finden, nehmen wir vielmehr an, daß alle Operationen auf der Bitebene durchgeführt werden, und versuchen dann, die kleinste Anzahl von Bit-Operationen zu bestimmen, die für die Bildung von Produkten erforderlich ist.