Unum (Zahlenformat)
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.“
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
BearbeitenDas 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 .
Typ I
BearbeitenDie 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ß.
Typ II
BearbeitenDie 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.
SoRNs
BearbeitenDa 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
BearbeitenAuf 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
BearbeitenEin 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
BearbeitenFü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.
Typ III
BearbeitenDas 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
BearbeitenGegeben 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
BearbeitenAus 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
BearbeitenDa 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
BearbeitenAusgenommen 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 00…0, so repräsentiert es ; besteht es aus 10…0, 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 0…01 oder 1…10 oder, falls das Regime den kompletten Rest der Zahl einnimmt, 1…11 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
BearbeitenEin 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
BearbeitenAls 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.
- Sonderfälle 0 und : Liegen nicht vor.
- Bestimme .
- Vorzeichen 0: .
- Laufweite 0001: : Es führen 3 Nullen, somit , d. h, .
- Exponent 101: .
- Mantisse 11011101: mit .
Daraus ergibt sich
Der letzte Ausdruck ergibt .[5]
Tabelle mit Beispielwerten
BearbeitenFü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
BearbeitenFü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
BearbeitenIn 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
BearbeitenFü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 | n. a. | ||
bis | bis | ||||
bis | bis | ||||
bis | bis | ||||
bis | bis | ||||
bis | bis |
Weblinks
Bearbeiten- Umfassende Informationen zu Posits
- Interaktive Website, die die Darstellungen veranschaulicht.
- New Approach Could Sink Floating Point Computation (englisch)
Einzelnachweise
Bearbeiten- ↑ 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 ( des 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.”
- ↑ 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]).
- ↑ 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).
- ↑ John L. Gustafson: Posit Arithmetic. (PDF; 918 KB) 26. März 2019, S. 13, abgerufen am 16. März 2021 (englisch).
- ↑ Rechnung bei WolframAlpha