% Content-encoding: UTF-8
\documentclass[ngerman]{article}
\usepackage[utf8]{inputenc}
\usepackage{multicol,babel}
\setcounter{secnumdepth}{0}
\setcounter{tocdepth}{0}

\renewcommand{\reftextbefore}{auf der vorherigen Seite}
\renewcommand{\reftextfacebefore}{auf der gegenüberliegenden Seite}
\renewcommand{\reftextafter}{auf der nächsten Seite}
\renewcommand{\reftextfaceafter}{auf der gegenüberliegenden Seite}


\begin{document}
% \renewcommand{\figurename}{Tabelle}

\title{Euler 9 für Turbo–Forth und ZF}
\author{Fred Behringer}
\maketitle


\section{Zusammenfassung}
Henry Vinerts (private Mitteilung) wollte Euler 9 gern mit Turbo--Forth
in
16--Bit--Breite berechnen. Eine schnelle Abschätzung zeigt, dass man mit
16 Bit
nicht duchkommt. Zwar gibt es (auch) in Turbo--Forth doppeltgenaue
Arithmetik,
aber ein paar Überlegungen zur Anpassung sind schon noch nötig.
Insbesondere
muss die Dreifachmultiplikation $a*b*c$ geeignet bewältigt werden.

\begin{multicols}{2}
Für 32--Bit--Systeme kennen wir den Lösungsvorschlag von Michael Kalus aus
Seite
25 des VD--Heftes 2/2008 und das Verfahren von Ulrich Hoffmann aus Heft
3/2008,
Seite 38, welches letztere das Ziehen der Quadratwurzel vermeidet. Ich
habe mir
für das 16--Bit--System Turbo--Forth Ullis Vorgehen als Ausgangspunkt
gewählt. Als
Nebenprodukt springt bei diesen Bemühungen heraus, dass das unten
stehende
Listing ohne jede Änderung auch für ZF verwendbar ist (ich habe es
ausprobiert).
Ich weiß, dass insbesondere Friederich Prinz und Martin Bitter im
Zusammenspiel
mit der Lokalen Forth--Gruppe Moers in früheren Zeiten intensiv mit ZF
(von Tom
Zimmer) gearbeitet und es modifiziert haben, und ich bin auf weitere
Reaktionen
zum Thema \emph{Euler 9} gespannt.

Natürlich muss man bei meinem abgekürzten Verfahren zur
Dreifachmultiplikation
(siehe Listing) sichergestellt haben, dass das Dreifachprodukt in ein
32--Bit--Paket passt. Aber dieses Problem, dass nämlich Forth bei
arithmetischen
Operationen nicht standardmäßig gegen Überlauf des Gesamtergebnisses
abgesichert
ist, hat man ja generell. Man muss eben Vorüberlegungen einsetzen lassen
oder
durch Zusatzprogrammierung selbst Warn--Abhilfen schaffen. Was passiert
aber mit
den Zwischenergebnissen? Kann es da Überlauf geben? Michael Kalus geht
im
VD--Heft 2/2008 auf Seite 6 ausführlich auf diese Frage ein. Ich will
hier keinen
strengen Beweis für das Funktionieren des \emph{abgekürzten} Verfahrens der
Dreifachmultiplikation aus dem unten stehenden Listing geben. Ich will
aber
anhand eines ganz kleinen Beispiels versuchen, zur Verdeutlichung
beizutragen.

Ich betrachte für dieses Beispiel ein 4---Bit--Forth (das ist nicht
verboten :-) 
und lege als Dezimalwerte $5$ $6$ $7$ auf den Stack. Im weiteren Verlauf gebe
ich 
hier die Stackwerte (in einer Art von DEBUG--Vorgang) binär wieder. Das
Verfahren 
geht davon aus, dass man weiß, dass das Dreierprodukt in einem
8--Bit--Paket Platz 
hat. (Diejenigen Zahlen, die in den folgenden Erläuterungen
offensichtlich keine 
Binärzahlen sind, seien als Dezimalzahlen zu lesen. Die \emph{frühesten}
Stackwerte 
stehen links. Bei der Anzeige doppeltgenauer Werte ist in
Little--Endian--Manier 
die Reihenfolge zu vertauschen. Man mache sich klar, dass man das Paar 
einfachgenauer Werte $a$ $b$ auf dem Stack auch als doppeltgenauen Wert $a +
16*b$ deuten kann, usw.) Wie das genau aussieht, kann man in Abbildung \vref{euler9:verlauf} sehen.


Es konnte bei den Zwischenergebnissen kein Überlauf auftreten! Warum nicht?
Kritisch sind die Stellen mit \verb|*| und \verb|+| . Sie können als Tricks betrachtet werden.
Insbesondere vermeidet die Stelle mit \verb|+| den \emph{Umweg} über eine
doppeltgenaue Addition \verb|d+| und den damit verbundenen zusätzlichen Aufwand. (Die
Stackbelegung der mit \verb|rot| eingeleiteten Zeile hätte auch zu einem Paar doppeltgenauer
Werte \verb|0010 0110 0000 0111| erweitert werden können, das dann per \verb|d+| hätte
zusammengeführt werden müssen.)

\end{multicols}

\vspace{1cm}
%\begin{figure*}[b]
\begin{center}
\begin{minipage}[t]{12cm}
\begin{alltt}
     0101 0110 0111   (= 5 6 7  )
>r   0101 0110        (= 5 6    )
um*  1110 0001        (=  14 1  ) (= 14 + 16*1 = 00011110 = 30)
r@   1110 0001 0111   (=   30 7 ) (Ziel: 14*7 + 16*7)
*    1110 0111        (= 14 1*7 )
swap 0111 1110        (=  7 14  )
r>   0111 1110 0111   (=  7 14 7)
um*  0111 0010 0110   (=  7 14*7) (= 0111 01100010 = 7 98)
rot  0010 0110 0111   (=  98 7  ) (= 14*7 + 16*7)
+    0010 1101        (=  2 13  ) (= 2 + 16*(7+6) = 2+208)
d.   11010010 ok      (= 128+64+16+2 = 210 = 5*6*7)
\end{alltt}
\end{minipage}
\caption{\label{euler9:verlauf}Der Stackverlauf der Dreifachmultiplikation in einem 16--Bit--System}
\end{center}
\vfill
%\end{figure*}
\vfill


\newpage
\section{Listing}
\begin{quote}
\listinginput[1]{1}{2008-04/euler9-turbozf.fs}
\end{quote}


%\end{document}