CW-Mitarbeiter Egon Schmidt
Im Bereich der Ver- und Entschlüsselung codierter Nachrichten sowie natürlich außerdem im Graübereich jener, die sich auf das Knacken der entsprechenden Codes spezialisieren, kommen nicht selten Dualzahlen mit 150 und mehr Stellen vor. Das Problem dabei: Solche Binarzahlen-Bandwürmer müssen vielfach immer aufs neue dividiert werden - und das kostet auch auf schnellen Rechnern Zeit. Doch Abhilfe naht.
Schon der Abc-Schütze lernt rasch, daß das Subtrahieren schwieriger und langwieriger ist als das Addieren, und daß erst recht das Dividieren weit mehr Mühe, Grips und Zeit erfordert als das Multiplizieren. Nicht anders ist es im Bereich der DV. Denn moderne Algorithmen gestatten es zwar beispielsweise, mit der Multiplikation zweier "langer" Binärzahlen schon dann zu beginnen, wenn gerade erst die ersten Stellen der beiden Zahlen vom Speicher kommend, in der CPU eines Hochleistungsrechners einlaufen; doch zum Dividieren ist unabdingbar, daß zunächst alle Stellen beider Zahlen-Würmer von präsent sind. Und dabei entstehen natürlich oft Zeitverluste, die durchaus fühlbar sind.
Das hier skizzierte Problem mag bei kleinen Maschinen wie einem PC nucht weiter von Belang sein, denn einmal ist hier die Maschinenzeit kein so kostbares Gut wie auf einem Groß-System, und zum anderen haben jene Rechner ja eher in Ausnahmefällen mit den besagten langen Zahlen zu tun. Doch bei bestimmten, schnellen Großrechnern wird im Falle der Division zweier vierstelliger Zahlen aus Tempo-Gründen geschickt ein alter Trick genutzt: Man bildet zunächst den Kehrwert des Divisors und läßt den Rechner erst danach eine recht schnell ablaufende - Multiplikation ausführen. Denn "Dividend mal Kehrwert des Divisors" ergibt ja das gleiche wie die gewöhnliche Division "Dividend-durch Divisor".
Mit diesem ehrwürdigen Trick kann man nun zwar das Dividieren beschleunigen - doch befriedigend ist das Resultat, betrachtet man die Geschwindigkeit, immer noch nicht. Und so ersann Ernest F. Brickell von Bell Communications Research in Morristown, New Jersey, USA, jetzt ein neues Verfahren, bei dem zwischenzeitlich einfach kurz mal das Zahlensystem gewechselt wird: Denn beim Brickell-Algorithmus wird ein Zwischenergebnis der Division nicht mehr im Dual- oder auch Binär-System mit seinen Nullern und Einsern dargestellt, sondern in einem
Ternärsystem, das auch noch Zweier kennt.
So ein Ternärsystem kann man sich in der Form plastisch vor Augen führen, daß man einfach mal die ersten sieben natürlichen Zahlen betrachtet. Im gewöhnlichen Zahlensystem lauten sie auf 0, 1, 2,. . ., 6. 7 und im bekannten Binärsystem auf 000, 001, 010, 011, 100, 101, 110und
111. In ternärer Darstellung hingegen ergeben sich die Zahlen 000, 001, 002, 010, 01 1, 012, 020 und 021; jede Stelle kann einen von drei verschiedenen Werten (0, 1 und 2) annehmen.
Brickell hat sich nun mit Hilfe dieses Ternärsystems einen Algorithmus überlegt, bei dem der Rechner - beziehungsweise ein spezieller, derzeit von Brickell und seinen Kollegen entwickelter Chip - den Dividenden und auch den Divisor in Gestalt gewöhnlicher Dualzahlen zugeführt bekommt und sogleich nach Einlaufen der ersten paar Stellen jeder Zahl mit der Division beginnen kann; dabei wird der Divisor in gewöhnlicher Form, und nicht etwa als inverser Wert (Kehrwert), eingesetzt. Doch das Ergebnis der hier nun ablaufenden Division wird zunächst im ternären System, errechnet und zwischengespeichert, ehe es, in einem weiteren Schritt, der keinen großen Aufwand erfordert, wieder in das vertraute Eins/Null-Dualsystem zurückverwandelt wird.
Mit diesem neuen Algorithmus und der Verwendung von sozusagen "dreiwertigen Bits" hat Brickell erreicht, daß auch die Division langer Zahlen fast ebenso schnell ablaufen kann, wie die CPU des Rechners diese Zahlen zugeführt bekommt. Und das kann, von weiteren denkbaren Anwendungen einmal ganz abgesehen, beim Chiffrieren und Dechiffrieren vertraulicher Nachrichten eine wesentliche Zeitersp
arnis bedeuten - beim Knacken der zugehörigen Codes vermutlich auch.