Zahlen, die zu einer anderen Basis als 10 dargestellt werden, insbesondere binär, werden mit der Basis dahinter tiefgestellt notiert; die Basis selbst wird immer dezimal notiert. So ist . Der Index 2 entfällt, wenn von Bitmustern o. Ä. die Rede ist, also nicht der numerische Wert im Vordergrund steht. Bitmuster werden in Schreibmaschinenschrift dargestellt, sofern technisch möglich.

Universal numbers, kurz Unum,[1] sind ein Gleitkommazahlen-Format, das von John L. Gustafson, bekannt durch Gustafsons Gesetz, als Alternative zu den vorherrschenden IEEE-754-Gleitkommazahlen entwickelt wurde. Die erste Version von Unums wird retrospektiv als Typ I bezeichnet, als danach Typ II und später Typ III veröffentlicht wurden.

“Some people are surprised that π can be represented as an exact number, but of course it can, which is one reason for the term ‘universal number.’”

„Einige überrascht es, dass π exakt dargestellt werden kann, aber natürlich geht das, und es ist einer der Gründe für den Begriff universal number.“

John L. Gustafson: A Radical Approach to Computation with Real Numbers[2]

Der wesentlichste interne Unterschied zu IEEE-754-Gleitkommazahlen ist das variable Format. Während durch den IEEE-754-Standard – lediglich abhängig von der Bit-Zahl – eine feste Anzahl von Exponenten- und Mantissen-Bits vorgeschrieben ist, sind diese bei Unums variabel. Allen Unum-Formaten ist gemein, dass arithmetische Über- und Unterläufe nicht zu Unendlichkeiten degenerieren, sondern bei dem betragskleinsten bzw. -größten Intervallen bzw. Zahlen verbleiben. Laut Gustafson ist der numerische Fehler beim Abgleiten von endlichen Ergebnissen ins Unendliche unendlich, wohingegen das Zuweisen eines endlichen Werts möglicherweise ein großer, jedoch endlicher Fehler ist.

Zahlenmodell

Bearbeiten
 
Darstellung der projektiven Geraden als Kreis mit   unten,   oben,   links und   rechts

Das mathematische Zahlenmodell hinter Typ-II- und Typ-III-Unums ist die projektive Gerade, also die reellen Zahlen zusammen mit einem unendlich fernen Punkt  , der durch Zahlen mit großem Betrag erreicht wird, egal ob negativ oder positiv. Wie   ist   ohne Vorzeichen und wird von der negativen und der positiven Seite gleichermaßen erreicht. In der Praxis von Gleitkommazahlen sind  , unendliche und undefinierte Werte grundsätzlich Spezialfälle; gewisse Metriken, die beispielsweise relative Genauigkeit angeben, sind darauf nicht sinnvoll anwendbar. Bei Unums wird   für undefinierte Werte verwendet. Operationen auf endlichen Zahlen, die mathematisch wohldefiniert sind, produzieren nie   als Ergebnis. Somit entspricht   mehr einem quiet NaN aus IEEE 754 als dessen unendlichen Werten. Wird beispielsweise durch die Addition zweier großer Zahlen der Wertebereich nach oben verlassen, runden IEEE-754-Gleitkommazahlen zu  ; in Typ-I- und Typ-II-Unums ist das Ergebnis dann ein Objekt, das das offene Intervall zwischen der größten exakt darstellbaren Zahl und   beschreibt. Typ-III-Unums stellen keine Intervalle dar, sie verbleiben dann bei dem größten endlichen Wert.

Das Zahlenmodell hinter Typ-I-Unums und IEEE 754 ist hingegen die abgeschlossene reelle Gerade, also die reellen Zahlen zusammen mit separaten Werten für   und  . Dazu gesellen sich außerdem undefinierte Werte, auch NaN für engl. not a number genannt. Ferner unterscheidet IEEE 754 die Zahlen   und  .

Grundsätzlich gibt es für jedes Unum   ein eindeutiges, genau dargestelltes Negatives   und bei Typ-II-Unums einen eindeutigen, genau dargestellten Kehrwert  , wohingegen ein solcher Kehrwert für Typ-III-Unums nur für   und Zweierpotenzen garantiert ist.[3] In der üblichen Darstellung der projektiven Geraden (s. Bild) entspricht die Negation der Spiegelung an der vertikalen und die Kehrwertbildung an der horizontalen Achse; insbesondere gilt   und  .

Die erste Format von Unums, im Nachhinein Typ I genannt, war als Erweiterung der IEEE-754-Gleitkommazahlen konzipiert. Es verwendet in seiner Darstellung ein ubit (u für engl. unprecise, unpräzise) am Ende, das angibt, ob die Zahl präzise   oder ein offenes Intervall zwischen nebeneinanderliegenden Gleitkommazahlen ist ( ). Das Layout ist dasselbe wie bei IEEE-754-Gleitkommazahlen, jedoch variiert die Anzahl der Exponenten- und Mantissenbits automatisch bzw. sind beide frei wählbar. Typ-I-Unums sind eine einfache Lösung für Intervallarithmetik.

Gustafson entwickelte Typ-II-Unums aus der Erfahrung, dass die IEEE-754-Kompatibilität wenig Nutzen bringt, aber viel Aufwand verursacht, der Teil mit Intervallarithmetik sich hingegen effizient umsetzen ließ.

Die zweite Version von Unums verwirft die Kompatibilität zu IEEE-754-Gleitkommazahlen zugunsten großer Flexibilität. Die Haupterkenntnis war, dass sich vorzeichenbehaftete ganze Zahlen gut auf die projektive Gerade abbilden lassen, wobei der Überlauf bewusst in Kauf genommen wird, dafür die Ordnungsrelation erhalten bleibt. Insbesondere hat bei vorzeichenbehafteten Ganzzahlformaten mit Zweierkomplement-Darstellung von negativen Zahlen die kleinste negative Zahl (die mit maximalem Betrag) die Eigenschaft, ihr eigenes Negatives zu sein. Als Ganzzahl ist dieser Randfall gelegentlich ein Hindernis, für den unendlich fernen Punkt in der projektiven Geraden ist diese Eigenschaft hingegen natürlich und wünschenswert.

Wie Typ-I-Unums interpretieren Typ-II-Unums das letzte Bit in der Darstellung als ubit, das ein offenes Intervall zwischen exakten Zahlen repräsentiert. Diese Intervalle können am Ende der Berechnung kollabiert werden, etwa auf ihren arithmetischen oder geometrischen Mittelpunkt.

Für ein  -Bit-Typ-II-Unum-Format werden   reelle, nicht notwendigerweise rationale, Zahlen größer als   ausgewählt und im ersten Quadranten auf der projektiven Geraden angesiedelt. Die anderen Quadranten ergeben sich durch Negativen- und Kehrwertbildung. Ein  -Bit-Wort hat   Zustände, davon wird die Hälfte von Intervallen belegt und drei beliebige der vier Quadranten ergeben sich aus dem jeweils vierten. Da   als Wahl fest vergeben wird, gibt es eine Option weniger als  .

Ein Beispiel für ein dezimales 8-Bit-Format: Gewünscht wird die exakte Darstellung der   Zahlen  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  . Die als Inverse angegebenen Zahlen sind Wünsche für den vierten Quadranten, auf eine Weise ausgedrückt, auf die sie ins Schema passen.

Die Operationen für Typ-II-Unums lassen sich im Allgemeinen nur durch eine Wertetabelle implementieren, was sie für Bitzahlen größer als ca. 20 behäbig macht, da Wertetabellen für zweistellige Operationen quadratisch anwachsen.

Gustafson entwickelte Typ-III-Unums, da sich Typ-II-Unums als schwerfällig für verschmolzene (engl. fused) Operationen wie Fused multiply-add herausstellten. Das Ziel von Typ-III-Unums ist also, die Vorteile von Typ-II-Unums software- und hardware-freundlich umzusetzen.

Da die Formate vom Typ I und II die Zahlenbereiche flexibel und anwendungsspezifisch zulassen, reichen oft geringe Bitlängen aus. Im Fall von 8 Bit kann bereits ein 256-Bit-Wort eine beliebige Vereinigung von Intervallen darstellen (da 28 = 256, siehe Kardinalität der Potenzmenge). In diesem Kontext werden die exakten Zahlen als Einermenge mit ebendieser Zahl und   als die Paarmenge   gesehen, aber der Einfachheit wegen auch als Intervall bezeichnet. Ein so interpretiertes Wort heißt SoRN für engl. Set of Real Numbers, zu deutsch (Teil-)Menge der reellen Zahlen. Dabei gibt das  ‑te Bit an, ob das Intervall mit der Darstellung   eine Teilmenge der SoRN ist. Als Ergebnis einer Operation bedeutet ein SoRN, dass die mathematisch exakte Lösung darin enthalten ist. Eine korrekte Implementierung vorausgesetzt, ist die Aussage im mathematischen Sinn wahr und keine Approximation mit unbekannten Fehlerschranken.

Die Angabe von SoRNs ist üblicherweise als Intervall oder als Vereinigung von Intervallen, falls Lücken bestehen. Dabei wird hier der Deutlichkeit wegen in der unteren Grenze   und in der oberen Grenze   geschrieben. Insbesondere stellt das Intervall   die Menge der reellen Zahlen dar. Als offenes Intervall ist ansonsten   die leere Menge.

Im Vergleich zu Intervallarithmetik sind SoRNs auch dann gutartig, wenn sonst Stellenauslöschung oder durch unerkannte Abhängigkeiten jeder Iterationsschritt zu einem exponentiellen Genauigkeitsverlust führt. Wenn nicht gerade mit einem einelementigen Intervall begonnen wird, divergiert beispielsweise jede Folge von Intervallen nach traditioneller Intervallarithmetik, die durch wiederholte Anwendung der Operationen   oder   entsteht (das heißt, die Intervalle werden immer größer und damit als Abschätzung unbrauchbar), wohingegen die von SoRNs beschriebenen Intervalle stetig kleiner werden und das Ergebnis festnageln.[2]

Arithmetik

Bearbeiten

Auf SoRNs lässt sich die Arithmetik der Unums fortsetzen: Sind   und   zwei SoRNs, so ist   das SoRN, das aus den Unums   mit   aus   und   aus   besteht. Analog wird Multiplikation definiert; Subtraktion und Division ergibt sich als   gemäß   und entsprechend   gemäß  . Die einstelligen Operationen   und   werden auf die Einzelelemente angewendet. In mathematischer Notation:

 
 
 
 
 
 

Mit SoRNs sind auch Operationen möglich, deren Ergebnis auch im mathematischen Sinn nicht immer eine einzelne Zahl ist. Beispielsweise ist die Quadratwurzel-Funktion für negative Eingaben undefiniert. Als Operation auf SoRNs liefert   entsprechend das leere SoRN. Grundsätzlich ist es zwar möglich, auf jede undefinierte Operation das leere Ergebnis zu liefern, aber in gewisser Hinsicht sind andere Ergebnisse oft besser. Beispielsweise ist   die Antwort auf Frage: Welche Zahl   löst die Gleichung  ? Für   und   ist diese Antwort: jede Zahl. Daher ergibt   das volle SoRN. Dasselbe gilt für   und   (was dasselbe sein muss, da  ). Ein Beispiel für eine undefinierte Operation, die weder das leere noch das volle SoRN liefert, ist   mit der Lösungsmenge  , also einem SoRN, das  ,   und alle positiven Intervalle umfasst.

Beispielsweise gegeben das SoRN  . Der Logarithmus davon (egal zu welcher Basis) ergibt  . Das Quadrat von diesem Ergebnis ist  .

Ein weiteres Beispiel sei die Funktion   mit  .[2] Was ist  ? Eine Rechnung mit Unums ergibt  . Nun ist es so, dass auch   ist, wodurch die Definitionslücke bei 0 verschwindet, und das Ergebnis bestätigt. Doch was, wenn die Eingabe nicht genau bekannt war, sondern als das SoRN   gegeben wird? Wird die erste Darstellung von   verwendet, liefern die Operationen auf 4-Bit-Unums exakte Ergebnisse und das Ergebnis-SoRN repräsentiert die Aussage  . Für den zweiten Ausdruck mit traditioneller Intervallarithmetik wird zuerst das Eingabeintervall   zu   abgeschlossen (da traditionelle Intervallarithmetik nur mit abgeschlossenen Intervallen arbeitet). Das Ergebnis ist dann ernüchternd:  . In der zweiten Darstellung kommt   zweimal vor; dass es sich dabei zweimal um derselben Wert (innerhalb der Grenzen) handeln muss und nicht um zwei unabhängige Werte mit denselben Grenzen, wird aber beim mechanischen Auswerten nicht berücksichtigt.

Lauflängen-Kodierung

Bearbeiten

Ein SoRN gilt als zusammenhängend, wenn in seiner Darstellung alle Einsen gepackt nebeneinander stehen (schließt das leere SoRN mit ein). Weil   an beiden Enden des Zahlenstrahls liegt, aber nur einmal im SoRN kodiert wird, ist das SoRN   im mathematischen Sinn zwar nicht zusammenhängend (genauer: im Sinne der projektiven Geraden ist die Menge schon zusammenhängend, aber nicht im Sinne eines Zahlenstrahls mit Endpunkten), wohl aber das SoRN, das es darstellt. Die arithmetischen Grundoperationen und viele andere wie die Wurzel erhalten zusammenhängende SoRNs, das heißt, für zusammenhängende SoRNs als Eingaben liefern sie zusammenhängende SoRNs als Ergebnis. Daher bietet sich eine sogenannte Lauflängen-Kodierung (engl. run-length encoding) an. Statt mit beliebigen SoRNs werden damit nur zusammenhängende dargestellt. Die Lauflängen-Kodierung speichert den Beginn und die Länge der Einser-Kolonne. Für 256 Stellen genügen 8 Bit für je den Beginn und die Länge, somit benötigt die Lauflängen-Kodierung insgesamt 16 Bit. Nur das volle SoRN ist zusammenhängend, kann aber streng genommen nicht so dargestellt werden, da seine Länge (256 Einsen) gerade das Maximum (255) in der Längendarstellung überschreitet. Dem kann abgeholfen werden, da für das leere SoRN formal mehrere Darstellungen existieren, nämlich alle mit Länge 0. Davon wird eine für das volle SoRN umgedeutet.

Insbesondere ist eine Lauflängen-Kodierung für SoRNs effektiver, je höher die Anzahl der Bits ist. Für 16-Bit-Unums wäre ein allgemeines SoRN 65.536 Bit breit, also knapp 8 KiB groß. Die Lauflängen-Kodierung benötigt nur 32 Bit.

Beispiel

Bearbeiten

Für das Beispiel wird ein 4-Bit-Typ-II-Unum verwendet, wobei die einzige wählbare Zahl 2 ist. Es gibt die 16 Intervalle  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,   und  . Ein Teilmengen-Wort besteht damit aus   Bit.

Allgemein braucht es die Lauflängen-Kodierung von   Bit genau   Bits.

Das System der Typ-III-Unums wird auch als Posits and Valids bezeichnet. Das englische Wort posit bedeutet Postulat. Die Posits sind die eigentlichen Zahlen, mit denen gerechnet wird; die Valids definieren Intervalle mit Grenzen von Posits gleichen Formats. Der primäre Zweck von Valids ist Fehlerabschätzung, die sich durch die hohe Fehlertoleranz der Posit-Grenzen oft in brauchbaren Rahmen bewegt. Der große Vorteil von Intervallarithmetik ist (typischerweise), dass das wahre Ergebnis garantiert innerhalb der Intervallgrenzen liegt. Intervallarithmetik läuft daher immer Gefahr, dass die untere und obere Intervallgrenze so weit auseinander liegen, dass die Aussage zwar richtig ist, das Ergebnis aber praktisch keine Aussagekraft mehr besitzt.

IEEE-Gleitkommazahlen erlauben bei der Auswertung der vom Standard vorgeschriebenen transzendenten Funktionen Fehler, die über den Rundungsfehler hinausgehen, hauptsächlich damit die Wertetabellen in der Hardware nicht zu groß werden. Solche Zugeständnisse machen Posits nicht.[3] Im Gegenteil: Implementierungen von Typ-III-Unums müssen eine Skalarprodukt-Operation (auch Fused dot-product genannt) anbieten, deren Ergebnis präzise auf das letzte Bit berechnet wird. Die Operationen Fused multiply-add und Fused sum sind Spezialfälle des Skalarprodukts. (Präzise heißt innerhalb der Rundungsgenauigkeit.) Das Skalarprodukt ist außerdem nicht in der Länge beschränkt; Implementierungen müssen mit jeder Anzahl von Summanden rechnen. Dazu wird ein Puffer verwendet, Quire genannt. Geeignete Quire-Größen sind in einer Tabelle unten aufgelistet.

Die Posits bestehen aus einem Vorzeichen-Bit (engl. sign), einer variablen Anzahl von Regime-Bits, die über grobe Größenordnung entscheiden (und zu denen kein IEEE-754-Äquivalent existiert), Exponenten-Bits und Mantissen-Bits.

Die Anzahl der Regime-, Exponenten- und der Mantissen-Bits variiert.[3] Bestimmungsgrößen eines Unum-Formats sind seine Gesamtbits (in der Praxis meist eine Zweierpotenz) und seine maximalen Exponentenbits  . Ein  Bit-Unum erlaubt nach Abzug des Vorzeichenbits für einen konkreten Posit zwischen   und   Regime-Bits. Aufgrund der Konstruktion muss die Anzahl der Regime-Bits mindestens   betragen (zur Konstruktion s. unten). Nimmt das Regime mehr Bits ein, als gemäß Gesamtbits minus   verbleiben, ist die Anzahl der Exponentenbits nachrangig, entsprechend reduziert und kleiner als  . Die ggf. übrigen Bits entfallen auf die Mantisse.

In der Anwendung kann der unendlich ferne Punkt   durch   ersetzt werden, was für keine reelle Zahl steht (englisch not a real number). Alle Operationen auf   ergeben wieder  , insbesondere ist  , wohingegen   ist. Als Grund für die Abweichung von keine Zahl (englisch not a number, kurz NaN) nennt Gustafson, dass es sich bei einigen Ergebnissen wie   um (komplexe) Zahlen handelt.[4]

Beispielformat

Bearbeiten

Gegeben das Format mit   Bits und  . Hat ein solches Posit   Regime-Bits, ergibt sich die Verteilung 1 : 4 : 2 : 9 auf Vorzeichen, Regime, Exponent und Mantisse. Hat es 12 Regime-Bits ist die Verteilung 1 : 12 : 2 : 1 und bei 14 Regime-Bits 1 : 14 : 1 : 0.

Kennzahlen

Bearbeiten

Aus der Anzahl der Gesamtbits und der maximalen Exponentenbits ergibt sich die Kennzahl des   (u für Unum und engl. seed für Samen oder Keim) als  . Für ein Unum-Format mit bis zu   Exponentenbits beträgt  . Bei bis zu 3 Exponentenbits beträgt das   und bei   schon  .

Im Unterschied zu IEEE 754 haben Unums keinen Exponenten-Bias oder eine vergleichbare Größe.

Menge der Zahlen

Bearbeiten

Da die negativen Zahlen und die Bitmuster ihrer Darstellungen aus den positiven hervorgehen, müssen nur letztere beschrieben werden. Die Menge der  Bit-Unums wird iterativ erzeugt, wobei   sein muss. Ausgehend vom einfachsten Format bestehend aus  -Bit-Unums, die jeweils nur aus Vorzeichen (1 Bit) und Regime (min.   Bit, s. unten für eine Begründung), wird das Format für   Bits durch Anfügen eines Bits an das Format mit   Bits definiert. Mit   wird die größte positive und mit   die kleinste positive Zahl im aktuellen Format bezeichnet. Zwar gilt  , die Gleichheit gilt jedoch nur, falls es Zweierpotenzen sind.

Die Menge der  -Bit-Unums besteht aus   Elementen:   und  ,   und   sind fest vorgegeben; dazu kommt das von der maximalen Anzahl   von Exponentenbits abhängige  , zusammen mit  ,   und  . (Dabei ist   frei wählbar.) Auch wenn keine Darstellung im  Bit-Format Exponentenbits nutzt, weil die Regime-Bits „immer alles auffressen“, wird   festgelegt, da der Wert von   davon abhängt. Bei der iterativen Darstellung der Zahlenmenge bleibt   gleich, nur die Bitanzahl wird erhöht. Das  Bit-Unum ist lediglich der Startpunkt der Konstruktion. Im  Bit-Format ist  .

Für den Schritt vom  Bit-Unum zum  Bit-Unum wird an jede Darstellung ein Bit angefügt. Ist dieses Bit 0, bleibt der repräsentierte Wert derselbe, unabhängig ob das Bit dem Regime, dem Exponenten oder der Mantisse zufällt. Ist das Bit 1, so stellt das Bitmuster eine neue Zahl dar, die zwischen den beiden Zahlen liegt, deren Darstellungen, interpretiert als ganze Zahl, je um   größer und kleiner sind:

  • Zwischen   und   wird   eingefügt und entsprechend   zwischen   und  . Das hinzugefügte Bit wird Teil des Regimes.
  • Zwischen   und  , wobei   und   mehr als   auseinanderliegen, wird das geometrische Mittel von   und   eingefügt:  . Das hinzugefügte Bit wird Teil des Exponenten.
  • Andernfalls wird zwischen   und   ihr arithmetisches Mittel   hinzugefügt. Das hinzugefügte Bit wird Teil der Mantisse.

Der erste Punkt fügt viele exponentiell auseinanderliegende Zahlen an den extremen Rändern hinzu. In einem gewissen Sinne approximieren sie   und   damit gut. Der letzte Punkt fügt viele linear auseinanderliegende Zahlen um   ein. Exponentiell bzw. linear auseinanderliegend bedeutet: Sind   aufeinanderfolgend, so ist im ersten Fall   und im zweiten Fall  . Konstruktionsbedingt ist die Summe   im zweiten Punkt eine gerade ganze Zahl, deren Hälfte somit eine ganze Zahl ist.

Die ersten Konstruktionsschritte für die positiven Posits mit  , das heißt mit  , sind:

  • Ausgangsformat mit   Bits
 
 ;   und  .
  • Format mit   Bits:
 
 ;   und  .
  • Format mit   Bits:
 
 ;   und  .
  • Format mit   Bits:
 ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,    ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  
 ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ,  ;   und  .

Ist   die Menge der  Bit-Unum mit höchstens   Exponentenbits, so gilt

 ,

das heißt, es werden keine Bitmuster verschwendet. Außerdem ist durch die Beziehung

 

gesichert, dass eine Erhöhung der Bitanzahl nur mehr Zahlen dargestellt werden können, aber keine verschwinden.

Die Menge

 

der durch Unums darstellbaren projektiven reellen Zahlen liegt dicht in  , was bedeutet, dass sich jede reelle Zahl beliebig genau durch ein Unum approximieren lässt.

Interpretation eines Bitmusters

Bearbeiten

Ausgenommen   soll die Ordnung auf Postits mit der Ordnung auf ihren Darstellungen übereinstimmen, wobei die Darstellungen als vorzeichenbehaftete ganze Zahlen in Zweierkomplement-Darstellung interpretiert werden. Aus der Menge der Zahlen und dieser Voraussetzung ergibt sich bereits eindeutig, welche Zahl von einer beliebigen Postits-Darstellung beschrieben wird. Hier folgt ein anschauliches, effektives Verfahren.

Besteht das Bitmuster aus 000, so repräsentiert es  ; besteht es aus 100, so repräsentiert es  . Nachfolgend werden diese beiden Fälle ausgeschlossen.

Das Vorzeichen ist das erste (= höchstwertige) Bit  . Wie bei IEEE 754 ist die Interpretation, dass für   die Zahl positiv und für   negativ ist. Davon ausgenommen sind die Werte   und  ; tatsächlich hat   technisch gesehen das Vorzeichenbit 0 und   das Vorzeichenbit 1, dennoch werden beide als weder positiv noch negativ bezeichnet. Im Unterschied zu IEEE-Gleitkommazahlen speichern Posits nicht ein Vorzeichen und einen Betrag.

Die folgenden Betrachtungen werden für   angegeben. Ist  , so wird die Zahl vor dem Bestimmen der Kennzahlen per Zweierkomplement nicht-negativ gemacht.

Die Lauflänge   (engl. run-length) einer konkreten Zahl ergibt sich aus den Regime-Bits. Das Regime folgt auf das Vorzeichen und besteht aus einer Folge gleicher Binärziffern, die durch die jeweils andere Binärziffer beendet wird oder bis zum Ende läuft. Das Regime hat also immer die Form 001 oder 110 oder, falls das Regime den kompletten Rest der Zahl einnimmt, 111 und die kürzestmögliche Formen sind 01, 10 und 11. Für Gesamtlänge 5 sind die möglichen Regimes zwischen 2 und 4 Bits lang, konkret 0001, 001, 01, 10, 110, 1110 und 1111. Führen Nullen das Regime an, so ist   die Anzahl dieser Nullen, also ist   negativ. Für 0001 ist   usw. bis 01 für  . Führen hingegen Einsen das Regime an, so ist   die Anzahl dieser Einsen, also ist   positiv oder null. Für 10 ist   für 110 ist   usw. bis 1111 für  . Das Regime kann nicht aus nur Nullen bestehen, denn dann wäre das Bitmuster (je nach Vorzeichenbit) das für   oder   (s. oben).

Es bezeichnet   den numerischen Wert der Exponentenbits, ggf. ergänzt um Nullen, interpretiert als vorzeichenlose binäre Zahl. Ist nämlich die Anzahl der Exponentenbits kleiner als  , werden für die Bestimmung von   fiktive Nullen an das Bitmuster angefügt, sodass die vorzeichenlose Zahl aus genau   binären Ziffern besteht.

Sind in der Darstellung am Ende noch Bits übrig, die nicht vergeben wurden, so entfallen sie auf die Mantisse. Gibt es   Mantissenbits und ist  , so sei   der numerische Wert der Mantissenbits, interpretiert als vorzeichenlose binäre Zahl; andernfalls setze  .

Für die Bestimmung des numerischen Werts eines Unums aus seinem Bitmuster ist

 .

Anschaulich trägt die Mantisse den Faktor   (in Binärdarstellung) bei, wobei   die binären Ziffern in der Mantisse bezeichnen. In den Begriffen von IEEE 754 ist das Hidden Bit immer 1 und Unums haben generell auch keine subnormalen Zahlen. Der Wert von   ist so gewählt, dass   gilt. Dadurch ist die Darstellung auch eindeutig.

Die Lauflänge erzeugt sehr schnell sehr große oder kleine Beträge auf Kosten der Genauigkeit in der Mantisse, jedoch lassen kurze Regimes, also Lauflängen nahe   und somit Zahlen nahe  , viel Platz für Mantissenbits. Dadurch lassen sich im Vergleich zu IEEE-754-Gleitkommazahlen bei derselben Gesamtbitzahl sowohl betragsmäßig größere Zahlen darstellen als auch Zahlen um   genauer auflösen.

Konsequenzen der Darstellung

Bearbeiten

Ein Posit wird negiert, indem seine Darstellung als Ganzzahl gemäß Zweierkomplement negiert wird. Da die Zweierkomplement-Operation sowohl die Darstellung der   als auch die Darstellung von   gleich lässt, wird für deren Negation keine Sonderfallbehandlung gebraucht.

Durch die Zweierkomplement-Darstellung ist der Größer-/Kleiner-Vergleich ohne Bestimmung der Kennzahlen möglich (sofern das Format, also Gesamtbreite und  , gleich ist). Mit Ausnahme von   ist ein Posit kleiner bzw. größer als ein anderes, falls ihre Darstellungen interpretiert als vorzeichenbehaftete Ganzzahlen dieselbe Relation haben. Die Zahlen müssen nicht aufwendig decodiert werden.

Beispielbitmuster

Bearbeiten

Als Typ setze ein 16-Bit-Unum mit Exponentenlänge   ein. Die Zahl hat das Bitmuster 0:0001:101:11011101, dabei trennt der Doppelpunkt Vorzeichen-, Regime-, Exponenten- und Mantissenbits.

  1. Sonderfälle 0 und  : Liegen nicht vor.
  2. Bestimme  .
  3. Vorzeichen 0:  .
  4. Laufweite 0001:  : Es führen 3 Nullen, somit  , d. h,  .
  5. Exponent 101:  .
  6. Mantisse 11011101:   mit  .

Daraus ergibt sich

 
 
 

Der letzte Ausdruck ergibt  .[5]

Tabelle mit Beispielwerten

Bearbeiten

Für ein weiteres Beispiel betrachten wir das Format mit 8 Bits und   sowie  . Dann ist   bzw.  . Einige Zahlen und ihre Werte sind in der Tabelle unten eingetragen.

Falls die Anzahl der Exponentenbits kleiner als   ist, werden die impliziten Exponentenbits unterstrichen.

Werte von  ,  ,  ,   und   für   Interpretation
für  
Bitmuster Werte von  ,  ,  ,   und  
für  
Interpretation
für  
nicht definiert   10000000 nicht definiert  
    01111111    
    01111110    
    01111101    
    01111001 01111001    
    01110101 01110101    
    01101101 01101101    
    01101010 01101010    
    01001110 01001110    
    01001101 01001101    
    01000011 01000011    
    01000010 01000010    
    01000001 01000001    
    01000000 01000000    
    00111111 00111111    
    00111110 00111110    
    00111101 00111101    
    00110010 00110010    
    00100101 00100101    
    00011111 00011111    
    00010101 00010101    
    00001110 00001110    
    00000101 00000101    
    00000011    
    00000010    
    00000001    
nicht definiert 0 00000000 nicht definiert 0

In den fünf Zeilen um die Eins ist deutlich, dass die Kehrwerte nicht eindeutig darstellbar sind, aber auf die korrespondierenden Werte abgebildet werden. Exakte Kehrwerte existieren genau für die Zahlen mit  , also Zweierpotenzen. Weil das Regime für Zahlen mit sehr großem oder sehr kleinem Betrag viele Bits einnimmt und so zunehmend wenige für die Mantisse übrig lässt, sind an den Rändern besonders viele Zweierpotenzen. Durch großes   lässt sich dieser Effekt verstärken, jedoch auf Kosten von Zahlen in der Nähe von   (und entsprechend  ). In der Praxis ist   eher klein, so ist   für 8-Bit-Unums eine typische Wahl.

Darstellen einer Zahl als Posit

Bearbeiten

Für   und   ist die Darstellung klar. Für   bestimmt man das Bitmuster von   und wendet darauf das Zweierkomplement an.

Sei also   darzustellen. Zuerst bestimme die Lauflänge   maximal oder (mit anderen Worten) bestimmt   (wobei   das Runden zur nächsten ganzen Zahl in Richtung   bedeutet). Dadurch sind die Regime-Bits eindeutig festgelegt. Falls noch Bits für den Exponenten übrig sind, bestimme   maximal, d. h.  . Falls noch   Bits für die Mantisse übrig sind, bestimme

 .

Dann gilt

 ,

jedoch ist   nicht notwendig ganzzahlig. Daher wird   als der gerundete Wert von   bestimmt (mit der üblichen Rundung zur nächstgelegenen ganzen Zahl), wobei zur nächsten geraden Zahl gerundet wird, wenn   genau zwischen zwei ganzen Zahlen liegt. Zuletzt stellt man   und   binär dar, wobei   im Allgemeinen nicht eingesetzt wird, sondern einaddiert. Beim Runden von   kann ein Überlauf auftreten, denn sind   Mantissenbits vorgesehen, kann es vorkommen, dass der Wert von   genau   Bits zur Darstellung braucht. Möglichst einfach formuliert wird die Darstellung für das Posit mit fiktivem   mit der Darstellung von   addiert (die Darstellungen interpretiert als Ganzzahl). Passt   in   Bits, ist das dasselbe als würden die letzten Bits einfach gesetzt. Im Ausnahmefall führt dies zur korrekten Anpassung des Exponenten und ggf. Regimes. Eine Ausnahmebehandlung, um nicht einen endlichen Wert auf   zu runden, ist nicht notwendig, da am oberen Rand des Zahlenbereichs die Regime-Bits die komplette Darstellung einnehmen und weder   noch   berechnet werden.

Beispiel   für das 8-Bit-Format mit  . Dann ist   und  , also ist die Lauflänge  ; die Regime-Bits sind somit 001. Es bleiben nach Abzug des Vorzeichenbits noch ein Exponenten-Bit und drei Mantissen-Bits. Für den Exponenten ergibt sich  , also abgerundet,  . Für die Mantisse ergibt sich

 

und so ergibt sich nach Rundung  . Für die Darstellung bestimmt man   und   und es ergibt sich 0:001:0:101. Gegenrechnen ergibt

 

Der Wert findet sich auch in der Tabelle oben.

Beispiel   für das 8-Bit-Format mit  . Dann sind   und  . Es ergibt sich insbesondere

 .

Nun passt   nicht in   Bits. Die Darstellung ohne   wäre 0:01:1:0000 was mit   addiert wird. Das ergibt 0:10:0:0000, was die Zahl   darstellt. Die größte Zahl kleiner als   wird von 0:01:1:1111 dargestellt und ist  

Die Werte finden sich in der Tabelle oben.

Beispiel   für das 8-Bit-Format mit  . Dann ist   und  , also ist die Lauflänge  ; die Regime-Bits sind somit 01. Es bleiben noch 3 Exponenten- und 2 Mantissen-Bits. Für den Exponenten ergibt sich  , also  . Für die Mantisse ergibt sich

 .

Daraus ergibt sich  . Die Darstellung ist also 0:01:100:10. Gegenrechnen ergibt

 .

Auch dieser Wert findet sich auch in der Tabelle oben.

Der relative Fehler beträgt beim ersten Beispiel   und beim letzten  . Die Beispiele zeigen, dass der größere Wertebereich mit einem Genauigkeitsverlust erkauft wird.

Ausnutzen der Posit-Darstellung

Bearbeiten
 
Gegenüberstellung der schnellen Sigmoid-Funktion und der fast_sigmoid-Implementierung für 8-Bit Posits

In einem 8-Bit-Unum mit   kann die Sigmoidfunktion   näherungsweise sehr schnell berechnet werden, indem die Darstellung der Unums ausgenutzt wird. Statt aufwendig die Exponentialfunktion auszuwerten, wird das Vorzeichenbit invertiert und die Darstellung logisch um 2 Stellen nach rechts verschoben. In C entspricht das dem Ausdruck (x ^ 0x80) >> 2.[3] Von der Idee her ist der Ansatz ähnlich wie der zur Berechnung des Kehrwerts der Quadratwurzel.

Standard-Posits

Bearbeiten

Für die Bitzahlen 16, 32, 64, 128 und 256 existieren IEEE-754-Formate. Geeignete Wahlen von   nähern deren Wertebereiche an.

Bits Exp.
(IEEE)
Wertebereich
(IEEE)
 
(Posit)
Wertebereich
(Posit)
Quire-Bits
(Posit)
      bis  0 n. a.
      bis       bis    0
      bis       bis    
      bis       bis    
      bis       bis    
      bis       bis    
Bearbeiten

Einzelnachweise

Bearbeiten
  1. Walter F. Tichy: The End of (Numeric) Error: An interview with John L. Gustafson. In: Ubiquity - Information Everywhere. 2016. Jahrgang. Association for Computing Machinery (ACM), April 2016, S. 1–14, doi:10.1145/2913029 (englisch, ubiquity.acm.org (Memento des Originals vom 10. Juli 2016 im Internet Archive) [abgerufen am 10. Juli 2016]): “JG: The word unum is short for universal number, the same way the word bit is short for binary digit.
  2. a b c John L. Gustafson: A Radical Approach to Computation with Real Numbers. In: Supercomputing Frontiers and Innovations. doi:10.14529/jsfi160203 (englisch, superfri.org [PDF; 2,4 MB; abgerufen am 6. Januar 2020]).
  3. a b c d John L. Gustafson, Isaac Yonemoto: Beating Floating Point at its Own Game: Posit Arithmetic. (PDF) 12. Juni 2017, abgerufen am 28. Dezember 2019 (englisch).
  4. John L. Gustafson: Posit Arithmetic. (PDF; 918 KB) 26. März 2019, S. 13, abgerufen am 16. März 2021 (englisch).
  5. Rechnung bei WolframAlpha