Präzision verlieren mit Gleichstrom

12

Ich möchte verwenden dc, um einige Basis-16-Zahlen mit Hexadezimalpunkten zu behandeln, aber ich stoße auf Präzisionsprobleme. Zum Beispiel multipliziere ich unten F423F.FDmit 100, beide hex. Die erwartete Antwort ist F423FFD, stattdessen F423FFA.E1, nahe beieinander, aber auch nach dem Runden nicht genau genug.

$ dc
16 d i o F423F.FD 100 * p
F423FFA.E1

Ich habe gelesen, dass dies dcein uneingeschränkter Präzisionsrechner war, und das ist keineswegs eine große Zahl. Gibt es etwas, was ich falsch mache?

Vielen Dank für Ihre Antworten. Angesichts der Probleme mit habe dcich die Kugel gebissen und meinen eigenen Parser für reelle Zahlen in anderen Basen geschrieben. Wenn sich jemand für den Code interessiert, kann ich ihn hier posten.

Yimin Rong
quelle

Antworten:

6

Beachten Sie, dass nur das Ausdrucken der Originalnummer zeigt, dass sie gerundet ist:

$ dc <<<'16 d i o F423F.FD p'
F423F.FA

Sie können dies umgehen, indem Sie viele nachgestellte Nullen hinzufügen, um die Genauigkeit zu erhöhen:

$ dc <<<'16 d i o F423F.FD000000 100 * p'
F423FFD.0000000
meuh
quelle
Vielen Dank. Ich denke, dass es am Ende mehr Code braucht, um die Zahlen zu massieren dc, um sie dann zu verwenden, um einfach einen Parser direkt zu schreiben! (Die Eingabe kann dezimal sein oder auch nicht und kann in anderen Basen erfolgen, daher variiert der Abstand.)
Yimin Rong
2
Ich werde dies als akzeptierte Antwort markieren. Die Verantwortlichen für die Aufrechterhaltung der dcAntworten: Um nicht-dezimale Nachkommastellen richtig zu behandeln, wäre ein völlig anderes Modell erforderlich als das von dc und bc verwendete Dezimalskalenmodell (gemäß POSIX für bc und nach historischer Tradition für beide). , so technisch könnte es behoben werden dc, aber das würde wahrscheinlich brechen bc, also als WONTFIX eingestuft.
Yimin Rong
8

Ausgedrückt als Dezimalzahl ( dczum Konvertieren verwenden) entspricht dies 999999,98 (abgerundet) × 256, dh 255999994,88, was hexadezimal F423FFA.E1 ist.

Der Unterschied ergibt sich also aus dcdem Rundungsverhalten: Anstatt 256 × (999999 + 253 ÷ 256) zu berechnen, was 255999997 ergibt, rundet es 253 ÷ 256 ab und multipliziert das Ergebnis.

dcist ein Taschenrechner mit willkürlicher Genauigkeit, dh er kann mit jeder gewünschten Genauigkeit rechnen, aber Sie müssen ihm mitteilen, was das ist. Standardmäßig ist die Genauigkeit 0, was bedeutet, dass die Division nur ganzzahlige Werte erzeugt und die Multiplikation die Anzahl der Stellen in der Eingabe verwendet. Verwenden Sie zum Festlegen der Genauigkeit k(und beachten Sie, dass die Genauigkeit unabhängig vom Eingabe- oder Ausgaberadix immer in Dezimalstellen ausgedrückt wird):

10 k
16 d i o
F423FFD 100 / p
F423F.FD0000000
100 * p
F423FFD.000000000

(Die Genauigkeit von 8 Stellen ist ausreichend, da Sie hier eine Dezimalzahl von 1 ÷ 256 angeben müssen.)

Stephen Kitt
quelle
1
Das scheint ein völlig unerwartetes Ergebnis für einen Taschenrechner mit "willkürlicher Genauigkeit" zu sein?
Yimin Rong
3
Es verliert immer noch an Präzision, wenn keingestellt ist: 10 k 16 d i o F423F.FD pF423F.FA, daher müsste ich alle Zahlen skalieren, bevor ich sie einsetze dc. Im Grunde genommen bedeutet das, sie vorab zu analysieren.
Yimin Rong
2
@Yimin ja, dcskaliert leider seine Eingabe nur mit der Anzahl der Stellen, was mir wie ein Fehler erscheint (da die Anzahl der Stellen mit dem Eingaberadix berechnet wird, aber auf den Dezimalwert angewendet wird).
Stephen Kitt
1
@dhag ist das, was POSIX angibt (für bc, das darauf dcbasiert): „Interne Berechnungen werden unabhängig von der Eingabe- und Ausgabebasis wie in Dezimalzahlen mit der angegebenen Anzahl von Dezimalstellen ausgeführt.“
Stephen Kitt
1
Es ist wirklich ein Problem, wie eine Konstante analysiert wird. Versuchen Sie es 20 k 16 d i o 0.3 1 / p (druckt .19999999999999999). Verstehen Sie, dass die Operation nur durch dividiert 0.2wird 1(was theoretisch den Wert nicht ändern sollte). Während 20 k 16 d i o 0.3000 1 / p(richtig) gedruckt wird .30000000000000000. (Fortsetzung)
Isaac
1

Die Angelegenheit

Das Problem ist die Art und Weise, wie DC (und BC) numerische Konstanten verstehen.
Zum Beispiel wird der Wert (in hex) 0.3(geteilt durch 1) in einen Wert in der Nähe von umgewandelt0.2

$ dc <<<"20k 16 d i o 0.3 1 / p"
.199999999999999999999999999

Tatsächlich wird auch die einfache Konstante 0.3geändert:

$ dc <<<"20 k 16 d i o     0.3     p"
.1

Es scheint, dass es auf seltsame Weise ist, aber es ist nicht (mehr später).
Wenn Sie weitere Nullen hinzufügen, nähert sich die Antwort dem richtigen Wert:

$ dc <<<"20 k 16 d i o     0.30     p"
.2E

$ dc <<<"20 k 16 d i o     0.300     p"
.2FD

$ dc <<<"20 k 16 d i o     0.3000     p"
.3000

Der letzte Wert ist genau und bleibt genau, egal wie viele Nullen hinzugefügt werden.

$ dc <<<"20 k 16 d i o     0.30000000     p"
.3000000

Das Problem ist auch in bc vorhanden:

$ bc <<< "scale=20; obase=16; ibase=16;    0.3 / 1"
.19999999999999999

$ bc <<< "scale=20; obase=16; ibase=16;    0.30 / 1"
.2E147AE147AE147AE

$ bc <<< "scale=20; obase=16; ibase=16;    0.300 / 1"
.2FDF3B645A1CAC083

$ bc <<< "scale=20; obase=16; ibase=16;    0.3000 / 1"
.30000000000000000

Eine Ziffer pro Bit?

Die sehr wenig intuitive Tatsache bei Gleitkommazahlen ist, dass die Anzahl der erforderlichen Ziffern (nach dem Punkt) der Anzahl der Binärbits (auch nach dem Punkt) entspricht. Eine Binärzahl von 0,101 entspricht genau 0,625 in Dezimalzahl. Die Binärzahl 0.0001110001 ist (genau) gleich 0.1103515625(zehn Dezimalstellen)

$ bc <<<'scale=30;obase=10;ibase=2; 0.101/1; 0.0001110001/1'; echo ".1234567890"
.625000000000000000000000000000
.110351562500000000000000000000
.1234567890

Auch für eine Gleitkommazahl wie 2 ^ (- 10), die in der Binärdatei nur ein (gesetztes) Bit hat:

$ bc <<<"scale=20; a=2^-10; obase=2;a; obase=10; a"
.0000000001000000000000000000000000000000000000000000000000000000000
.00097656250000000000

Hat die gleiche Anzahl von Binärziffern .0000000001(10) wie Dezimalziffern .0009765625(10). Das mag in anderen Basen nicht der Fall sein, aber Basis 10 ist die interne Darstellung von Zahlen in dc und bc und daher die einzige Basis, um die wir uns wirklich kümmern müssen.

Der mathematische Beweis ist am Ende dieser Antwort.

bc Skala

Die Anzahl der Stellen nach dem Punkt konnte mit der eingebauten Funktionsform scale()bc gezählt werden:

$ bc <<<'obase=16;ibase=16; a=0.FD; scale(a); a; a*100'
2
.FA
FA.E1

Wie gezeigt, reichen 2 Ziffern nicht aus, um die Konstante darzustellen 0.FD.

Das Zählen der nach dem Punkt verwendeten Zeichen ist eine sehr falsche Methode, um die Skala der Zahl zu melden (und zu verwenden). Die Skala einer Zahl (in einer beliebigen Basis) sollte die Anzahl der benötigten Bits berechnen.

Binärziffern in einem Hex-Float.

Es ist bekannt, dass jede hexadezimale Ziffer 4 Bits verwendet. Daher benötigt jede Hexadezimalziffer nach dem Dezimalpunkt 4 Binärziffern, die aufgrund der obigen (ungeraden?) Tatsache auch 4 Dezimalziffern erfordern.

Daher 0.FDerfordert eine Zahl wie 8 Dezimalstellen, um korrekt dargestellt zu werden:

$ bc <<<'obase=10;ibase=16;a=0.FD000000; scale(a);a;a*100'
8
.98828125
253.00000000

Fügen Sie Nullen hinzu

Die Mathematik ist einfach (für Hex-Zahlen):

  • Zählen Sie die Anzahl der Hexadezimalstellen ( h) nach dem Punkt.
  • Mit h4 multiplizieren .
  • Fügen Sie h×4 - h = h × (4-1) = h × 3 = 3×hNullen hinzu.

Im Shell-Code (für sh):

a=F423F.FD
h=${a##*.}
h=${#h}
a=$a$(printf '%0*d' $((3*h)) 0)
echo "$a"

echo "obase=16;ibase=16;$a*100" | bc

echo "20 k 16 d i o $a 100 * p" | dc

Welches wird gedruckt (richtig sowohl in dc und bc):

$  sh ./script
F423F.FD000000
F423FFD.0000000
F423FFD.0000000

Intern könnte bc (oder dc) bewirken, dass die Anzahl der erforderlichen Stellen mit der oben berechneten Anzahl ( 3*h) übereinstimmt , um hexadezimale Gleitkommazahlen in die interne Dezimaldarstellung umzuwandeln. Oder eine andere Funktion für andere Basen (unter der Annahme, dass die Anzahl der Stellen in Bezug auf die Basis 10 (innerhalb von bc und dc) in einer solchen anderen Basis endlich ist). Wie 2 i (2,4,8,16, ...) und 5,10.

posix

Die posix-Spezifikation besagt, dass (für bc, auf dem dc basiert):

Interne Berechnungen werden unabhängig von der Eingabe- und Ausgabebasis wie in Dezimalzahlen mit der angegebenen Anzahl von Dezimalstellen ausgeführt.

Aber "... die angegebene Anzahl von Dezimalstellen." könnte verstanden werden als "... die erforderliche Anzahl von Dezimalstellen, um die numerische Konstante darzustellen" (wie oben beschrieben), ohne die "internen Dezimalberechnungen" zu beeinflussen

Weil:

bc <<<'scale=50;obase=16;ibase=16; a=0.FD; a+1'
1.FA

bc verwendet nicht wirklich 50 ("die angegebene Anzahl von Dezimalstellen") wie oben eingestellt.

Nur wenn geteilt, wird es konvertiert (immer noch falsch, da es eine Skala von 2 verwendet, um die Konstante zu lesen, 0.FDbevor es auf 50 Stellen erweitert wird):

$ bc <<<'scale=50;obase=16;ibase=16; a=0.FD/1; a'
.FAE147AE147AE147AE147AE147AE147AE147AE147A

Dies ist jedoch genau:

$ bc <<<'scale=50;obase=16;ibase=16; a=0.FD000000/1; a'
.FD0000000000000000000000000000000000000000

Auch hier sollte beim Lesen von numerischen Zeichenfolgen (Konstanten) die richtige Anzahl von Bits verwendet werden.


Mathe Beweis

In zwei Schritten:

Ein binärer Bruch kann als / 2 n geschrieben werden

Ein binärer Bruch ist eine endliche Summe negativer Zweierpotenzen.

Beispielsweise:

= 0.00110101101 = 
= 0. 0     0      1     1      0      1     0      1      1     0       1

= 0 + 0 × 2 -1 + 0 × 2 -2 + 1 × 2 -3 + 1 × 2 -4 + 0 × 2 -5 + 1 × 2 -6 + 0 × 2 -7 + 1 × 2 -8 + 1 × 2 -9 + 0 × 2 -10 + 1 × 2 -11

= 2 -3 + 2 -4 + 2 -6 + 2 -8 + 2 -9 + 2 -11 = (ohne Nullen)

In einem binären Bruchteil von n Bits hat das letzte Bit einen Wert von 2- n oder 1/2 n . In diesem Beispiel: 2 -11 oder 1/2 11 .

= 1/2 3 + 1/2 4 + 1/2 6 + 1/2 8 + 1/2 9 + 1/2 11 = (mit Umkehrung)

Im Allgemeinen kann der Nenner mit einem positiven Zähler-Exponenten von zwei zu 2 n werden . Alle Terme können dann zu einem einzigen Wert a / 2 n kombiniert werden . Für dieses Beispiel:

2 = 8 /2 11 + 2 7 /2 11 + 2 5 /2 11 + 2 3 /2 11 + 2 2 /2 11 + 1/2 11 = (ausgedrückt mit 2 11 )

= (2 8 + 2 7 + 2 5 + 2 3 + 2 2 + 1) / 2 11 = (Extrahieren des gemeinsamen Faktors)

= (256 + 128 + 32 + 8 + 4 + 1) / 2 11 = (in Wert umgewandelt)

= 429/2 11

Jeder binäre Bruch kann als b / 10 n ausgedrückt werden

Multiplizieren Sie a / 2 n mit 5 n / 5 n und erhalten Sie (a × 5 n ) / (2 n × 5 n ) = (a × 5 n ) / 10 n = b / 10 n , wobei b = a × 5 n . Es hat n Ziffern.

Für das Beispiel haben wir:

( 429,5 11 ) / 10 11 = 20947265625/10 11 = 0,20947265625

Es wurde gezeigt, dass jeder binäre Bruch ein Dezimalbruch mit der gleichen Anzahl von Ziffern ist.

Isaac
quelle