Ein schneller Quadrierungs - Algorithmus für Zahlensysteme mit beliebiger Basis
Übersicht
Hier wird der Panflöten-Algorithmus vorgestellt, der die Quadrierung einer Zahl mit dem halben Aufwand leistet
wie der übliche Multiplikations-Algorithmus.
Er funktioniert bei b-adischen Zahlensystemen mit beliebiger Basis.
Bei gebrochenen Zahlen entfernt man zunächst das Komma
und markiert beim Ergebnis die doppelte Anzahl Nachkommastellen.
Der Algorithmus binär
Die binäre Version ist - wie bei allen Algorithmen - besonders einfach.
Die zu quadrierende Zahl N bestehe aus dem Ziffernstring nmax ... n1n0
(in der symbolischen Darstellung links aus den Ziffern abcd)
Beispiel: Quadriere 15 = 11112:
a_b_c_d 1_1_1_1 Zeile 1: Zahl gespreizt
bcd 111 Zeile 2
cd 11 Zeile 3
d 1 Zeile 4
------- --------
Summe 11100001 Zeile 5: Summe = Ergebnis
- Zeile 1: Schreibe die zu quadrierende Zahl gepreizt hin.
Statt Nullen fügt man Unterstriche ein (übersichtlicher)
- Zeilen 2, 3, 4: Für i = imax herunter bis 1:
Falls Ziffer ni ≠ 0 :
Schreibe unter Ziffer ni den Ziffernstring ni-1 ... n0
- Zeile 5: Summiere alles (Zeilen 1 bis 4) = Ergebnis
Es folgen noch 2 Beispiele mit Nullen in der Zahl. Hier sieht man, daß beim Spreizen der Zahl Unterstriche statt Nullen übersichtlicher sind, und daß unter eine Ziffer 0 der gespreizten Zahl kein Ziffernstring geschrieben wird. Führende Nullen in einem Ziffernstring sollten geschrieben werden, damit dieser genau unter der entsprechenden Ziffer der gespreizten Zahl beginnt (optische und didaktische Klarheit). Beispiele: 23 = 101112 und 54 = 1101102 :
1_0_1_1_1 1_1_0_1_1_0
0111 10110
11 0110
1 10
--------- 0
1000010001 -----------
101101100100
Damit nicht nur der Rechenaufwand, sondern auch der Platzbedarf halbiert wird, kann man eine komprimierte Schreibweise anwenden: Man schreibt außer dem 1. Ziffernstring noch weitere Ziffernstrings in die 2. Zeile (oder eine andere), wenn dort Platz ist, was spätestens nach Abarbeiten der (abgerundet) halben Ziffernzahl der Fall ist. Obige Beispiele komprimiert:
1_0_1_1_1 1_1_0_1_1_0
0111111 10110 100
--------- 0110
1000010001 -----------
101101100100
Für Anfänger ist die komprimierte Schreibweise nicht zu empfehlen,
und auch Geübte sollten Ziffernstrings,
die nicht durch eine Lücke getrennt sind, durch ein Komma o.Ä. trennen.
Zum dezimalen Quadrierungs-Algorithmus
Vereinfachung bei Einserblocks
Eine Folge von x Einsen in der zu quadrierenden Zahl würde nach obigem Algorithmus
x zu addierende Teilstrings der Zahl erzeugen. Es geht jedoch einfacher.
Beispiel: Quadriere 2037 = 11111110101
1_1_1_1_1_1_1_0_1_0_1 Zahl gespreizt, streiche Einsen
1111110101 erster Teilstring 1 nach links
-0101 -letzter Teilstring minus
01
----------------------
1111110101000001111001 Summe = Ergebnis
Der Einserblock erfährt eine Sonderbehandlung:
-- Schreibe den durch die erste 1 erzeugten Teilstring um 1 weiter links
-- (alle inneren Einsen des Blocks erzeugen nichts)
-- setze vor den durch die letzte 1 erzeugten Teilstring ein Minuszeichen
(incl. Minuszeichen beginnt also auch dieser String um 1 weiter links)
-- streiche in der gespreizten Zahl alle Einsen des Blocks außer der ganz rechts
(d.h. diese werden nicht addiert)
Diese Vereinfachung kann man auf jeden Einserblock in einer Zahl anwenden -
oder nur auf einige: Die Zahl der zu addierenden / subtrahierenden Ziffern ist zwar schon
bei dem Block 11 geringer, aber der Algoritmus ist etwas komplizierter (Addition und Subtraktion).
Ab dem Block 111 lohnt sich die Vereinfachung sicher. Bei obigem Beispiel mit einem Block aus 7 Einsen
werden nur 2 statt 7 Teilstrings erzeugt und verrechnet
Diese Methode ähnelt dem Booth-Algorithmus für 1-er Folgen bei der binären Multiplikation
Besonders einfach ist so die Quadrierung einer Zahl, die nur aus einem Einserblock besteht.
Quadriere 15 = 11112:
1_1_1_1 1_1_1_1
111 11100001
--------
11100001 komprimiert
Der durch die letzte Eins erzeugte, zu subtrahierende Teilstring ist hier leer, man schreibt nichts.
Man addiert nur 2 Dinge:
- den durch die erste 1 erzeugten Teilstring (um 1 nach links verschoben!)
- die rechteste 1 der gespreizten Zahl
Einfacher formuliert: Um eine Binärzahl zu quadrieren, die nur aus x Einsen besteht,
fügt man vor der letzten Eins x Nullen ein. Die Quadratzahl besteht somit aus x Einsen und x Nullen.
Noch einfacher ist die bekannte Regel, wie man eine runde Zahl (1 gefolgt von x Nullen)
in einem beliebigen "normalen" Zahlensystem quadriert: Man verdoppelt einfach die Anzahl der Nullen.
Man kann auch hier eine Art komprimierte Schreibweise anwenden (Bild rechts):
Man schreibt die rechte 1 nochmal in Zeile 2, füllt den Zwischenraum mit Nullen (rot) und hat schon das Ergebnis
Herleitung
Wir zeigen an einem Beispiel die theoretische Grundlage. Gegeben sei eine 4-stellige natürliche Zahl N zur Basis b:
N = n3n2n1n0
= ( n3*b3 + n2*b2 +
n1*b1 + n0*b0 )
Will man diese Zahl quadrieren, muss man - nach den üblichen Klammerregeln -
jedes Element der Klammer mit jedem Element der Klammer (incl. sich selbst) multiplizieren.
Nach Umsortieren und geeignetem Zusammenfassen erhält man:
N2 = n32*b6 + n22*b4 + n12*b2 + n02*b0 Jede Ziffer samt Stellenwert quadriert
+ 2n3 * ( n2*b5 + n1*b4 + n0*b3 )
+ 2n2 * ( n1*b3 + n0*b2 )
+ 2n1 * ( n0*b1 )
Dieses Schema funktioniert bei mehr Ziffern genauso: Hat man 1 Ziffer mehr, so müßte man statt n2
Produkten von je 2 Ziffern (n=Ziffernzahl) jetzt (n+1)2 = n2 + 2n + 1 Produkte von je 2 Ziffern haben.
Und die hat man, neu hinzu kommen nämlich 1 neue quadrierte Ziffer (in obiger Formel nach dem Gleichheitszeichen einzufügen)
und ihre 2n Produkte mit jeder anderen Ziffer (neue Zeile nach der ersten einfügen, analog zur 2. Zeile).
Der binäre Algorihmus läßt sich noch weiter vereinfachen:
- Es gibt nur die Ziffern 0 und 1, und es gilt 0x = 0 und 1x = 1
Man kann also in der oberen Zeile bei den Ziffern n3 bis
n0 die Exponenten 2 weglassen
- Dann kann man die obere Zeile zu einer Zahl (N gespreizt) zusammenfassen
(die Exponenten bi werden durch die Stellenwerte ausgedrückt), also:
n3 0 n2 0 n1 0 n0 (7-stellige Zahl mit 3 Nullen)
- Auch die Ausdrücke in Klammern kann man zu je einer Zahl zusammenfassen
(ergibt verschieden lange Teilstrings von N) und dann noch
den Faktor 2 durch eine Erhöhung um 1 der Potenz von b ausdrücken, also:
+ n3 * ( n2n1n0*b4 ) [ aus 2n3 * ( n2n1n0*b3 ) ]
+ n2 * ( n1n0*b3 ) [ aus 2n2 * ( n1n0*b2 ) ]
+ n1 * ( n0*b2 )
[ aus 2n1 * ( n0*b1 ) ]
Die Multiplikation n3 * ( n2n1n0*b4 )
z.B. bedeutet gerade, daß der Ziffernstring n2n1n0 an die durch b4
bestimmte Stelle geschrieben wird, wenn n3 =1 ist, andernfalls nicht (weil das Ergebnis 0 ist)
Auch die Vereinfachung bei Einserblocks läßt sich leicht herleiten:
Wir berechnen das Quadrat der Zahl und vereinfachen schrittweise die Struktur des Rechenschemas.
Obiges Beispiel: Quadriere 2037 = 11111110101
Schritt 0: Berechne das Quadrat ohne Vereinfachung. Die durch den Einserblock erzeugten
7 Strings sind farblich unterteilt, um die Umgruppierung beim nächsten Schritt klarer zu machen:
1_1_1_1_1_1_1_0_1_0_1
1111110101
111110101
11110101
1110101
110101
10101
0101
01
----------------------
1111110101000001111001
Schritt 1: Die Einsen des Einerblocks in jedem Teilstring werden anders gruppiert. Man erkennt das System: Je zwei Einsen (und zuletzt eine Rest-Eins) ergeben einen fortlaufenden Einser-String. Die Einser-Srings werden links und rechts um je 2 Stellen kürzer:
111
1111111
11111111111
Schritt 2: Jede Zeile von x Einsen wird durch den Ausdruck 2x-1 ersetzt (z.B. 111 durch 23-1 = 1000-1). Zur Vereinfachung lassen wir die Nullen weg, schreiben aber jede 1 und -1 natürlich stellenrichtig (d.h. jede positive 1 um eine Stelle weiter nach links als die erste 1 des Blocks):
1 -1
1 -1
1 -1
Schritt 3: Wir fassen alle 1 und -1 des obigen Schemas in 1 Zeile zusammen:
1 1 1 -1-1-1
Schritt 4: Die Reste 0101 der Teilstrings sind um je 1 Stelle verschoben, ergeben also den Wert 0101*1111111. Dieser Ausdruck wird ersetzt durch 0101*(10000000-1), was 01010000000-1 ergibt. Zur Vereinfachung lassen wir die Nullen weg, schreiben aber die 0101 und -0101 natürlich stellenrichtig (d.h. die 0101 um eine Stelle weiter nach links als die erste 0101 des Blocks):
0101 -0101
Schritt 5: Wir ersetzen im Gesamtschema (Schritt 0) die 7 durch den Einserblock erzeugten Teilstrings durch die in Schritt 2 und 4 gewonnenen Ausdrücke. (Der schwarze Teilstring 01 hat mit dem Einserblock und dessen Vereinfachung nichts zu tun, sondern wird durch die zweitletzte 1 der gespreizten Zahl erzeugt):
1_1_1_1_1_1_1_0_1_0_1
1 1 1 -1-1-1
0101 -0101
01
----------------------
1111110101000001111001
Schritt 6: Wir verrechnen den grünen Teilstring mit der gespreizten Zahl
und schreiben den roten Teilstring in dieselbe Zeile. Nun haben wir gerade das vereinfachte Schema.
(Der negative Teilstring, hier -0101, überlappt sich manchmal mit dem positiven Teilstring,
abhängig von der zu quadrierenden Zahl, und muß dann in die nächste Zeile geschrieben werden):
1_1_1_1_1_1_1_0_1_0_1
1111110101 -0101
01
----------------------
1111110101000001111001
Aufwand
- Bei Quadrierung mit dem üblichen Multiplikationsalgorithmus müssen bei einer Zahl
mit n Stellen maximal n Zahlen mit je n Einsen addiert werden, also insgesamt n2 Ziffern
- Bei Quadrierung mit dem hier gezeigten Algorithmus müssen die gepreizte Zahl mit max. n Einsen
sowie maximal n-1 Zahlen mit durchschnittlich (n-1)/2 Ziffern addiert werden.
Zusammen also (n-1)2/2 + n = (n2 - 2n + 1 + 2n) /2 also etwa n2/2 Ziffern
Man hat also nur den halben Aufwand
(Durch die oben beschriebene Vereinfachung bei 1-er Blocks kann der absolute Aufwand sehr viel geringer werden,
aber das gilt auch für die übliche binäre Mutliplikation mit Vereinfachung durch den Booth-Algorithmus)
Potenzierung
Der schnelle Quadrierungs-Algorithmus macht auch die Berechnung höherer Potenzen schneller.
Denn es ist üblich, z.B. zur Berechnung von N8 so vorzugehen:
- Berechne N2
- Berechne N4 aus N2 * N2
- Berechne N8 aus N4 * N4
Allgemein setzt man jede beliebige Potenz aus kleineren Potenzen so zusammen,
daß der Rechenaufwand minimal wird.
Ähnlichkeit mit Quadratwurzel-Algorithmus
Zwischen Quadrierungs- und Quadratwurzel-Algorithmus gibt es gewisse Analogien:
- Beim ersteren werden aus jeder Ziffer (außer der letzten) 2 Ziffernstellen,
beim letzteren werden aus je 2 Ziffern (außer ggf. der ersten) eine
- Beim ersteren werden mit 2 multiplizierte Summanden addiert, beim letzteren subtrahiert
Der Quadrierungs-Algorithmus hat auch eine Analogie mit der Bildung der n-ten Quadratzahl
als Summe der ersten n ungeraden Zahlen ( 12 = 1 , 22 = 1 + 3 , 32 = 1 + 3 + 5 , ... ), denn:
- Beide Methoden summieren größenmäßig gestaffelte, einander enthaltende Zahlen
Linker-Rest-Version
Es gibt obigen Quadrierungs-Algorithmus auch in einer ähnlichen Version,
die statt den rechten den linken Reststring jeder Ziffer summiert.
Man kann nämlich (s.o. Abschnitt "Herleitung") die Summanden auch so zusammenfassen: (1. Zeile unverändert)
N2 = n32*b6 + n22*b4 + n12*b2 + n02*b0 Jede Ziffer samt Stellenwert quadriert
+ ( n3*b3 + n2*b2 + n1*b1) * 2n0
+ ( n3*b4 + n2*b3 ) * 2n1
+ ( n3*b5 ) * 2n2
Daraus ergibt sich folgendes Rechenschema:
a_b_c_d 1_1_1_1 Zeile 1: Zahl gespreizt
abc 111 Zeile 2
ab 11 Zeile 3
a 1 Zeile 4
------- --------
Summe 11100001 Zeile 5: Summe = Ergebnis
- Zeile 1: Schreibe die zu quadrierende Zahl gepreizt hin.
Statt Nullen fügt man Unterstriche ein (übersichtlicher)
- Zeilen 2, 3, 4: Für i = 0 bis imax-1:
Falls Ziffer ni ≠ 0 :
Schreibe unter Ziffer ni+1 rechtsbündig den Ziffernstring
nmax ... ni+1
- Zeile 5: Summiere alles = Ergebnis
Auch hier kann man die komprimierte Schreibweise anwenden sowie (entsprechend geändert)
die Vereinfachung bei Einserblocks. Bei Einserblocks ist der Aufwand genauso gering wie bei
der Rechter-Rest-Version, aber die Summanden müssen etwas weiter verschoben werden, so daß das
Rechenschema nicht ganz so elegant ist
Weitere Versionen
Es lassen sich weitere Versionen des binären Quadrierungsalgorithmus entwerfen:
Man kann die kurzen Teilstrings zuerst hinschreiben, die (Rechter- und Linker-Rest)
Algorithmen arbeiten dann in umgekehrter Richtung. Aber dann stehen die langen Teilstrings
nicht mehr direkt unter der gespreizten Zahl, deshalb macht man beim Addieren eher Fehler.
Möglich sind auch Versionen, die ohne die gespreizte Zahl auskommen und deren Ziffern
gleich in die Teilstrings integrieren. Doch auch diese Versionen sind unergonomischer.
Weitere Algorithmen
Nach obigem Muster (Zifferndarstellung ausmultiplizieren, geeignet zusammenfassen,
praktisches Verfahren und ergonomische Schreibweise finden) lassen sich
weitere Algorithmen entwerfen, z.B.:
- schnelle Kubierung (Berechnung von N3 )
Die Zahl N wird hier stärker gespreizt (je 2 Ziffenzwischenräume),
man hat ein Mehrfaches an Summanden, und die Faktoren 3 oder 6 statt 2
- schnelle Wurzelberechnung
- verschiedene Multiplikationsalgorithmen
Geschichte
Obiger Algorithmus wurde von mir entwickelt. Es ist aber kaum vorstellbar, daß nicht schon andere Leute ihn entwickelt haben. Möglicherweise rechnen unsere Computer so - man kann schlecht hineinschauen, besonders nicht in die Chips mit Mathe-Prozeduren.
Homepage Leonhard Heinzmann veröffentlicht: 25. 3. 2013 Stand: 5. 1. 2014