# SRT-Division

Die SRT-Division ist ein schnelles Divisionsverfahren, das in der Computerarithmetik verwendet wird. Die Bezeichnung rührt von ihren drei Erfindern her, die um 1958 nahezu gleichzeitig und unabhängig das Verfahren beschrieben – Dura Sweeney (IBM), James Robertson (University of Illinois) und Keith Tocher (Imperial College London). Der breiten Öffentlichkeit bekannt wurde das Verfahren durch den Pentium-FDIV-Bug, der in den ersten Versionen von Intels Pentium-Prozessoren zu vereinzelten fehlerhaften Divisionen führte. Grund waren einige falsche (weil fehlende) Einträge in der Quotienten-Tabelle.

## Theoretische Grundlagen

Gegeben seien:
* Dividend: $p\ |p\in \mathbb {Z}$
* Divisor: $d\ |d\in \mathbb {N} \land d\geq 1$
* Basis: $g\ |g\in \mathbb {N} \land g\geq 2$
* Ziffernliste: $S_{g}:=\{-a,...,0,...,+a\}|a\in \mathbb {N} \land 2\cdot a+1\leq g$
Gesucht:
* Jene Lösung für $p:=q\cdot d+r$ mit dem betragsmäßig kleinsten $r\in \mathbb {Z}$ mit dem gleichen Vorzeichen wie $p\cdot d$.
Ziel der SRT-Division ist es, den Ausdruck $q:=p\div d$ darzustellen als $q=\sum _{k=-n}^{N-n}q_{k}g^{-k}+\epsilon \qquad q_{k}\in S_{g}$.
Dabei ist N die Anzahl der Iterationen (und damit die Anzahl der berechneten Ziffern). n ist die Anzahl der für die Berechnung der Ziffern vor dem Dezimalpunkt benötigten Iterationen. Bei Gleitkommazahlen mit normalisierter Mantisse ist n immer 0. In der Prozessortechnik wird die SRT-Division aus praktischen Gründen meist mit $g=4$ und $S_{4}={-2,-1,0,1,2}$ durchgeführt. So kann man einerseits zwei Ergebnisbits pro Iteration berechnen, kann andererseits darauf verzichten, den Divisor aufwendig zu multiplizieren, da $S_{4}$ nur aus 2er-Potenzen besteht.
Die SRT-Division kann man dabei in zwei Komponenten aufteilen, zum einen in den eigentlichen Divisionsalgorithmus, zum anderen in die Ziffernauswahlfunktion, die in der Prozessortechnik im Regelfall mit Hilfe einer Tabelle realisiert wird. Dabei erhält die Ziffernauswahlfunktion z. B. die sechs höchsten Bits aus dem Zwischenergebnis und die vier höchsten Bits aus dem Divisor und liefert als Ergebnis die nächste Quotientenziffer aus $S_{g}$ zurück.

## Die SRT-Division in der Praxis
### Herkömmliches Divisionsverfahren

Beim herkömmlichen Divisionsverfahren beginnt man mit den höchstwertigen Stellen, prüft, wie häufig der Divisor enthalten ist, notiert die Anzahl als höchstwertige Ziffer des Ergebnisses, subtrahiert den Divisor entsprechend häufig. Für den nächsten Schritt, der die nächstniedrigere Ziffer des Quotienten berechnet, wird die nächstniedrigere Ziffer des Dividenden zum Zwischenergebnis hinzugefügt. Der Vorgang wird solange wiederholt, bis der Quotient mit zufriedenstellender Genauigkeit ermittelt wurde.
Beispiel:

### Nachteile dieses Verfahrens

Für die Entscheidung, wie häufig der Divisor den momentan betrachteten Teil der Zahl teilt, muss die gesamte Zahl vorliegen. Eine Abschätzung reicht nicht aus. Der Zeitaufwand für eine Addition steigt linear mit der Anzahl der Ziffern, weil sich Überträge im Laufe der Addition im schlimmsten Fall von der niederwertigsten Ziffer bis zur höchstwertigen Ziffer fortpflanzen können (Beispiel: 99999999999+1), wodurch die Addition auch nicht parallelisierbar ist. Da Computer mit Binärzahlen arbeiten, also nur die Ziffern 0 und 1 besitzen, bestehen selbst »kleine« Zahlen aus vielen Ziffern. Die vier im Beispiel benutzten Zahlen (Dividend, Divisor, Quotient und Rest) werden zum Beispiel im Binärzahlensystem folgendermaßen dargestellt: 15624829 ⇒ 111011100110101001111101, 523 ⇒ 1000001011, 29875 ⇒ 111010010110011, 204 ⇒ 11001100. Um die Schaltwerke zu vereinfachen, arbeiten Computer darüber hinaus im Regelfall mit einer konstanten Anzahl an Bits. Wird die Zahl 523 also in einem 64-Bit-Register gespeichert, dann wird auch mit 64 Bits gerechnet (von denen die meisten Bits führende bzw. bei Gleitkommazahlen abschließende Nullen sind).

### Saved-Carry-Addition

Um das Problem mit den Überträgen zu lösen, greift das SRT-Verfahren auf die Saved-Carry-Addition (zu Deutsch: Gespeicherte Überträge) zurück. Bei dieser Addition wird das Ergebnis errechnet, wobei allerdings die Überträge ignoriert werden. Diese werden separat gespeichert und müssen später noch hinzuaddiert werden, um das korrekte Ergebnis zu erhalten.
Beispiel:

#### Keine Korrektur bei falsch geratenen Quotienten-Ziffern

Wenn man mittels Papier und Bleistift eine Division durchführt, muss man intelligent raten, wie die nächste Ziffer des Quotienten lautet.
Beispiel:
Hier würde man basierend auf den ersten Ziffern »raten«, dass 523 dreimal in 1562 hineinpasst. Führt man dann allerdings den Schritt zu Ende, erkennt man, dass die Annahme falsch war:
Im korrigierenden Divisionsverfahren (siehe Beispiel zu Beginn) würde man jetzt den Quotienten zu 2 korrigieren und 523 wieder addieren (oder neu rechnen):
Das SRT-Verfahren ist ein Nicht-korrigierendes Divisionsverfahren, hier bleibt also im Prinzip -7 stehen. In diesem Fall muss man die Subtraktion dann aber mit der gesamten Zahl durchführen:
Erst im nächsten Rechenschritt wird nun die negative Zahl korrigiert, indem der Quotient als -1 (also negativ, hier dargestellt durch einen Überstrich) angenommen wird:
Führt man dieses Verfahren fort ...
... so erhält man z. B. den Quotienten (negativ ist fett) 31935. Dieses Ergebnis, dargestellt in einer redundanten Schreibweise (jede Zahl kann auf viele Arten dargestellt werden) muss nun noch normalisiert werden. 31 bedeutet nichts anderes als 30 minus 1, also 29. Es folgen eine positive Zahl 9 und eine negative 3 also 87 und schlussendlich eine positive Zahl 5. Somit lautet der Quotient korrigiert: 29875 (plus der Rest 204), was dem Ergebnis aus dem ersten Beispiel entspricht.

### Beides zusammen

Da wir bei der Division auch zu große Quotienten wählen dürfen (da sich dieser Fehler offenbar im nächsten Schritt wieder korrigieren lässt), brauchen wir nun bei der Addition nicht mehr die gesamte Zahl inklusive Überträge zu addieren, sondern es reicht ein Näherungswert, z. B. die Summe ohne Überträge; die Überträge können dann im jeweils nächsten Schritt hinzugefügt werden. Allerdings gilt dies nicht ohne Einschränkungen:
Im letzten Schritt müsste eine zweistellige Ziffer gewählt werden, um die im vorletzten Schritt zu klein gewählte -5 wieder auszugleichen. Selbst wenn ab jetzt nur noch positive 9en als Ziffern eingesetzt werden, kann das korrekte Ergebnis nicht mehr erreicht werden. Daher ist es unerlässlich, wenigstens die drei höchstwertigen Ziffern vollständig (also inklusive Überträge) zu berechnen. Hier werden nun die drei höchsten Ziffern (die auch 0 sein können) vollständig summiert, der Rest wie im vorangegangenen Beispiel mit Saved-Carry-Addition:
Ergebnis ist hier die Zahl 31936 mit Rest -319, neben dem Quotienten, der hier um eins zu groß ist, muss nun auch noch der negative Rest normalisiert werden. Der Rest wird korrigiert, indem der Divisor hinzuaddiert wird (ergibt dann 204, wie in den Beispielen weiter oben), der Quotient ist dann wieder 31935, oder auch normalisiert 29875.

## Ähnliche Verfahren

* Goldschmidt-Division
* Newton-Raphson-Division