Inhaltsverzeichnis
d-star-collection
Grundlagen
Wir lernen in der Schule multiplizieren in der „langen Form“ und die Frage ist nun, können wir damit einen Algorithmus finden, um doppelt genaue Zahlen zu multiplizieren?
Die lange Multiplikation geht so:
12 * 34
-------
8
+ 40
+ 60
+ 300
---
+ 100 Ü
---
408 Summe
===
Man multipliziere die beiden Einer (24), dann den zweiten Einer mit dem ersten Zehner (410), den zweiten Zehner mit dem ersten Einer (302) und nun noch die beiden Zehner (1030). Diese Zwischenergebnisse werden schließlich aufsummiert und die Überträge hinzugerechnet.
Abstraktion
Bild1
A B * C D
---------------
BD
+ AD 00
+ BC 00
+ AC 00 00
--------
+ YY XX 00 Ü
--------
KK MM NN Summe
Die beiden Zahlen AB und CD stellen unsere doppelt genauen Zahlen dar. Der Wert in der oberen Zelle A entspricht der höheren Stelle, der Wert B in der unteren Zelle der unteren Stelle, ebenso bei CD: C ist die höhere, D die untere Stelle, daher liegt C in der oberen und D in der unteren Zelle. Jede Stelle füllt also eine Zelle auf dem Stack.
Der Algorithmus d* "d-star"
In der Stacknotation mit lokalen Variablen sieht das so aus:
: d* { B A D C -- NN MM }
B D um* ( NN XX )
A D * +
B C * + ;
Und wo ist nun die Zelle mit KK geblieben, also quasie die dritte Stelle? Da das Ergebnis, die doppelt genaue Multiplikation, auch nur höchstens doppeltgenau sein soll, entfällt die Positionen AC samt dem Übertrag YY einfach, und damit gibt es auch die Summe KK nicht. Werden Zahlen multipliziert, die dahin überlaufen, haben wir einen Fehler gemacht. Das ist bei der einfach genauen Multiplikation auch so. Auch dort dürfen mit * nur Zahlen multipliziert werden, die keinen Übertrag in die nächste Zelle ergeben.
hex 2 FF * u. <ret> 1FE ok 2 true * u. <ret> FFFFFFFE ok \ sollte aber sein: 1FFFFFFFE \ Der Übertrag entfällt einfach! 2 true um* ud. <ret> 1FFFFFFFE ok
Das Wort um* liefert das richtige Ergebnis, weil der Übertrag mit berechnet wird. Die 'richtige' einfachgenaue Multiplikation muss also in einem doppeltgenauem Ergebnis münden, sonst stimmt sie ab einer gewissen Größe nicht mehr.
Im Forth wird dieser Überlauf im aber nicht abgefangen und auch nicht als Fehler angezeigt. Der Programmierer muss selbst darauf achten, dass seine Produkte in der Grenze einer Zelle bleiben, die Faktoren also nicht zu groß werden. Oder er nimmt gleich um* für seine Multiplikation.
Für d benutzt werden. Damit wird eine weitere Zelle bereitgestellt (t steht für „trippel“).
gilt das ebenso. Die doppeltgenaue Multiplikation kann auch überlaufen in die nächst höhere Zelle GG. Um das darzustellen muss ut
So kann man sich seine eigenen Multiplikationsworte zusammenstellen, so genau wie man möchte, indem immer weitere Zellen hinzu genommen werden. Um die Verwirrung auf dem Stack nicht zu groß werden zu lassen, können lokale Variablen benutzt werden. Die Ausführungsgeschwindigkeit sinkt dadurch aber. Ein Beispiel dazu ist weiter unten angegeben.
Stack Akrobatik
Aus Bild1 entnehmen wir: In die unterste Zelle kommt das Produkt BD und sein Überlauf nach XX muss mitgenommen werden. Die Multiplikation muss also mit um
erfolgen, und in der höheren Zelle finden wir den Überlauf XX wieder: B D um ( – NN XX )
In die höhere Zelle kommt die Summe AD+BC+XX und es kann einfach gerechnet werden. Überläufe nach YY werden nicht mehr berücksichtigt, denn die Summe KK wird nicht mehr gebildet.
Um das ohne lokale Variablen zu formulieren muss man etwas tüfteln. Auch um dafür zu sorgen das die Version auf 64Bit Maschinen korrekt arbeitet.
: d* ( ud1 ud2 -- udprod ) >r swap >r 2dup um* 2swap r> * swap r> * + + ;
Was passiert da eigentlich?:
( B A D C -- NN MM ) \ mit ud1 = B A und ud2 = D C >r ( -- B A D ) ( R: -- C ) swap ( -- B D A ) ( R: -- C ) >r ( -- B D ) ( R: -- C A ) 2dup um* ( -- B D NN XX ) ( R: -- C A ) 2swap r> ( -- NN XX B D A ) ( R: -- C ) * ( -- NN XX B AD ) ( R: -- C ) swap r> ( -- NN XX AD B C ) ( R: -- ) * ( -- NN XX AD BC ) + + ( -- NN MM )
Varianten
Eine Variante stammt von Luca Masini. Sie arbeitet auf 16Bit Maschienen gut, geht aber nicht auf 64Bit Maschinen, da dort TUCK und PICK nicht in die Zellen greifen können.
: d* ( d1 d2 -- d3 ) 3 pick * >r tuck * >r um* r> + r> + ;
Gegeben ist auch hier wieder die Eingangsreihenfolge ( d1 d2 – ) entsprechend den Zellen ( B A D C – ) aus Bild1. Die TOP-Zelle C wird nur einmal gebraucht um BC zu bilden: 3 PICK * >R erledigt dies und BC räumen wir damit schon mal aus dem Weg. Nun ist D in der TOP-Zelle. D wird 2x gebraucht: TUCK * >R bildet das AD und hebt es auf dem Returnstack auf, danach ist D=TOP und B gleich darunter. Das Produkt BD muss mit seinem Überlauf verarbeitet werden, also: um* und damit ist TOP=XX und bereits in der höheren Zelle, während BD darunter abgelegt worden ist. Nun können die Zwischenprodukte BC und AD vom Returnsatck geholt und zu TOP=XX addiert werden: R> + R> + und fertig ist die Berechnung.
Es bietet sich an die Worte PICK und TUCK zu verwenden, wenn sie in Maschinencode realisiert worden sind um schnell zu sein. Sonst ist noch mehr Akrobatik auf dem Stack erforderlich.
: d* ( d1 d2 -- d3 ) \ d1 = cell-low == B D um* \ d2 = Cell-high == AD BC XX + + \ ( B A D C -- NN MM ) rot swap >r >r ( B D -- ) ( R: -- C A ) over over >r >r ( B D -- ) ( R: -- C A D B ) um* ( NN XX -- ) ( R: -- C A D B ) r> r> r> ( NN XX B D A -- ) ( R: -- C ) * ( NN XX B AD -- ) ( R: -- C ) swap ( NN XX AD B -- ) ( R: -- C ) r> ( NN XX AD B C -- ) * ( NN XX AD BC -- ) + + ( N M -- ) ; \ ok mk18.04.08
Tripple genaues Ergebnis
Wer nun noch weitere Genauigkeit benötigt braucht die dritte Zelle mit dem Wert KK darin.
: ut* { B A D C -- NN MM KK }
B D um* ( -- NN XX )
A D um* >r ( -- NN XX AD ) ( R: -- YY1 )
+ ( -- NN MM1 ) ( R: -- YY1 )
B C um* >r ( -- NN MM1 BC ) ( R: -- YY1 YY2 )
+ ( -- NN MM ) ( R: -- YY1 YY2 )
A C * ( -- NN MM AC ) ( R: -- YY1 YY2 )
r> + ( -- NN MM KK2 ) ( R: -- YY1 )
r> + ( -- NN MM KK ) ;
Und so kann man das weiter steigern, soweit wie man möchte.