Representação do ponto flutuante em binário

Na representação dos números ponto flutuante em binário, os dígitos binários do lado direito do ponto estão associados as potências negativas de 2.

Vamos representar o seguinte número na representação binária:

$(0.75)_10$ = $\frac{75}{100}$ = $\frac{3}{4}$ = $(0.11)_2$

Observe que os números fracionários escritos com denominador sendo uma potência de 2 podem ser facilmente representados na notação ponto flutuante binária:

$(0.625)_10$ = $\frac{625}{1000}$ = $\frac{5}{8}$ = $(0.101)_2$

Infelizmente, nem todos os números podem ser representados como uma fração com um denominador uma potência de 2. Por exemplo, $\frac{1}{3}$ não pode ser escrita como uma fração com denominador sendo uma potência de 2 mas podemos obter uma aproximação.

$\frac{1}{3}$ = $\frac{x}{2}$ $\rightarrow$ x = $\frac{2}{3}$

Vamos considerar a seguinte aproximação:

denominador 2

$\frac{1}{3} \approx $ $\frac{ \lfloor \frac{2}{3} \rfloor }{2}$ $\approx \frac{0}{2}$

$\frac{1}{3} \approx \frac{0}{2} \approx (0.0)_2$

denominador 4

$\frac{1}{3} \approx $ $\frac{ \lfloor \frac{4}{3} \rfloor }{4}$ $\approx \frac{1}{4}$

$\frac{1}{3} \approx \frac{1}{4} \approx (0.01)_2$

denominador 8

$\frac{1}{3} \approx $ $\frac{ \lfloor \frac{8}{3} \rfloor }{8}$ $\approx \frac{2}{8}$

$\frac{1}{3} \approx \frac{2}{8} \approx (0.010)_2$

denominador 16

$\frac{1}{3} \approx $ $\frac{ \lfloor \frac{16}{3} \rfloor }{16}$ $\approx \frac{5}{16}$

$\frac{1}{3} \approx \frac{5}{16} \approx (0.0101)_2$

denominador 32

$\frac{1}{3} \approx $ $\frac{ \lfloor \frac{32}{3} \rfloor }{32}$ $\approx \frac{10}{32}$

$\frac{1}{3} \approx \frac{10}{32} \approx (0.01010)_2$

denominador 64

$\frac{1}{3} \approx $ $\frac{ \lfloor \frac{64}{3} \rfloor }{64}$ $\approx \frac{21}{64}$

$\frac{1}{3} \approx \frac{21}{64} \approx (0.010101)_2$

1/3 $\approx$ 0.0

1/3 $\approx$ 0.010

1/3 $\approx$ 0.0101

1/3 $\approx$0.01010

1/3 $\approx$ 0.010101

1/3 $\approx$ 0.0101[01]....₂

Neste caso, o número $\frac{1}{3}$ precisam de representação de uma quantidade infinita de bits  para serem representados fielmente.

A maior parte das linguagens adota o padrão IEEE 754 criado em 1985 como padrão para a representação e aritmética de ponto flutuante. Resumidamente, o float é representado da seguinte maneira:

O bit mais significativo s representa o sinal, o campo exp codifica o expoente e o campo frac codifica a parte fracionário do número float.

O campo bit utiliza 1 bit, O campo exp utiliza 8 bits e o campo frac utiliza 23 bits.

M = $(-1)^{s}$*( $1.(frac)_2$ )* $2^{e-127}$

Vamos representar o número 0.5 no computador.

0.5 = $\frac{1}{2}$ 
Na representação binária,

(0.5)₁₀ = $(0.1)_2$ = ($(-1)^{0}$ *1.0 x 2^-1)₂

Na representação ponto flutuante,

s = 1

frac = 0

e-127 = -1 => e = 127-1 = 126

#include <stdio.h>

#include <stdlib.h>

int main(){

 float x;

 scanf("%f",&x);

 int y = *((int *)&x);

 int i;

 int frac; //23 bits

 int expoente; //8bits

 int sinal; //1bit

 for(i=31;i>=0;i--)

  if( ( y & (1<<i) )!=0 ) printf("1");

  else printf("0");

 printf("\n"); 

 frac = y % (1<<23);

 y = y / (1<<23);

 printf("frac %d\n", frac);

 expoente = y % (1<<8);

 y = y / (1<<8);

 printf("expoente %d\n", expoente);

 sinal = y;

 printf("sinal %d\n",sinal); 

 system("PAUSE");

}

Entrada

0.5

Saída

00111111000000000000000000000000

frac 0

expoente 126

sinal 0

Leio o artigo
0,999...OU“COMO COLOCAR UM BLOCOQUADRADO EM BURACO REDONDO"
Revista Eureka 29

Floating-point arithmetic with arbitrary

1. Motivation 
  The floating-point arithmetic used in computers is prone to some errors related to the way that real numbers are represented (binary base) and also related to the size of the representation (32 bits or 64 bits). These two limiting factors often cause errors in precision calculations performed with floating point numbers. 


As in the decimal base, certain real numbers has an infinite representation of digits. Even some numbers with finite decimal base representation can have an infinite binary base representation. As an example, the decimal representation is 0.1 is 0.0(0011) in binary base representation. The numbers in brackets is repeated indefinitely. Moreover, the decimal representation of 0.125 is finite in the floating-point binary base 0.001. 


A floating point number is stored as follows (+ | -) s * 2 ^ e. The s represents the sginificante. The significant  can have 24 or 53 binary digits. 


For example, the number 0.1 is represented in the computer as follows: 


1.1001100110011001100110011001100110011001100110011010 * 2 ^ -4 


This representation will result in noticeable errors in simple calculations: 




Consider the following C program: 

double x = 1.0; 
  for (i = 0, i <100; i + +) { 
  x = x - 0.01; 
  }  
   printf ("% .15 lf \ n", x);
  

The output of this program will be: 
-0.000000000000001 


The idea presented in [1] is to calculate precision error associated with an operation to store it and spread it with the calculation result. Thus, the result of an operation becomes not only a floating-point and becomes an expansion e = en + en-1 + ... + e2 + e1, where each component ei is a floating-point number. 


The addition operation of two floating point numbers is as follows: 

# Define Fast_Two_Sum_Tail (a, b, x, y) \
 bvirt = x - a, \
 y = b - bvirt
 # Define Fast_Two_Sum (a, b, x, y) \
 x = (REAL) (a + b) \
 Fast_Two_Sum_Tail (a, b, x, y)

  
  The expansion and generated by the addition of a and b is x + y. 
   
Figure extracted doctoral qualification Markos Oliveira Freitas 


The sum of expansion with a floating-point number is as follows: 


Figure extracted doctoral qualification Markos Oliveira Freitas 


Using this idea, the algorithm is as follows: 

int grow_expansion (elen, e, b, h) / * and Can Be and h being the same.  * / 
  int elen / / size of the expansion 
  REAL * and / / expansion 
  REAL b / / floating-point add 
  REAL * h / / output expansion 

and [0] = 1.0; 
  h [0] = 0.0; 
  for (i = 0, i <100; i + +) { 
  elen = grow_expansion (elen, e, - 0.01, h); 
  expansioncopy (elen, and h); 
  } 
    printf ("% .15 lf \ n", estimate (elen, e));  

The result of the program will 

0.000000000000000 

The C code with the operations can be find here . 




References 
[1] JR Shewchuk. Adaptive precision floating-point arithmetic and fast robust geometric predicates . Computational Geometry & Discrete, 18 (3). 
   

Aritmética com ponto-flutuante arbitrária

1. Motivação
    A aritmética de ponto-flutuante utilizada nos computadores é susceptível a alguns erros relacionados  com a forma que os números reais são representados (base binária) e também relacionado com o tamanho da representação (32 bits ou 64 bits). Esses dois fatores limitantes frequentemente geram erros de precisão nos cálculos realizados com os números com ponto flutuante.


    Como na base decimal, certos números reais tem uma representação infinita de dígitos. Mesmos alguns números com a representação na base decimal finita, podem ter uma quantidade infinita de dígitos na base binária. Como, por exemplo,  o número decimal 0.1 tem representação binária 0.0(0011). Os números entre parênteses repete-se indefinidamente. Por outro lado, o número decimal 0.125 tem representação de ponto-flutuante finita na base binária 0.001.


  Um número ponto flutuante é armazenado da seguinte maneira (+|-) s*2^e. O s representa o sginificante. O significante pode ter 24 ou 53 dígitos binários.


    Por exemplo, o número 0.1 é representado no computador da seguinte maneira:


 1.1001100110011001100110011001100110011001100110011010*2^-4


    Essa representação ocasionará erros perceptíveis em cálculos simples:


    Considere o seguinte programa em C:

 double x = 1.0;
 for(i=0;i<100;i++){
 x = x - 0.01;
 } 
 printf("%.15lf\n",x);
 

   A saída desse programa será:   
  -0.000000000000001




    A idéia apresentada em [1] consiste em calcular o erro de precisão associado uma operação armazená-la e propagá-la com o resultado do cálculo. Dessa maneira, o resultado de uma operação deixa de ser apenas um ponto-flutuante e passa a ser um expansão e = en+en-1+...+e2+e1, onde cada componente ei é um número ponto-flutuante.


    A operação de adição de dois números de ponto flutuante fica da seguinte maneira:

#define Fast_Two_Sum_Tail(a, b, x, y) \
 bvirt = x - a; \
 y = b - bvirt
 #define Fast_Two_Sum(a, b, x, y) \
 x = (REAL) (a + b); \
 Fast_Two_Sum_Tail(a, b, x, y)

  
 A expansão e gerada pela adição de a e b é x+y.
  
  Figura extraída qualificação de doutorado Markos Oliveira Freitas


 A soma de expansão com um número com ponto-flutuante fica da seguinte maneira:



    Figura extraída qualificação de doutorado Markos Oliveira Freitas


     Utilizando essa idéia, o algoritmo fica da seguinte maneira:   

  int grow_expansion(elen, e, b, h) /* e and h can be the same. */
  int elen; //tamanho da expansão
  REAL *e;  //expansão
  REAL b;   //ponto-flutuante adicionado
  REAL *h;  //expansão de saída

  e[0] = 1.0;
  h[0] = 0.0;
  for(i=0;i<100;i++){
   elen = grow_expansion(elen,e,-0.01,h);
   expansioncopy(elen,e,h);
  }
  printf("%.15lf\n", estimate(elen, e) );

O resultado do programa será  

0.000000000000000

O código C com as operações pode ser encontada aqui.




Referências
[1] J. R. Shewchuk. Adaptive precision floating-point arithmetic and fast robust   geometric predicates. Discrete & Computational Geometry, 18(3).