Perder precisión con cc

12

Quiero usar dcpara manejar algunos números de base 16 con puntos hexadecimales, pero me encuentro con problemas de precisión. Por ejemplo, a continuación estoy multiplicando F423F.FDpor 100, ambos hex. La respuesta esperada es F423FFD, en cambio, es F423FFA.E1cercana, pero no lo suficientemente precisa, incluso después del redondeo.

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

Leí que dcera una calculadora de precisión ilimitada, y este no es un gran número de ninguna manera. ¿Hay algo que estoy haciendo mal?

Gracias por sus respuestas Dados los problemas con dc, mordí la bala y escribí mi propio analizador de números reales en otras bases. Si alguien está interesado en el código, puedo publicarlo aquí.

Yimin Rong
fuente

Respuestas:

6

Tenga en cuenta que solo imprimir el número original muestra que se redondea:

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

Puede evitarlo agregando muchos ceros finales para mayor precisión:

$ dc <<<'16 d i o F423F.FD000000 100 * p'
F423FFD.0000000
meuh
fuente
Gracias. ¡Creo que terminará tomando más código para masajear los números dcy luego escribir un analizador directamente! (La entrada puede o no tener un decimal, y puede estar en otras bases, por lo que la cantidad de relleno varía.)
Yimin Rong
2
Marcaré esto como la respuesta aceptada. Las personas responsables del mantenimiento dcrespondieron: para manejar adecuadamente los dígitos fraccionales no decimales requeriría un modelo completamente diferente al modelo de escala decimal utilizado por dc y bc (según lo establecido por POSIX para bc, y por tradición histórica para ambos). , por lo que técnicamente podría repararse dc, pero eso probablemente se rompería bc, por lo que se clasifica como WONTFIX.
Yimin Rong
8

Expresado como decimal (usando dcpara convertir), esto corresponde a 999999.98 (redondeado hacia abajo) × 256, es decir 255999994.88, que es F423FFA.E1 en hexadecimal.

Entonces, la diferencia proviene del dccomportamiento de redondeo: en lugar de calcular 256 × (999999 + 253 ÷ 256), que daría 255999997, redondea 253 ÷ 256 hacia abajo y multiplica el resultado.

dces una calculadora de precisión arbitraria , lo que significa que puede calcular con la precisión que desee, pero debe decirle qué es eso. Por defecto, su precisión es 0, lo que significa que la división produce solo valores enteros, y la multiplicación usa el número de dígitos en la entrada. Para establecer la precisión, use k(y tenga en cuenta que la precisión siempre se expresa en dígitos decimales, independientemente de la raíz de entrada o salida):

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

(La precisión de 8 dígitos sería suficiente ya que eso es lo que necesita para representar 1 ÷ 256 en decimal).

Stephen Kitt
fuente
1
¿Sería un resultado completamente inesperado para una calculadora de "precisión arbitraria"?
Yimin Rong
3
Todavía pierde precisión cuando kse establece: 10 k 16 d i o F423F.FD pF423F.FA, por lo que tendría que escalar todos los números antes de usarlos dc. Básicamente equivale a analizarlos previamente de todos modos.
Yimin Rong
2
@Yimin sí, desafortunadamente dcescala su entrada usando solo el número de dígitos, lo que me parece un error (ya que el número de dígitos se calcula usando la raíz de entrada, pero se aplica al valor decimal).
Stephen Kitt
1
@dhag, eso es lo que POSIX especifica (para lo bcque dcse basa): "Los cálculos internos se realizarán como en decimal, independientemente de las bases de entrada y salida, al número especificado de dígitos decimales".
Stephen Kitt
1
Realmente es un problema de cómo se analiza una constante. Prueba 20 k 16 d i o 0.3 1 / p (que imprime .19999999999999999). Comprenda que la operación solo se divide 0.2por 1(que en teoría no debería cambiar el valor). Mientras 20 k 16 d i o 0.3000 1 / p(correctamente) imprime .30000000000000000. (Cont.)
NotAnUnixNazi
1

La cuestión

El problema es la forma en que dc (y bc) entienden las constantes numéricas.
Por ejemplo, el valor (en hexadecimal) 0.3(dividido entre 1) se transforma en un valor cercano a0.2

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

De hecho, la constante simple 0.3también cambia:

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

Parece que es de una manera extraña, pero no lo es (más tarde).
Agregar más ceros hace que la respuesta se acerque al valor correcto:

$ 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

El último valor es exacto y seguirá siendo exacto, independientemente de la cantidad de ceros añadidos.

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

El problema también está presente en bc:

$ 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

¿Un dígito por bit?

El hecho muy poco intuitivo para los números de coma flotante es que el número de dígitos requeridos (después del punto) es igual al número de bits binarios (también después del punto). Un número binario 0.101 es exactamente igual a 0.625 en decimal. El número binario 0.0001110001 es (exactamente) igual a 0.1103515625(diez dígitos decimales)

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

Además, para un número de coma flotante como 2 ^ (- 10), que en binario tiene solo un bit (conjunto):

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

Tiene el mismo número de dígitos binarios .0000000001(10) que los dígitos decimales .0009765625(10). Puede que ese no sea el caso en otras bases, pero la base 10 es la representación interna de los números en dc y bc y, por lo tanto, es la única base por la que realmente debemos preocuparnos.

La prueba de matemáticas está al final de esta respuesta.

escala bc

El número de dígitos después del punto podría contarse con la función incorporada scale()bc:

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

Como se muestra, 2 dígitos son insuficientes para representar la constante 0.FD.

Y, además, contar el número de caracteres utilizados después del punto es una forma muy incorrecta de informar (y usar) la escala del número. La escala de un número (en cualquier base) debe calcular el número de bits necesarios.

Dígitos binarios en un flotador hexagonal.

Como se sabe, cada dígito hexadecimal usa 4 bits. Por lo tanto, cada dígito hexadecimal después del punto decimal requiere 4 dígitos binarios, que debido al hecho (¿impar?) También requieren 4 dígitos decimales.

Por lo tanto, un número como 0.FDrequerirá 8 dígitos decimales para ser representado correctamente:

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

Agregar ceros

La matemática es sencilla (para números hexadecimales):

  • Cuente el número de dígitos hexadecimales ( h) después del punto.
  • Multiplica hpor 4.
  • Agrega h×4 - h = h × (4-1) = h × 3 = 3×hceros.

En el código de shell (para 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

Que se imprimirá (correctamente tanto en CC como en CC):

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

Internamente, bc (o dc) podría hacer que el número de dígitos requeridos coincida con el número calculado anteriormente ( 3*h) para convertir los flotantes hexadecimales en la representación decimal interna. O alguna otra función para otras bases (suponiendo que el número de dígitos es finito en relación con la base 10 (interna de bc y dc) en dicha otra base). Como 2 i (2,4,8,16, ...) y 5,10.

posix

La especificación posix establece que (para bc, en qué dc se basa):

Los cálculos internos se realizarán como en decimal, independientemente de las bases de entrada y salida, al número especificado de dígitos decimales.

Pero "... el número especificado de dígitos decimales". podría entenderse como "... el número necesario de dígitos decimales para representar la constante numérica" ​​(como se describió anteriormente) sin afectar los "cálculos internos decimales"

Porque:

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

bc no está usando realmente 50 ("el número especificado de dígitos decimales") como se estableció anteriormente.

Solo si se divide, se convierte (aún de forma incorrecta, ya que utiliza una escala de 2 para leer la constante 0.FDantes de expandirla a 50 dígitos):

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

Sin embargo, esto es exacto:

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

Nuevamente, la lectura de cadenas numéricas (constantes) debe usar el número correcto de bits.


Prueba de matemáticas

En dos pasos:

Una fracción binaria se puede escribir como a / 2 n

Una fracción binaria es una suma finita de potencias negativas de dos.

Por ejemplo:

= 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 = (sin ceros)

En una fracción binaria de n bits, el último bit tiene un valor de 2 -n , o 1/2 n . En este ejemplo: 2-11 o 1/2 11 .

= 1/2 3 + 1/2 4 + 1/2 6 + 1/2 8 + 1/2 9 + 1/2 11 = (con inverso)

En general, el denominador podría convertirse en 2 n con un numerador positivo exponente de dos. Todos los términos se pueden combinar en un solo valor a / 2 n . Para este ejemplo:

= 2 8 /2 11 + 2 7 /2 11 + 2 5 /2 11 + 2 3 /2 11 + 2 2 /2 11 + 1/2 11 = (expresado con 2 11 )

= (2 8 + 2 7 + 2 5 + 2 3 + 2 2 + 1) / 2 11 = (extracción de factor común)

= (256 + 128 + 32 + 8 + 4 + 1) / 2 11 = (convertido a valor)

= 429/2 11

Cada fracción binaria se puede expresar como b / 10 n

Multiplique a / 2 n por 5 n / 5 n , obteniendo (a × 5 n ) / (2 n × 5 n ) = (a × 5 n ) / 10 n = b / 10 n , donde b = a × 5 n . Tiene n dígitos.

Por ejemplo, tenemos:

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

Se ha demostrado que cada fracción binaria es una fracción decimal con el mismo número de dígitos.

NotAnUnixNazi
fuente