Ein schneller Quadrierungs - Algorithmus: dezimale Version
Übersicht
Hier wird die dezimale Version des Panflöten-Algorithmus vorgestellt, der die Quadrierung
einer Zahl mit dem halben Aufwand leistet wie die Multiplikation von zwei gleich langen Zahlen.
Dezimal ist die Linker-Rest-Version des Algorithmus besser (Gründe unten), nur sie wird hier gezeigt.
Es wird empfohlen, zuerst den Hauptartikel mit dem binären Algorithmus
zu lesen, wo der (einfache) Rechenvorgang genau erklärt ist.
Dort gibt's auch die theoretische Herleitung und weitere Themen.
Der Algorithmus dezimal (kurze Version)
Ein Beispiel: quadriere 5629:
5 6 2 9 Spreize die Zahl (kein Summand!)
--------
5058 Summand 562*9 doppelt addieren!
112 Summand 56*2 doppelt addieren!
30 Summand 5*6 doppelt addieren!
25360481 Gespreizte Zahl, Ziffern quadriert
--------
31685641 Summe obere 4 Zeilen = Ergebnis
Das Spreizen der Zahl (oberste Zeile) ist nur informatorisch (im Ggs. zum binären Algorithmus),
aufsummiert wird die gespreizte Zeile mit quadrierten Ziffern (vorletzte Zeile).
Binär sind beide Ausdrücke gleich, deshalb konnte man dort gleich die oberste Zeile summieren.
Beim dezimalen Rechnen ist manches komplizierter, egal bei welchem Algorithmus.
Beim Quadrierungs-Algorithmus sieht das so aus:
- Die Teilstrings der Zahl sind mit der Ziffer rechts zu multiplizieren
(ähnlich wie beim üblichen dezimalen Multiplikations-Algorithmus)
Regel: Falls eine Ziffer ≠ 0, multipliziere damit den Ziffernstring links von ihr
und schreibe ihn rechtsbündig unter die linke Nachbarziffer
- Die Ziffernstrings sind nochmal mit 2 zu multiplizieren.
Bei der kurzen Version des Algorithmus geschieht das, indem man diese Strings zweimal addiert
(Binär wurde die Multiplikation mit 2 durch Verschieben der Ziffenstrings um 1 nach links erledigt)
- Beim Spreizen der Zahl sind die einzelnen Ziffern zu quadrieren.
Dabei ergeben sich meist 2-stellige Werte. Man schreibt immer ein Ziffernpaar, ggf. mit führender 0
Der Algorithmus dezimal (lange Version)
Ein Beispiel: quadriere 5629:
5 6 2 9 Spreize die Zahl (kein Summand!)
--------
5058 Summand 562*9
112 Summand 56*2
30 Summand 5*6
--------
316258 Summe
632516 2*Summe
25360481 Gespreizte Zahl, Ziffern quadriert
--------
31685641 Summe obere 2 Zeilen = Ergebnis
Der einzige Unterschied zur kurzen Version liegt bei der Verdopplung der
(bereits mit einer Ziffer multiplizierten) Ziffernstrings.
Jetzt werden zunächst alle Ziffernstrings addiert, ihre Summe mit 2 multipliziert und
das Ergebnis zur gespreizten Zahl mit quadrierten Ziffern addiert
Vergleich: Linker-Rest-Version und Rechter-Rest-Version
Der dezimale Linker-Rest-Algorithmus hat gegenüber dem (hier nicht gezeigten) dezimalen Rechter-Rest-Algorithmus folgende Vorteile:
- man schreibt die Teilstrings wie beim Multiplizieren üblich v.r.n.l.
- ein Teilstring beginnt rechts immer an einer festen Stelle, auch wenn
er durch die Multiplikation mit einer Ziffer links um 1 Ziffer länger wird
Deshalb ist dezimal der Linker-Rest-Algorithmus ergonomischer.
Aber binär ist m.E. der Rechter-Rest-Algorithmus etwas eingängiger (übliche Schreibrichtung nach rechts)
und verbal leichter formulierbar, und die Vereinfachung bei Eineserblocks ist etwas eleganter
Bei allen Algorithmen kann man auch die komprimierte Schreibweise anwenden
Aufwand
Bei einer Quadrierung mit dem üblichen Multiplikations-Algorithmus müssen bei einer Zahl N mit n Ziffern
maximal n2 Ziffern addiert und (außer im Binärsystem) vorher diese n2 Ziffern mit einer
Ziffer multipliziert werden (jeweils mit Behandlung der Überträge)
Beim hier gezeigten Quadrierungs-Algorithmus ist der Aufwand kleiner, aber je nach Version verschieden:
Binär:
Beim binären Quadrierungs-Algorithmus ist der Aufwand nur halb so groß
(bei Zahlen mit Einserblocks noch viel kleiner)
Dezimale Langversion:
Es müssen die Teilstrings addiert werden (maximal n-1 Zahlen mit durchschnittlich (n-1)/2 Ziffern)
sowie die Summe der Strings (ca. 2n Ziffern) und die gespreizte Zahl (max. 2n Ziffern),
zusammen also max. (n-1)2/2 + 4n Ziffern, also ( n2 - 2n +1 + 8n ) /2
~ n2/2 + 3n Ziffern
Diese Ziffern mußten praktisch alle vorher mit 1 Ziffer multipliziert werden
(bei der gespreizten Zahl nur n statt 2n Ziffern)
Der Aufwand gegenüber dem üblichen Multiplikations-Algorithmus nimmt also mit der Ziffernzahl ab.
Der Unterschied beträgt bei 10 Ziffern 80 : 100 (80%) , bei 100 Ziffern 5300 : 10000 (53%)
Der Algorithmus ist aber geringfügig komplizierter (Summe *2, Spreizen der Zahl)
Dezimale Kurzversion:
Es müssen die Teilstrings addiert werden (maximal n-1 Zahlen mit durchschnittlich (n-1)/2 Ziffern),
und zwar zweimal, sowie die gespreizte Zahl (max. 2n Ziffern),
zusammen also max. (n-1)2 + 2n Ziffern, also n2 - 2n + 1 + 2n = n2 + 1 Ziffern
Davon mußten vorher (n-1)2/2 + n Ziffern mit 1 Ziffer multipliziert werden.
Im Vergleich zum üblichen Multiplikations-Algorithmus müssen also genauso viele Ziffern addiert,
aber nur gut halb so viele, nämlich (n-1)2/2 + n statt n2 Ziffern mit 1 Ziffer multipliziert werden.
Gewichtet man Addition und Multiplikation von Ziffern gleich dann liegt der Aufwand bei über 75% (gering abhängig von der Ziffernzahl).
Gewichtet man die Multiplikation stärker (schwieriger, höhere Überträge), ist er entsprechend geringer
Wertung:
Der dezimale Algorithmus ist nur für das Rechnen "von Hand" interessant - Computer rechnen binär.
Deshalb ist die einfachere Kurzversion des Quadrierungs-Algorithmus vorzuziehen, die bei Zahlen
bis 10 und mehr Ziffern genauso schnell ist wie die Langversion. Letztere erreicht aber bei hoher Stellenzahl
(z.B. 100) die Geschwindigkeit des binären Algorithmus ohne Vereinfachung bei Einserblocks
Homepage Leonhard Heinzmann veröffentlicht: 25. 3. 2013 Stand: 22. 5. 2013