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)^[1], James Robertson (University of Illinois)^[2] und Keith Tocher (Imperial College London)^[3]. 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\geq g$

Gesucht:

Jene Lösung für $q:=p\div d+r$ mit dem betragsmäßig kleinsten r mit dem gleichen Vorzeichen wie $p\cdot d$ .

Ziel der SRT-Division ist es, den Ausdruck $q:=p\div d+r$ darzustellen als $q=\sum _{k=-n}^{N-n}q_{k}g^{-k}+r\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:

15624829:523=29875 Rest 204
1046            Schritt 1:  1562:523=2, 2*523=1046, 1562-1046=516 ⇒ Quotient: 2????
 ====
 5164
 4707           Schritt 2:  5164:523=9, 9*523=4707, 5164-4707=457 ⇒ Quotient: 29???
 ====
  4578
  4184          Schritt 3:  4578:523=8, 8*523=4184, 4578-4184=394 ⇒ Quotient: 298??
  ====
   3942
   3661         Schritt 4:  3942:523=7, 7*523=3661, 3942-3661=281 ⇒ Quotient: 2987?
   ====
    2819
    2615        Schritt 5:  2819:523=5, 5*523=2615, 2819-2615=204 ⇒ Quotient: 29875
    ====
     204

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:

  15624829
 +52329875
  ========
  67943694 (Ergebnis ohne Überträge)
 00001101- (Überträge)
  ========
 +67954704 (Korrigiertes Ergebnis)

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:

15624829:523=

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:

 15624829:523=3
-1569
 ----
   -7

Im korrigierenden Divisionsverfahren (siehe Beispiel zu Beginn) würde man jetzt den Quotienten zu 2 korrigieren und 523 wieder addieren (oder neu rechnen):

 15624829:523=2
-1569
 ----
   -7
 +523
 ----
  516

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:

 15624829:523=3
-15690000
 --------
   -65171

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:

               _
 15624829:523=31
-15690000
 --------
   -65171
  +523000
  -------
   457829

Führt man dieses Verfahren fort ...

               _ _
 15624829:523=31935 Rest 204
-15690000 (-523*10000*+3)
 --------
   -65171
  +523000 (-523* 1000*-1)
  -------
   457829
  -470700 (-523*  100*+9)
  -------
   -12871
   +15690 (-523*   10*-3)
   ------
     2819
    -2615 (-523*    1*+5)
    -----
      204

... 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:

               _ _               +15690000 (die betragsmäßig kleinere Zahl wird von der betragsmäßig
 15624829:523=3195?              -15624829  größeren abgezogen, Vorzeichenkorrektur erst beim Ergebnis)
-15690000 (-523*10000*+3)        ---------
---------                           +76281 (Ergebnis ohne Übertrag, IMMER(!) positiv -
   -76281 (Ergebnis)                        weil ja kein Übertrag berücksichtigt wird)
  +523000 (-523* 1000*-1)           -11110 (Übertragsziffern, IMMER(!) negativ (oder 0))
   +11110 (Übertrag)                ------
  -------                           +65171 (Korrigierte Differenz, hier positiv)
  +568939 (Ergebnis)                       → gleich wie im vorhergehenden Beispiel
  -470700 (-523*  100*+9) ←+
  -111110 (Übertrag)         |
  -------                    +-- Basierend auf der Zahl 568735, müsste der Quotient eigentlich 
   -23981 (Ergebnis)             10 oder sogar 11 sein, da der Quotient aber nur eine Ziffer sein 
   +26150 (-523*   10*-5)        kann (positiv oder nicht), ist hier 9 das Maximum.
   +11110 (Übertrag)
   ------
   +14389 (Ergebnis)
    -???? (-523*    1*+?)
    -1110 (Übertrag)

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:

                _ _
 156|24829:523=31936
-156|90000 (-523*10000*+3)
 ===| =====
-000|????? (Teilergebnis mit Übertrag) ← Die beiden höchstwertigen Ziffern vollständig berechnet, 
-???|76281 (Teilergebnis ohne Übertrag) - (das Ergebnis kann nur um 1 vom korrekten Ergebnis abweichen)
-000|76281 (Gesamtergebnis - Teils mit, Teils ohne Übertrag)

 -007|6281 (Gesamtergebnis - Teils mit, Teils ohne Übertrag)
 +052|3000 (-523* 1000*-1)
 +001|1110 (Übertrag aus dem Teilergebnis ohne Übertrag)
  ===|==== [OK]
 +046|???? (Teilergebnis mit Übertrag)
 +???|8939 (Teilergebnis ohne Übertrag)
 +046|8939 (Gemischtes Gesamtergebnis)

  +468|939 (Gemischtes Gesamtergebnis)
  -470|700 (-523*  100*+9)
  -011|110 (Übertrag aus dem Teilergebnis ohne Übertrag)
   ===| ===
  -013|??? (Teilergebnis mit Übertrag)
  -???|181 (Teilergebnis ohne Übertrag)
  -013|981 (Gemischtes Gesamtergebnis)

   -139|81 (Gemischtes Gesamtergebnis)
   +156|90 (-523*   10*-3)
   +011|10 (Übertrag aus dem Teilergebnis ohne Übertrag)
    ===|== [OK]
   +028|?? (Teilergebnis mit Übertrag)
   +???|29 (Teilergebnis ohne Übertrag)
   +028|29 (Gemischtes Gesamtergebnis)

     282|9 (Gemischtes Gesamtergebnis)
    -313|8 (-523*    1*+6)
    -001|0 (Übertrag aus dem Teilergebnis ohne Übertrag)
     ===|=
    -032|? (Teilergebnis mit Übertrag)
    -???|9 (Teilergebnis ohne Übertrag)
    -032|9 (Gemischtes Gesamtergebnis)

     -329| (Gemischtes Gesamtergebnis)
     +000| (es folgt keine Quotientenziffer mehr)
     +010| (Übertrag aus dem Teilergebnis ohne Übertrag)
      ===|
     -319| (Divisionsrest) ← Diese letzte Addition wird vollständig mit allen 
                                Übertragsbits durchgeführt.

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.

Einzelnachweise

↑ John Cocke, Dura W. Sweeney: High speed arithmetic in a parallel device. Technical Report IBM, February 1957.
↑ James E. Robertson: A new class of digital division methods. IEEE Trans. Electronic Computers, 7 (1958), S. 218–222.
↑ Keith D. Tocher: Techniques of multiplication and division for automatic binary computers. Quart. J. Mech. Appl. Math. 11 (1958), S. 364–384.

Weblinks

uni-oldenburg.de: SRT-Division, Wiland Schmale, Professor für Mathematik im Ruhestand an der Carl von Ossietzky Universität Oldenburg, Ergänzung zu einer Mitmachvorlesung zum Thema SRT-Division (pdf; 284 kB)
tu-muenchen.de: Hauptseminar Analyse von Softwarefehlern - Pentium Bug, Boris Ljepoja, Thomas Pfennig, Stefan Rosenegger, 30. Oktober 2002

[1] John Cocke, Dura W. Sweeney: High speed arithmetic in a parallel device. Technical Report IBM, February 1957.

[2] James E. Robertson: A new class of digital division methods. IEEE Trans. Electronic Computers, 7 (1958), S. 218–222.

[3] Keith D. Tocher: Techniques of multiplication and division for automatic binary computers. Quart. J. Mech. Appl. Math. 11 (1958), S. 364–384.

[1]

[2]

[3]

SRT-Division

Inhaltsverzeichnis

Theoretische Grundlagen

Die SRT-Division in der Praxis

Herkömmliches Divisionsverfahren

Nachteile dieses Verfahrens

Saved-Carry-Addition

Keine Korrektur bei falsch geratenen Quotienten-Ziffern

Beides zusammen

Ähnliche Verfahren

Einzelnachweise

Weblinks