\documentclass[a4paper]{article}

\usepackage[utf-8]{inputenc}
\usepackage[german]{babel}
\usepackage{url}
\usepackage{alltt}
\usepackage{multicol}

\title{Doppeltgenaue Multiplikation}
%\ifx\shorttitle\undefined\else
%\shorttitle{Berichte generieren}
%\fi
\author{Michael Kalus}

\begin{document}
\maketitle

Am Beispiel der doppeltgenauen Multiplikation d* wird gezeigt wie der Algorithmus der Multiplikation auf einer Maschine abgearbeitet werden kann.

\begin{multicols}{2}

\section{Grundlagen}

Wir lernen in der Schule multiplizieren in der "langen Form" und die Frage ist nun, können wir damit einen Algorithmus finden, um doppeltgenaue Zahlen zu multiplizieren?

Die lange Multiplikation geht so:\medskip

\hfil
\begin{minipage}{3cm}
\begin{verbatim}
12 * 34
-------
      8
+    40  
+    60
+   300
    ---
+   100 Ü
    ---
    408 Summe
    ===
\end{verbatim}
\end{minipage}\medskip

Man multipliziere die beiden Einer ($2*4$), dann den zweiten Einer mit dem ersten Zehner ($4*10$), den zweiten Zehner mit dem ersten Einer ($30*2$) und nun noch die beiden Zehner ($10*30$). Diese Zwischenergebnisse werden schließlich aufsummiert und die Überträge hinzugerechnet.



\section{Der Algorithmus}


\hfil
\begin{minipage}{3cm}
\begin{verbatim}

  A B  *  C D
---------------
            BD
+        AD 00
+        BC 00
+     AC 00 00
   -----------
+  ZZ YY XX 00 Ü
   -----------
   GG KK MM NN Summe

\end{verbatim}
\centerline{Bild 1: Doppeltgenaue Multiplikation}
\end{minipage}\medskip

Die beiden Zahlen $AB$ und $CD$ stellen schon unsere doppeltgenauen 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$. Jede Stelle füllt also eine Zelle auf dem Stack. In der Stacknotation mit lokalen Variablen sieht das dann so aus:

\begin{quote}
\begin{verbatim}
: d* { B A D C -- NN MM }
  B D um* ( NN XX )
  A D * +
  B C * + ;
\end{verbatim}
\end{quote}

Und wo sind nun der Überlauf $YY$ und die Zelle  $KK$ geblieben, also quasie die dritte Stelle? Da das Ergebnis der doppeltgenauen 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 \verb|*| nur Zahlen multipliziert werden, die keinen Übertrag in die nächste Zelle ergeben.
 
\begin{quote}
\begin{verbatim}
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
\end{verbatim}
\end{quote}

Das Wort \verb|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 \verb|*| 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 \verb|um*| statt \verb|*| für seine Multiplikation.

Für \verb|d*| gilt das ebenso. Die doppeltgenaue Multiplikation kann auch überlaufen in die nächst höhere Zelle $GG$. Um das darzustellen muss \verb|ut*| benutzt werden. Damit wird eine weitere Zelle bereitgestellt (t steht für \glqq trippel\grqq).

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.

\section{Die Stack--Akrobatik im \texttt{d*} soll auch auf 64Bit--Maschinen laufen.}

Aus Bild 1 entnehmen wir: In die unterste Zelle kommt das Produkt $BD$ und sein Überlauf nach $XX$ muss mitgenommen werden. Die Multiplikation muss also mit \verb|um*| erfolgen, und in der höheren Zelle finden wir den Überlauf $XX$ wieder: $B D$ \verb|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.

\begin{quote}
\begin{verbatim}
: d*     ( ud1 ud2 -- udprod )
  >r swap >r 2dup um*
  2swap r> * swap r> * + + ;
\end{verbatim}
\end{quote}


\section{Was passiert da eigentlich?}

\begin{footnotesize}
\begin{quote}
\begin{verbatim}
 ( 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 )
\end{verbatim}
\end{quote}
\end{footnotesize}

Wer nun noch weitere Genauigkeit haben will, braucht auch die dritte Zelle mit dem Wert $KK$ darin.

\begin{quote}
\begin{verbatim}
\ tripple genaues Ergebnis
: 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 ) ;  
\end{verbatim}
\end{quote}

Und so kann man das weiter steigern, soweit wie man möchte.

\end{multicols}
\end{document}