% Content-encoding: UTF-8
\documentclass[ngerman]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setcounter{secnumdepth}{0}
\setcounter{tocdepth}{0}

\begin{document}

\title{Simples LNS}
\author{Rafael Deliano}
\maketitle

Die Darstellung in [62] passt direkt für Mikroprozessoren. Die Z80--Source wurde auf FORTH und HC08 portiert.


\begin{multicols*}{2}
Das Grundschema hat sich seit Mitchell [1] nicht verändert.

\begin{center}
\includegraphics[width=0.4\columnwidth]{2008-01/SLNS-Bild1}\\
\label{SLNS:Bild1}Bild 1: Aufspaltung
\end{center}

Man sucht sich mit der Funktion SCANBIT [61] das oberste gesetzte Bit. Dessen Position ergibt den Integer-Teil des Logarithmus, die folgenden Bits die Fraction (Bild 1). Für den groben Logarithmus BITLOG in [61] wurden als Fraction nur 3 Bits verwendet. Bei so niedriger Auflösung kann man den Bereich von ld(1) bis ld(2) als Gerade annehmen, wie dort geschehen (Bild 2).

\vspace{-3ex}
\begin{center}
\includegraphics[width=0.8\columnwidth]{2008-01/SLNS-Bild2}\\
\label{SLNS:Bild2}Bild 2: Verlauf $\mbox{ld}(x)$
\end{center}

Eine 8--Bit--Fraction ergibt deutlich bessere Auflösung, man muss nun aber die Kurve in Bild 2 annähern. In [62] wird dafür eine 256--Byte--Tabelle (Bild 3, 4) verwendet. 

\begin{figure*}[t]
\begin{minipage}[b]{0.5\textwidth}
\begin{center}
\includegraphics[width=0.6\textwidth]{2008-01/SLNS-Bild5}\\
\label{SLNS:Bild5}Bild 5:  Berechnung ILOG
\end{center}
\end{minipage}
\hfill
\begin{minipage}[b]{0.5\textwidth}
\begin{center}
\includegraphics[width=0.5\textwidth]{2008-01/SLNS-Bild6}\\
\label{SLNS:Bild6}Bild 6:  Berechnung LOG
\end{center}
\end{minipage}
\end{figure*}

\begin{figure*}[t]
\hfil
\begin{minipage}[b]{0.4\textwidth}
$k:=1..100\ \ A_k:=|a_k - k^{2,5}|$\\
\includegraphics[width=0.8\textwidth]{2008-01/SLNS-Bild7a}
\end{minipage}
\hfil
\begin{minipage}[b]{0.4\textwidth}
$A_k:=\frac{k^{2,5}}{a_k}$\\
\includegraphics[width=0.8\textwidth]{2008-01/SLNS-Bild7b}
\end{minipage}
\hfill
\begin{center}
\label{SLNS:Bild7}Bild 7: Fehlerplot $x^{2,5}$
\end{center}
\end{figure*}

 
\section{LOG}

Die Routine liefert eine 16--Bit--Integerzahl die den Dezimalpunkt genau in der Mitte hat (Bild 6), d.h. $y=256*\mbox{ld}(x)$. Dass oben 4 Bits unbelegt sind, ist sehr erwünscht, weniger Probleme mit Überlauf, wenn man mit fester 16--Bit--Wortlänge rechnet.\bigskip

\begin{center}
\begin{minipage}{0.5\columnwidth}
$x := 0..255$\\
$g_x:=256\cdot\frac{\ln(1+\frac{x}{256})}{\ln(2)}$\\
$d_x:=\mbox{runden}(g_x)$
\end{minipage}\\
\includegraphics[width=0.6\columnwidth]{2008-01/SLNS-Bild3}\\
\label{SLNS:Bild3}Bild 3: Berechnung L-TAB
\end{center}
\columnbreak

 

\section{ILOG}

Im Rückwandlungsbefehl muss man ersteinmal prüfen, ob das obere Byte größer 0F ist, und dann wegen Überlauf direkt FFFF ausgeben. In Assembler wird man die Daten wie gezeigt in einem 24--Bit--Register anordnen und dann abhängig vom oberen Byte entsprechend oft hochschieben.

Speicherverbrauch und Geschwindigkeit sowohl für Assembler als auch nanoFORTH auf einem 2,45--MHz--68HC08 sind in Tabelle 1 angegeben. Zuzüglich 512 Byte für die Tabellen.\bigskip

\begin{center}
\begin{minipage}{0.8\columnwidth}
$x := 0..255$\\
$g_x:=256\cdot\left[\exp\left[(\frac{x}{256})\cdot\ln(2)\right]-1\right]$\\
$d_x:=\mbox{runden}(g_x)$
\end{minipage}
\includegraphics[width=0.6\columnwidth]{2008-01/SLNS-Bild4}\\
\label{SLNS:Bild4}Bild 4:  Berechnung IL-TAB
\end{center}
\bigskip


In Listing 2 sind die beiden Beispielprogramme aus [62] aufgeführt. Vgl.\ hierzu die Flussdiagramme in Bild 5, 6 des einführenden Artikels auf Seite \pageref{LNS}.\bigskip

\begin{center}
\begin{tabular}{lllll}
  & \multicolumn{2}{c}{FORTH} & \multicolumn{2}{c}{Assembler}\\
  &    Byte & usec &     Byte & usec \\
LOG  & 103 & 300-700 &  39 &  20-50 \\
ILOG & 171 & 200-400 &  50 &  40-100\\
\end{tabular}\bigskip

Tabelle 1: Speicher \& Rechenzeit
\end{center}
\bigskip

Für $x^{2,5}$ sind in Bild 7 die Fehlerplots. Der absolute Fehler steigt natürlich, wenn die Zahlen größer werden, bis dann endgültig Überlauf eintritt. Bei relativem Fehlerplot hat man aber nur bei sehr kleinen Zahlen und im Überlauf extremen Fehler. 

\section{Literatur}
\begin{tabular}{lp{0.9\columnwidth}}
{[61]} &emb (9) oder  VD 1/2004 „Einfacher Logarithmus“\\
{[62]} & Guagliano „Simple logarithms speed microprocessors math operations“  
EDN 24. Jan 1985 in: Hickman „Electronic Circuits, Systems an Standards: the Best of EDN“ Butterworth-Heinemann 1991
\end{tabular}
\end{multicols*}

\begin{minipage}[t]{0.59\textwidth}
\section{Listing 1: Tabellen, LOG, ILOG}
\begin{quote}
\begin{verbatim}
TABLE L-TAB 
   00 C, 01 C, 03 C, 04 C, 06 C, 07 C, 09 C, 0A C,
   ...
   FA C, FB C, FC C, FC C, FD C, FE C, FF C, FF C,

TABLE IL-TAB
   00 C, 01 C, 01 C, 02 C, 03 C, 03 C, 04 C, 05 C,
   ...
   F5 C, F6 C, F8 C, F9 C, FA C, FC C, FD C, FF C,

: LOG           \ ( UN1 — UN2 ) 
   DUP 99 /?ERROR \ error if UN1 = 0
   0F 0 DO
      DUP 8000 AND
      IF I LEAVE ELSE 1<SHIFT THEN
   LOOP
   0F SWAP - 8<SHIFT
   SWAP 1<SHIFT 8SHIFT> L-TAB + C@
   OR ;

: ILOG          \ ( UN1 — UN2 )
   DUP F000 AND
   IF DROP FFFF    \ overflow UN2 = FFFF
   ELSE.
     DUP FF AND IL-TAB + C@ 100 OR
     SWAP 8SHIFT>
     DUP 08 =
     IF DROP         \ no shifts
     ELSE DUP 08 U<
     IF   7 SWAP - 0 DO 1SHIFT> LOOP
     ELSE 9      - 0 DO 1<SHIFT LOOP
     THEN
     THEN
   THEN ;
\end{verbatim}
\end{quote}
\end{minipage}
\begin{minipage}[t]{0.4\textwidth}
\section{Listing 2: Beispiele}
\begin{quote}
\begin{verbatim}
: X^2,5    \ ( UN1 — UN2 ) 
   LOG 
   DUP 1<SHIFT SWAP 1SHIFT> + 
   ILOG ; 
   
: FUNCTION    \ ( B A — C ) 
   LOG 
   1<SHIFT 
   084A -         \ 313d 
   ILOG 
   SWAP LOG 1<SHIFT 
   08DA -         \ 462d 
   ILOG 
   + 
   LOG 1SHIFT> ILOG ; 
\end{verbatim}
\end{quote}

\vspace{3cm}
Kompletter Sourcecode auf:\medskip
 
\url{http://www.embeddedFORTH.de}\medskip

 
Für Portierung auf andere Forth--Varianten vergleiche dort im 
GP32--Manual die Seiten 4.2 und 4.3.
\end{minipage}

\end{document}
