Continuando a investigar o problema da precisão decimal usando aritmética binária, iniciada em postagens anteriores [1,2,3,4], pude desenvolver algoritmos para calcular números reais apresentados no formato de números decimais de ponto flutuante, que dão o mesmo resultado exato como se cálculos seriam feitos manualmente.
Esses algoritmos usam aritmética binária, regulada pelo padrão IEEE754. Para testar a operação dos algoritmos, foi desenvolvido um programa de teste em C ++ que implementa uma calculadora decimal de 18 bits.
Como o volume do material excede o formato do post, expus os principais pontos na forma de resumos. Vamos chamar este post de Teses de Maio :(.
Então
Sabe-se que
Aritmética familiar ao usuário é aritmética decimal.
Também existem aritmética b-ária, onde b é a base do sistema numérico, assumindo qualquer valor diferente de zero [5].
Para exibir números em diferentes escalas, usamos a notação de números de ponto flutuante na forma do produto da mantissa e algum grau arbitrário de base. Essa é a chamada notação exponencial.
Se o grau do número for fixo e a mantissa do número for um número inteiro, esse formato será chamado de formato de ponto fixo. Um caso especial do formato de ponto fixo é um número em que o grau é zero. Este formato é um formato inteiro.
Se a mantissa é um número fracionário no sistema de números b-ário com a parte inteira c ≠ 0 ec c, então esse número é chamado normalizado.
Apesar do fato de que, por sua natureza física, os números são aproximados, para um dispositivo de computação esses são números exatos e o dispositivo deve executar operações neles com uma precisão especificada pelo usuário.
Cálculos precisos em média aritmética, obtendo um resultado com um determinado número de dígitos significativos válidos após o ponto [6].
Todos os cálculos no computador são realizados em formato binário. Para eles, a base é b = 2.
Como os sistemas de números binários e decimais são incomensuráveis, ao converter números reais decimais em código binário, na maioria das vezes obtemos o valor aproximado do equivalente binário do número decimal. Portanto, ao converter números decimais em binários, ocorrem erros de representação.
Os números decimais que têm o equivalente binário exato são chamados representáveis.
Os números decimais que não possuem o equivalente binário exato são chamados de não representativos.
Todos os números decimais inteiros são representáveis se o número de dígitos significativos em seus equivalentes binários não exceder a grade de bits da área de palavras-máquina na qual estão escritos.
Quanto mais dígitos binários for representado o equivalente binário do número, menor será o erro de apresentação. Isso explica o desejo de aumentar constantemente a capacidade do registro operacional do processador.
Qualquer número decimal cujo equivalente binário contenha o número de dígitos significativos que excedem a grade de bits de uma palavra de máquina só pode ser representado aproximadamente.
As operações aritméticas, que resultam em um excesso da profundidade de bits da palavra mantissa da máquina, retornam um número aproximado.
Os números aproximados podem conter números verdadeiros, duvidosos e incorretos.
Números incorretos nos cálculos afetam a precisão e às vezes podem levar a resultados completamente incorretos [3].
De acordo com a teoria dos cálculos aproximados, para obter resultados corretos, números aproximados são arredondados para excluir números incorretos [6].
A precisão que o usuário deseja, ou pode obter nos cálculos, é determinada pelo número de dígitos válidos que o algoritmo computacional fornece.
Qualquer número binário pode ser arredondado para o número especificado de dígitos binários, descartando bits extras.
Da mesma forma, qualquer número decimal pode ser arredondado para o número necessário de dígitos decimais, descartando dígitos extras.
Você não pode simplesmente descartar dígitos binários extras em um número binário para arredondar seu equivalente decimal para um número determinado de dígitos decimais, pois diminuir a profundidade de bits do equivalente binário de um número decimal aumentará o número de dígitos inválidos em seu equivalente decimal.
Qualquer número real expresso na forma de uma fração decimal pode ser representado com precisão no formato de um número de ponto flutuante (TFT), no qual a mantissa é um número inteiro. O expositor no NTC indicará a posição do ponto nesse número.
Se o número for apresentado no formato de um NTC com uma mantissa inteira, a mantissa e o expoente desse número poderão ser convertidos com precisão em código binário.
Novo
Um formato no qual a mantissa TNT decimal é representada pelo equivalente binário da mantissa número inteiro decimal, e o expoente é o equivalente binário da potência de 10 (base b = 10), será chamado formato binário decimal misto (SDDF).
A diferença entre o SDDF e o formato NTP binário é que o expoente no SDDF é igual ao grau base b = 10, enquanto o expoente do formato NDT binário é igual ao grau base binário b = 2. Assim, para SDDF, o número será apresentado como
e para o CNC, na norma IEEE754, como
.
A diferença entre o SDDF e o formato TFT decimal binário (DDF ou BCD) é que, no DDF, a mantissa e o expoente são números decimais inteiros nos quais cada dígito é escrito como um byte ou tetrad, enquanto todos os números decimais são expressos em SDDF seus equivalentes binários inteiros.
Assim, qualquer número real decimal pode ser representado no SDDF com um código binário de até N dígitos decimais significativos.
Todas as operações aritméticas nos CTDs decimais no SDDF são realizadas de acordo com as regras da aritmética comum, onde todos os argumentos são números inteiros.
Antes de cada operação aritmética, o número decimal é representado no formato SDDF: [S, M, z, e]. Onde está o código S do sinal do número (0 ou 1). M é o equivalente inteiro binário da mantissa de um número com o número de dígitos decimais N. Onde N é a precisão dos cálculos. z é o sinal do expoente, e é o valor do expoente. Essa representação é uma representação decimal normalizada.
Por exemplo, para cálculos com precisão de N = 7 dígitos significativos, o número 123.456 deve ser representado como 1234560 * 10 ^ -4.
A mantissa decimal mínima para N = 7 será M = 1.000.000.
A mantissa decimal máxima para N = 7 será M = 9999999.
O equivalente binário do número máximo de 7 bits 9999999 será 100 110 001 001 011 001 111 111. Ele contém 24 dígitos binários. Portanto, é necessário um registro binário de 24 bits para representar mantissas decimais no intervalo de 1.000.000 a 9999999.
Se em uma palavra de máquina binária de 32 bits, na qual 24 dígitos são atribuídos à mantissa, um dígito é atribuído ao sinal do número S, um dígito ao sinal do expoente z e 6 dígitos ao expoente, números reais decimais podem ser representados nesse SDF preciso para N = 7 números decimais significativos. Os valores absolutos desses números variam de 1.000.000 * 10 ^ -64 a 9999999 * 10 ^ 64.
Após cada operação aritmética, a mantissa decimal do número deve ser normalizada e arredondada para o número inteiro mais próximo. Para fazer isso, o equivalente binário resultante da mantissa do número, se necessário, deve ser multiplicado ou dividido pelo equivalente binário de 10 a tal ponto que o número de dígitos do equivalente decimal da mantissa se torne igual a N. O número resultante deve ser arredondado para o número inteiro mais próximo.
Um exemploEncontre, até N = 7, o resultado da expressão (9675,423 * 10 ^ 2-9,675421 * 10 ^ 5) * 10 ^ 6 - 199992
Calculada manualmente ou em uma calculadora do Windows, essa expressão será igual ao número 8.000000
Escrevemos os operandos na forma normalizada:
A=9,675423*10^5= 9675423*10^-1
B= 9675,421*10^2 = 9675421*10^-1
C=1000000 = 1000000*10^0
D = 1999920*10^-1No SDDF, esses operandos serão representados como:
A=[0, 9675423,1, 1]
B=[0,9675421,1, 1]
C=[0, 1000000,0, 0]
D=[0, 1999920,1, 1]Encontre a diferença S = AB. Como os expoentes dos operandos A e B são os mesmos, encontramos a mantissa de sua diferença:
9675423-9675421=2Para normalizar a mantissa S, devemos multiplicá-la por 10 ^ 6, enquanto o expoente deve ser reduzido por 6. Então S = 2 * 1.000.000 = 2.000.000 * 10 ^ -7
Calculamos o produto P = D * C. Para fazer isso, multiplique a mantissa dos fatores e adicione os exponenciais:
M = 2.000.000 * 10 ^ -7 * 1.000.000 * 10 * 0 = 2.000.000.000.000 * 10 ^ -7
Após normalizar a mantissa, obtemos P = 2.000.000 * 10 ^ -1.
O resultado do cálculo R será igual a:
R = PD = 2.000.000 * 10 ^ -1-1999920 * 10 ^ -1 = 80 * 10 ^ -1
Após a normalização, obtemos R = 8000000 * 10 ^ -6.
Para comparação, o cálculo dessa expressão no Excel fornece o resultado R = 8,0000698E + 00.
O autor desenvolveu um algoritmo de calculadora no SDDF que executa a adição, subtração, multiplicação e divisão de números decimais com até 18 dígitos significativos. Para confirmar a correção do algoritmo, um programa C ++ foi gravado. Como o autor não é um programador profissional, o programa desenvolvido destina-se apenas ao estudo do algoritmo de cálculo.
Abaixo, por exemplo, há uma captura de tela demonstrando o cálculo da seguinte expressão:
1,23456789098765432*10^8 * 9,87654321234567891*10^(-9) - 1,2193263123914037*10^0≈ 3.0*10^(-17)
Para testar o desempenho, a operação de multiplicação de dois números de 18 bits foi iniciada em um ciclo. O programa foi executado em um computador Intel® Core (TM) i3-4330 CPU@3.50GHz 3.50 GHz. RAM 8,0 GB. Tipo de sistema: 64 bits A velocidade foi igual a 2,4 * 10 ^ 6 multiplicações por segundo.
Não posso comparar com a velocidade das calculadoras Windows e Excel até agora, não há educação suficiente :(. Quanto à precisão dos cálculos, é o mesmo que se os cálculos fossem feitos manualmente.
Referências:
- Vista lateral: padrão IEEE754
- A normalização de flutuação é necessária?
- Erros aritméticos binários fatais ao trabalhar com números de ponto flutuante
- Novamente sobre números de ponto flutuante
- Sistemas numéricos
- Regras básicas para cálculos aproximados