Perdendo a precisão com CC

12

Eu quero usar dcpara lidar com alguns números de base 16 com pontos hexadecimais, mas estou tendo problemas de precisão. Por exemplo, abaixo estou multiplicando F423F.FDpor 100, ambos hexadecimais. A resposta esperada é F423FFD, em vez disso, está dando F423FFA.E1, próxima, mas não é precisa o suficiente, mesmo após o arredondamento.

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

Eu li que dcera uma calculadora de precisão ilimitada, e este não é um número grande de forma alguma. Existe algo que estou fazendo errado?

Obrigado por suas respostas. Dado os problemas com dc, mordi a bala e escrevi meu próprio analisador para números reais em outras bases. Se alguém estiver interessado no código, posso publicá-lo aqui.

Yimin Rong
fonte

Respostas:

6

Observe que apenas imprimir o número original mostra que ele é arredondado:

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

Você pode contornar isso adicionando muitos zeros à direita para obter mais precisão:

$ dc <<<'16 d i o F423F.FD000000 100 * p'
F423FFD.0000000
meuh
fonte
Obrigado. Eu acho que vai acabar pegando mais código para massagear os números dce depois escrever apenas um analisador diretamente! (Entrada pode ou não ter um número decimal, e pode ser em outras bases, de modo que a quantidade de enchimento varia.)
Yimin Rong
2
Vou marcar isso como a resposta aceita. As pessoas responsáveis ​​por manter dcresponderam: Para lidar adequadamente com dígitos fracionários não-decimais, seria necessário um modelo completamente diferente do modelo em escala decimal usado por dc e bc (conforme ditado pelo POSIX para bc e pela tradição histórica para ambos). , então tecnicamente poderia ser corrigido dc, mas isso provavelmente seria interrompido bc, classificado como WONTFIX.
Yimin Rong
8

Expressado como decimal (usando dcpara converter), isso corresponde a 999999,98 (arredondado para baixo) × 256, ou seja , 255999994,88, que é F423FFA.E1 em hexadecimal.

Portanto, a diferença vem do dccomportamento de arredondamento: em vez de calcular 256 × (999999 + 253 × 256), o que daria 255999997, ele arredonda 253 × 256 e multiplica o resultado.

dcé uma calculadora de precisão arbitrária , o que significa que pode calcular com a precisão desejada, mas é preciso dizer o que é isso. Por padrão, sua precisão é 0, o que significa que a divisão produz apenas valores inteiros e a multiplicação usa o número de dígitos na entrada. Para definir a precisão, use k(e lembre-se de que a precisão é sempre expressa em dígitos decimais, independentemente da raiz de entrada ou saída):

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

(A precisão de 8 dígitos seria suficiente, pois é isso que você precisa para representar 1 ÷ 256 em decimal.)

Stephen Kitt
fonte
1
Isso parece ser um resultado completamente inesperado para uma calculadora de "precisão arbitrária"?
Yimin Rong
3
Ele ainda perde precisão quando kestá definido: 10 k 16 d i o F423F.FD pF423F.FA, então eu teria que escalar todos os números antes de usá-los dc. Basicamente, é uma pré-análise de qualquer maneira.
Yimin Rong
2
@Yimin sim, infelizmente dcdimensiona sua entrada usando apenas o número de dígitos, o que parece um erro para mim (já que o número de dígitos é calculado usando a raiz da entrada, mas aplicado ao valor decimal).
Stephen Kitt
1
@dhag é o que o POSIX especifica (para bc, com dcbase em): “Os cálculos internos devem ser conduzidos como se fossem decimais, independentemente das bases de entrada e saída, para o número especificado de dígitos decimais.”
Stephen Kitt
1
É realmente um problema de como uma constante está sendo analisada. Tente 20 k 16 d i o 0.3 1 / p (que imprime .19999999999999999). Entenda que a operação está apenas dividindo 0.2por 1(que, em teoria, não deve alterar o valor). Enquanto 20 k 16 d i o 0.3000 1 / p(corretamente) imprime .30000000000000000. (Cont.)
Isaac
1

O problema

O problema é a maneira pela qual dc (e bc) entende constantes numéricas.
Por exemplo, o valor (em hexadecimal) 0.3(dividido por 1) é transformado em um valor próximo a0.2

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

De fato, a constante simples 0.3também é alterada:

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

Parece que é de uma maneira estranha, mas não é (mais tarde).
Adicionar mais zeros faz com que a resposta se aproxime do valor correto:

$ 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

O último valor é exato e permanecerá exato, não importa como mais zeros sejam adicionados.

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

O problema também está presente no 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

Um dígito por bit?

O fato não intuitivo dos números de ponto flutuante é que o número de dígitos necessários (após o ponto) é igual ao número de bits binários (também após o ponto). Um número binário 0,101 é exatamente igual a 0,625 em decimal. O número binário 0.0001110001 é (exatamente) igual a 0.1103515625(dez dígitos decimais)

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

Além disso, para um número de ponto flutuante como 2 ^ (- 10), que em binário possui apenas um bit (definido):

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

Tem o mesmo número de dígitos binários .0000000001(10) que dígitos decimais.0009765625 (10). Pode não ser o caso em outras bases, mas a base 10 é a representação interna dos números em dc e bc e, portanto, é a única base com a qual realmente precisamos nos preocupar.

A prova de matemática está no final desta resposta.

escala bc

O número de dígitos após o ponto pode ser contado com o scale()formulário de função interno bc:

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

Como mostrado, 2 dígitos são insuficientes para representar a constante 0.FD.

Além disso, apenas contar o número de caracteres usados ​​após o ponto é uma maneira muito incorreta de relatar (e usar) a escala do número. A escala de um número (em qualquer base) deve calcular o número de bits necessários.

Dígitos binários em um flutuador hexadecimal.

Como é sabido, cada dígito hexadecimal usa 4 bits. Portanto, cada dígito hexadecimal após o ponto decimal requer 4 dígitos binários, os quais, devido ao fato (ímpar?) Acima, também exigem 4 dígitos decimais.

Portanto, um número como 0.FDexigirá que 8 dígitos decimais sejam representados corretamente:

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

Adicionar zeros

A matemática é simples (para números hexadecimais):

  • Conte o número de dígitos hexadecimais ( h) após o ponto.
  • Multiplique hpor 4.
  • Adicione h×4 - h = h × (4-1) = h × 3 = 3×hzeros.

No código do 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

Qual será impresso (corretamente em dc e bc):

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

Internamente, bc (ou dc) pode fazer com que o número de dígitos necessários corresponda ao número calculado acima ( 3*h) para converter flutuadores hexadecimais na representação decimal interna. Ou alguma outra função para outras bases (assumindo que o número de dígitos é finito em relação à base 10 (interna de bc e dc) nessa outra base). Like 2 i (2,4,8,16, ...) e 5,10.

posix

A especificação posix afirma que (para bc, em que dc se baseia):

Os cálculos internos devem ser conduzidos como se fossem decimais, independentemente das bases de entrada e saída, para o número especificado de dígitos decimais.

Mas "... o número especificado de dígitos decimais". pode ser entendido como "… o número necessário de dígitos decimais para representar a constante numérica" ​​(como descrito acima) sem afetar os "cálculos internos decimais"

Porque:

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

bc não está realmente usando 50 ("o número especificado de dígitos decimais") como definido acima.

Somente se dividido, ele é convertido (ainda incorretamente, pois usa uma escala de 2 para ler a constante 0.FDantes de expandi-la para 50 dígitos):

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

No entanto, isso é exato:

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

Novamente, a leitura de seqüências numéricas (constantes) deve usar o número correto de bits.


Prova de matemática

Em duas etapas:

Uma fração binária pode ser escrita como a / 2 n

Uma fração binária é uma soma finita de potências negativas de dois.

Por exemplo:

= 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 = (com zeros removidos)

Em uma fração binária de n bits, o último bit tem um valor de 2- n ou 1/2 n . Neste exemplo: 2 -11 ou 1/2 11 .

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

Em geral, o denominador pode se tornar 2 n com um expoente numerador positivo de dois. Todos os termos podem ser combinados em um único valor a / 2 n . Para este exemplo:

2 = 8 /2 11 + 2 7 /2 11 + 2 5 /2 11 + 2 3 /2 11 + 2 2 /2 11 + 1/2 11 = (expresso com 2 11 )

= (2 8 + 2 7 + 2 5 + 2 3 + 2 2 + 1) / 2 11 = (extração do fator comum)

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

= 429/2 11

Cada fração binária pode ser expressa como b / 10 n

Multiplique a / 2 n por 5 n / 5 n , obtendo (a × 5 n ) / (2 n × 5 n ) = (a × 5 n ) / 10 n = b / 10 n , em que b = a × 5 n . Tem n dígitos.

Por exemplo, temos:

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

Foi demonstrado que toda fração binária é uma fração decimal com o mesmo número de dígitos.

Isaac
fonte