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

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 mit Glück und Verstand die nächste Ziffer des Quotienten abschätzen:

Beispiel

 15624829 : 523 =

Hier würde man, basierend auf den ersten Ziffern abschätzen, 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˙˙˙˙     unerwünschtes Ergebnis

Es hilft allerdings auch nicht, die nächste Ziffer immer etwas zu knapp abzuschätzen, auch dann stimmt die Ziffer nicht und man erhält zwar keinen negativen Wert, aber einen, der erfordert, diesen Stelle nochmals zu bearbeiten.

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 in diesem Schritt die −7 stehen. Dafür muss man die Subtraktion dann aber mit der gesamten Zahl durchführen:

 15624829 : 523 = 3
−1569௦௦௦௦
─────────
   −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
−1569௦௦௦௦
─────────
   −65171
  +523௦௦௦
  ───────
   457829

Führt man dieses Verfahren fort ...

                   _ _
 15624829 : 523 = 31935  Rest 204
−1569௦௦௦௦ (−523 ×1௦௦௦௦ × +3)
─────────
   −65171
  +523௦௦௦ (−523 × 1௦௦௦ × −1)
  ───────
   457829
  −4707௦௦ (−523 ×  1௦௦ × +9)
  ───────
   −12871
   +1569௦ (−523 ×   1௦ × -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:

                   _ _           +1569௦௦௦௦     die betragsmäßig kleinere Zahl wird von der betragsmäßig
 15624829 : 523 = 3195?          −15624829     größeren abgezogen, Vorzeichenkorrektur erst beim Ergebnis
−1569௦௦௦௦     −523×1௦௦௦௦×+3      ─────────
─────────                           +76281     Ergebnis ohne Übertrag, immer positiv –
   −76281     Ergebnis                         da ja kein Übertrag berücksichtigt wird
  +523௦௦௦     −523× 1௦௦௦×−1         −11110     Übertragsziffern, immer negativ bzw. 0
   +11110     Übertrag              ──────
  ───────                           +65171     korrigierte Differenz, hier positiv
  +568939     Ergebnis                         → gleich wie im vorhergehenden Beispiel
  −4707௦௦     −523×  1௦௦×+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 
   +2615௦     −523×   1௦×-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 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 normalisiert 29875.

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

Related Articles