Como analisar manualmente um número de ponto flutuante de uma string

https://stackoverflow.com/questions/85223

01-07-2019
|

Pergunta

É claro que a maioria das línguas têm funções de biblioteca para isso, mas suponho que eu quero fazê-lo eu mesmo.

Suponha que a bóia é dada como em um programa C ou Java (exceto para o 'f' ou 'd' sufixo), por exemplo "4.2e1", ".42e2" ou simplesmente "42". Em geral, temos a "parte inteira" antes do ponto decimal, o "parte fracionária" depois do ponto decimal, e o "expoente". Todos os três são números inteiros.

É fácil de encontrar e processar os dígitos individuais, mas como você compor-los em um valor do tipo float ou double sem perder precisão?

Estou pensando em multiplicando a parte inteira com 10 ^ n , onde n é o número de dígitos na parte fracionária, e em seguida, adicionando a parte fracionária para a parte inteira e subtraindo n do expoente. Isso transforma efetivamente 4.2e1 em 42e0, por exemplo. Então eu poderia usar a função pow para computar 10 ^ expoente e multiplicar o resultado com a nova parte inteira. A questão é, será que essa precisão máxima garantia método todo?

Quaisquer pensamentos sobre isso?

Solução

eu montar directamente o número de ponto flutuante usando sua representação binária.

Leia no caráter número um após o outro e primeiro descobrir todos os dígitos. Fazer isso em aritmética inteira. Também manter o controle de ponto decimal e expoente. Este será importante mais tarde.

Agora você pode montar o seu número de ponto flutuante. A primeira coisa a fazer é digitalizar a representação inteira dos dígitos para o primeiro conjunto de um bit (maior para o menor).

Os bits imediatamente a seguir ao primeiro-bit são sua mantissa.

Obtendo o expoente não é duro. Você sabe que a primeira posição de um bit, a posição do ponto decimal e expoente opcional da notação científica. Combiná-los e adicionar o viés ponto expoente flutuante (eu acho que é 127, mas verifique alguma referência, por favor).

Este expoente deve estar em algum lugar na faixa de 0 a 255. Se é maior ou menor do que você tem um positivo ou número infinito negativo (caso especial).

Guarde o expoente como nos bits 24 a 30 do seu float.

O bit mais significativo é simplesmente o sinal. Um meio negativo, zero meios positivo.

É mais difícil de descrever do que realmente é, tentar decompor um número de ponto flutuante e tomar um olhar para o expoente e mantissa e você vai ver como ela realmente é fácil.

Btw - fazendo a aritmética em si mesmo ponto flutuante é uma má idéia, porque você sempre irá forçar o seu mantissa a ser truncado para 23 bits significativos. Você não terá uma representação exata dessa forma.

Outras dicas

Todas as outras respostas ter perdido como duro é fazer isso corretamente. Você pode fazer uma primeira abordagem corte neste que é preciso, até certo ponto, mas até você levar em conta IEEE arredondamento modos (et al), você nunca terá a direito resposta. Eu tenho escrito implementações ingênuas antes com uma quantidade bastante grande de erro.

Se você não está com medo de matemática, eu recomendo a leitura do seguinte artigo de David Goldberg, O que cada cientista computador deve saber sobre Floating-Point Arithmetic . Você vai obter uma melhor compreensão do que está acontecendo sob o capô, e por que os bits são definidos como tal.

Meu melhor conselho é começar com uma implementação atoi de trabalho, e sair de lá. Você encontrará rapidamente você está perdendo coisas, mas alguns olhares em strtod source 's e você estará no caminho certo (o que é um longo, longo caminho). Eventualmente, você vai elogiar Inserir diety aqui que existem bibliotecas padrão.

/* use this to start your atof implementation */

/* atoi - christopher.watford@gmail.com */
/* PUBLIC DOMAIN */
long atoi(const char *value) {
  unsigned long ival = 0, c, n = 1, i = 0, oval;
  for( ; c = value[i]; ++i) /* chomp leading spaces */
    if(!isspace(c)) break;
  if(c == '-' || c == '+') { /* chomp sign */
    n = (c != '-' ? n : -1);
    i++;
  }
  while(c = value[i++]) { /* parse number */
    if(!isdigit(c)) return 0;
    ival = (ival * 10) + (c - '0'); /* mult/accum */
    if((n > 0 && ival > LONG_MAX)
    || (n < 0 && ival > (LONG_MAX + 1UL))) {
      /* report overflow/underflow */
      errno = ERANGE;
      return (n > 0 ? LONG_MAX : LONG_MIN);
    }
  }
  return (n>0 ? (long)ival : -(long)ival);
}

O algoritmo "padrão" para converter um número decimal para a melhor aproximação de ponto flutuante é de William Clinger Como ler números de ponto flutuante com precisão , download de aqui . Note-se que fazendo isso corretamente requer inteiros de múltipla precisão, pelo menos, uma certa percentagem do tempo, para casos de canto alça.

Algoritmos para ir para o outro lado, imprimindo o melhor número decimal de um número-flutuante, são encontrados em Burger e Dybvig de Números Impressão ponto-flutuante com rapidez e precisão , para download aqui . Isso também requer múltiplo-precisão inteiro aritmética

corretamente arredondado Binary-Decimal Ver também David M de Gay e Decimal Conversões -Binary para algoritmos que vão nos dois sentidos.

Você poderia ignorar o decimal ao analisar (exceto para a sua localização). Diga a entrada era: 156.7834e10 ... Isto poderia ser facilmente analisado para o número inteiro 1.567.834 seguido por e10, que você iria em seguida, modificar a e6, desde o decimal foi de 4 dígitos a partir do final da parte "numeral" do flutuador.

A precisão é um problema. Você precisa verificar a especificação IEEE do idioma que você está usando. Se o número de bits na Mantissa (ou fração) é maior do que o número de bits em seu tipo Integer, então você vai precisão possivelmente perder quando alguém digitar um número, tais como:

5123.123123e0 -. Convertidos para 5123123123 em nosso método, que não se encaixa em um inteiro, mas os bits para 5,123123123 pode caber na mantissa da especificação flutuador

Claro, você poderia usar um método que leva cada dígito na frente do decimal, multiplica o total atual (em um float) por 10, em seguida, adiciona o novo dígito. Para dígitos após o decimal, multiplicar o dígito por um poder cada vez maior de 10 antes de adicionar ao total atual. Este método parece implorar a questão de por que você está fazendo isso em tudo, no entanto, uma vez que requer o uso do ponto flutuante primitiva sem usar as bibliotecas de análise prontamente disponíveis.

De qualquer forma, boa sorte!

Sim , você pode decompor a construção em operações de ponto flutuante enquanto estas operações são EXACT , e você pode pagar um único inexata final operação.

Infelizmente, as operações de ponto flutuante logo se tornar inexata, quando exceder a precisão de mantissa, os resultados são arredondados. Uma vez que um "erro" arredondamento é introduzido, será acumulado em outras operações ...
Então, geralmente, NÃO , você não pode usar tal algoritmo ingênuo para converter decimais arbitrárias, isso pode levar a um número incorretamente arredondado, fora por vários ulp do correto, como outros já lhe disse .

MAS ver LET quão longe podemos GO:

Se você reconstruir cuidadosamente o flutuador como esta:

if(biasedExponent >= 0)
    return integerMantissa * (10^biasedExponent);
else
    return integerMantissa / (10^(-biasedExponent));

existe um risco de ultrapassar precisão tanto quando acumulando o integerMantissa se ele tem muitos dígitos, e ao levantar 10 elevado à potência de biasedExponent ...

Felizmente, se duas primeiras operações são exatos, então você pode pagar uma operação final inexata * ou /, graças às propriedades IEEE, o resultado será arredondado corretamente.

Vamos aplicar isso para floats precisão simples que têm uma precisão de 24 bits.

10^8 > 2^24 > 10^7

Observando que múltiplo de 2 só vai aumentar o expoente e deixar o mantissa inalterada, só temos de lidar com potências de 5 para exponenciação de 10:

5^11 > 2^24 > 5^10

No entanto, você pode pagar 7 dígitos de precisão na integerMantissa e uma biasedExponent entre -10 e 10.

Em precisão dupla, 53 bits

10^16 > 2^53 > 10^15
5^23 > 2^53 > 5^22

Então você pode pagar 15 dígitos decimais e um expoente polarizado entre -22 e 22.

É até você para ver se seus números sempre caem na faixa correta ... (Se você é realmente complicado, você poderia arranjar para o equilíbrio mantissa e expoente por inserir / remover zeros à direita).

Caso contrário, você terá que usar alguma precisão estendida.
Se o seu idioma fornece inteiros de precisão arbitrária, então é um pouco complicado para obtê-lo direito, mas não tão difícil, eu fiz isso em Smalltalk e blog sobre isso em http://smallissimo.blogspot.fr/2011/09/clarifying-and-optimizing.html e http://smallissimo.blogspot.fr/2011/09/reviewing-fraction-asfloat.html

Note que essas são implementações simples e ingênuas. Felizmente, libc é mais otimizado.

Meu primeiro pensamento é para analisar a cadeia em uma mantissa int64 e um int decimal expoente usando apenas os primeiros 18 dígitos do mantissa. Por exemplo, 1.2345e-5 seria analisado em 12345 e -9. Então eu iria manter multiplicando o mantissa por 10 e diminuindo o expoente até o mantissa foi 18 dígitos (> 56 bits de precisão). Então eu ficaria o expoente decimal-se em uma mesa para encontrar um fator e expoente binário que pode ser usado para converter o número de decimal n * 10 ^ m para p binário * 2 ^ forma q. O factor seria outro int64 então eu multiplicar a mantissa por isso de tal forma que o topo I obtido 64-bits do número de bits 128 resultante. Este int64 mantissa pode ser convertido para um float perdendo apenas a precisão necessária e o expoente 2 ^ q podem ser aplicadas usando multiplicação sem perda de precisão.

Eu esperaria que isso seja muito preciso e muito rápido, mas você também pode querer lidar com os números especiais Nan, -Infinity, -0,0 e infinito. Eu não pensei sobre os números desnormalizados ou modos de arredondamento.

Por que você tem que entender o padrão IEEE 754, a fim de representação binária adequada. Depois disso, você pode usar Float.intBitsToFloat ou Double.longBitsToDouble .

http://en.wikipedia.org/wiki/IEEE_754

Se você deseja que o resultado mais preciso possível, você deve usar uma precisão de trabalho superior interna, e depois downconvert o resultado para a precisão desejada. Se você não se importa algumas ULPs de erro, então você pode apenas repetidamente multiplicar por 10, quando necessário, com a precisão desejada. Gostaria de evitar a função pow (), uma vez que irá produzir resultados inexatos para grandes expoentes.

Não é possível converter qualquer cadeia arbitrária que representa um número em um casal ou flutuar sem perder precisão. Há muitos números fracionários que podem ser representados exatamente em decimal (por exemplo, "0.1") que só pode ser aproximada de bóia binário ou duplo. Esta é semelhante à forma como a fração 1/3 não pode ser representado exatamente em decimal, você só pode escrever 0,333333 ...

Se você não quiser usar uma função de biblioteca diretamente porque não olhar para o código-fonte para as funções de biblioteca? Você mencionou Java; a maioria dos JDKs fornecido com código fonte para as bibliotecas de classe para que você possa olhar para cima como o método java.lang.Double.parseDouble (String) funciona. É claro que algo como BigDecimal é melhor para controlar precisão e arredondamento modos, mas você disse que precisa para ser um float ou double.

Usando uma máquina de estado. É bastante fácil de fazer, e funciona mesmo se o fluxo de dados é interrompido (você apenas tem que manter o estado eo resultado parcial). Você também pode usar um gerador de analisador (se você está fazendo algo mais complexo).

Eu concordo com terminal. Uma máquina de estado é a melhor maneira de realizar essa tarefa, pois há muitas maneiras estúpidas um analisador pode ser quebrado. Eu estou trabalhando em um agora, eu acho que é completa e tem Acho que 13 estados.

O problema não é trivial.

Eu sou um hardware ponto engenheiro de hardware concepção interessados ??flutuante. Estou na minha segunda implementação.

Eu encontrei este hoje http://speleotrove.com/decimal/decarith.pdf

que na página 18 dá alguns casos de teste interessante.

Sim, eu li o artigo de Clinger, mas sendo um engenheiro de hardware espírito simples, eu não posso começar minha mente em torno do código apresentado. A referência para o algoritmo de Steele como asnwered no texto de Knuth foi útil para mim. Entrada e saída são problemáticas.

Todas as referências acima mencionadas para vários artigos são excelentes.

Eu ainda tenho que inscreva-se aqui ainda, mas quando eu faço, assumindo que o login não é tomada, será broh. (Broh-ponto).

Clyde

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow