Jump to content
Sign in to follow this  
fredericopissarra

Convertendo uma "string" para ponto-flutuante, manualmente...

Recommended Posts

Artigo recente do #BitIsMyth: https://is.gd/kRROpi

---------------%<------- corte aqui --------------%<-------------------------------
Não vou mostrar código aqui porque seria um bem grande e com alguns macetes e testes de condições especiais (como NaNs, overflows, underflows). Para dar uma olhada no código atual da glibc, obtenha o código-fonte (no Debian/Ubuntu: apt source libc6) e veja o arquivo stdlib/strtod_l.c.

O problema em questão aqui é como transformar uma string contendo um valor decimal que tenha componente fracionário para ponto flutuante. Para tanto, usarei o tipo float como base (porque tem menos bits significativos – me permitirá escrever menos!). Considere o valor de PI com algumas “casas decimais” de “precisão”: 3.14159

Converter a parte inteira é trivial: Basta realizar múltiplas divisões por 2 e os restos nos darão os bits à partir do MSB. Neste caso, 3 é 0b11. Mas, e quanto a parte fracionária? O motivo que dividirmos por 2 o valor inteiro até obtermos zero como quociente é que cada posição do componente inteiro é um múltiplo de 2, em binário. Ou seja, 3 é 1\cdot2^1+1\cdot2^0. No caso da parte fracionária, os fatores multiplicadores dos bits são da ordem de 2^{-n}. O expoente negativo indica que o valor de cada bit deverá ser dividido pela potência de dois. A operação inversa, então, é multiplicar o valor decimal fracionário por 2 e obter o valor inteiro que, necessariamente, será 0 ou 1. No caso, 0.14159\cdot2=0.28318. Obtivemos 0, na parte inteira, e 0.28318 na parte fracionária… Esse 0, inteiro, é o MSB da parte fracionária… No segundo passo, multiplicamos apenas a parte fracionária resultante (0.28318) por 2. A parte inteira do resultado é o próximo bit e repetimos tudo para os próximos bits (eis todos os cálculos para 25 bits):

0.14159 * 2 = 0.28318 (MSB fracionario = 0)
0.28318 * 2 = 0.56636 (0)
0.56636 * 2 = 1.13272 (1)
0.13272 * 2 = 0.26544 (0)
0.26544 * 2 = 0.53088 (0)
0.53088 * 2 = 1.06176 (1)
0.06176 * 2 = 0.12352 (0)
0.12352 * 2 = 0.24704 (0)
0.24704 * 2 = 0.49408 (0)
0.49408 * 2 = 0.98816 (0)
0.98816 * 2 = 1.97632 (1)
0.97632 * 2 = 1.95264 (1)
0.95264 * 2 = 1.90528 (1)
0.09528 * 2 = 1.81056 (1)
0.81056 * 2 = 1.62112 (1)
0.62112 * 2 = 1.24224 (1)
0.24224 * 2 = 0.48448 (0)
0.48448 * 2 = 0.96896 (0)
0.96896 * 2 = 1.93792 (1)
0.93792 * 2 = 1.87584 (1)
0.87584 * 2 = 1.75168 (1)
0.75168 * 2 = 1.50336 (1)
0.50336 * 2 = 1.00672 (1)
0.00672 * 2 = 0.01344 (0)
0.01344 * 2 = 0.02688 (0)
...

Assim o valor final de 3.14159 é, em binário, com 27 bits de precisão é 0b11.0010010000111111001111100.

Como estamos lidando com float e já temos 2 bits na parte inteira, precisamos fazer essas repetições apenas 23 vezes. Uma vez a mais para determinar se precisaremos arredondar o valor obtido. Se a precisão de um float é de 24 bits, é necessário obter 25 para usar esse bit extra para arredondamento.

Da sequência acima, obtemos o valor 0b11.00100100001111110011111. Agora, precisamos normalizar esse valor, deixando apenas 1 bit setado na parte inteira. Isso é feito deslocando o “ponto binário” 1 bit para a esquerda. O valor obtido é 0b1.10010010000111111001111_1. Como o bit inferior, além da precisão do float, ou seja, dos 23 bits da parte fracionária, é 1, arredonda-se o valor da “mantissa” (de 23 bits, em vermelho) para cima, acrescentando 1, obtendo: 0b1.10010010000111111010000.

Agora, note que, na equação que nos dá o valor contido na estrutura de um float:

\displaystyle v=\left(-1\right)^s\cdot\left(1+\frac{f}{2^{23}}\right)\cdot2^e

O valor inteiro f nada mais é do que a parte fracionária, binária, deslocada 23 bits para a esquerda, ignorando o valor inteiro normalizado, ou seja, f é 0b100_1001_0000_1111_1101_0000 (0x490fd0 ou 4788176). Agora temos f=4788176 e e=1:

\displaystyle v=\left(-1\right)^0\cdot\left(1+\frac{4788176}{8388608}\right)\cdot2^{1}=3.141590118408203125

Que é a representação mais próxima de 3.14159 que podemos conseguir com um float.

Neste ponto você deve estar pensando que é meio esquisito que uma rotina de conversão de string para ponto flutuante precise usar ponto flutuante. Isso é, mais ou menos, a história do ovo e da galinha (embora o “ovo” tenha surgido primeiro! A galinha evoluiu de outras espécies que botavam ovos!), mas a rotina geralmente usa aritmética de múltipla precisão e é até possível usar BCD (Binary Coded Decimal) para tanto… De novo, a rotina ____STR2F_INTERNAL() em strtod_l.c é bastante intrincada porque leva em contra aqueles underflows e overflows, mas também a notação xxx.xxx...E+/-eee, mas o princípio fundamental é esse ai em cima!

Share this post


Link to post
Share on other sites

Aconselho a ver o texto no link... existem figuras feitas com o LaTeX no texto que o forum não sabe como lidar...

Aconselho, também, aos admins do forum a instalarem algum plugin para conversão de latex amsmath equations para gráficos, ao estilo do Wordpress, por exemplo...

Uma maneira de ver as "fórmulas" é usar o link https://www.codecogs.com/latex/eqneditor.php, fazer um Copy and Paste do código LaTeX para o site e ver a fórmula... mas, é mais fácil ver lá no #BitIsMyth! 🙂

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...