Quão determinista é a imprecisão do ponto flutuante?

Eu entendo que os cálculos de ponto flutuante têm problemas de precisão e há muitas perguntas explicando o motivo. Minha pergunta é se eu executar o mesmo cálculo duas vezes, posso sempre confiar nele para produzir o mesmo resultado? Quais fatores podem afetar isso?

  • Tempo entre cálculos?
  • Estado atual da CPU?
  • Hardware diferente?
  • Linguagem / plataforma / SO?
  • Erupções solares?

Eu tenho uma simples simulação de física e gostaria de gravar sessões para que elas possam ser repetidas. Se os cálculos puderem ser confiáveis, eu só precisarei registrar o estado inicial mais qualquer input do usuário e eu sempre poderei reproduzir exatamente o estado final. Se os cálculos não forem precisos, os erros no início podem ter enormes implicações no final da simulação.

No momento, estou trabalhando no Silverlight, mas estaria interessado em saber se essa pergunta pode ser respondida em geral.

Atualização: As respostas iniciais indicam que sim, mas aparentemente isso não é totalmente claro como discutido nos comentários para a resposta selecionada. Parece que vou ter que fazer alguns testes e ver o que acontece.

Pelo que entendi, você só tem garantido resultados idênticos, desde que você esteja lidando com o mesmo conjunto de instruções e compilador, e que quaisquer processadores que você execute respeitam estritamente os padrões relevantes (ie IEEE754). Dito isso, a menos que você esteja lidando com um sistema particularmente caótico, qualquer desvio nos cálculos entre as execuções provavelmente não resultará em comportamento de bugs.

Pegadinhas específicas de que tenho conhecimento:

1.) alguns sistemas operacionais permitem que você defina o modo do processador de ponto flutuante de forma a quebrar a compatibilidade.

2.) resultados intermediários de ponto flutuante geralmente usam precisão de 80 bits no registrador, mas apenas 64 bits na memory. Se um programa é recompilado de uma maneira que altera o registro de spilling dentro de uma function, ele pode retornar resultados diferentes em comparação com outras versões. A maioria das plataformas lhe dará uma maneira de forçar todos os resultados a serem truncados para a precisão da memory.

3.) as funções da biblioteca padrão podem mudar entre as versões. Eu entendo que existem alguns exemplos incomuns encontrados no gcc 3 vs 4.

4.) O próprio IEEE permite que algumas representações binárias sejam diferentes … especificamente valores NaN, mas não consigo me lembrar dos detalhes.

A resposta curta é que os cálculos FP são totalmente deterministas, de acordo com o Padrão de Pontos Flutuantes IEEE , mas isso não significa que eles sejam totalmente reproduzíveis em máquinas, compiladores, sistemas operacionais, etc.

A longa resposta a essas perguntas e mais pode ser encontrada no que provavelmente é a melhor referência em ponto flutuante, o que cada cientista da computação de David Goldberg deve saber sobre aritmética de ponto flutuante . Pule para a seção sobre o padrão IEEE para os detalhes principais.

Para responder rapidamente aos seus pontos de bala:

  • O tempo entre os cálculos e o estado da CPU tem pouco a ver com isso.

  • O hardware pode afetar as coisas (por exemplo, algumas GPUs não são compatíveis com o ponto flutuante IEEE).

  • Linguagem, plataforma e sistema operacional também podem afetar as coisas. Para uma descrição melhor do que eu posso oferecer, veja a resposta de Jason Watkins. Se você estiver usando Java, dê uma olhada no discurso de Kahan sobre as inadequações de ponto flutuante do Java .

  • Flares solares podem importar, espero que com pouca frequência. Eu não me preocuparia muito, porque se eles importam, então todo o resto está estragado também. Eu colocaria isso na mesma categoria que me preocupar com o EMP .

Finalmente, se você estiver fazendo a mesma sequência de cálculos de ponto flutuante nas mesmas inputs iniciais, então as coisas devem ser reproduzidas exatamente bem. A seqüência exata pode mudar dependendo do seu compilador / os / biblioteca padrão, assim você pode obter alguns pequenos erros desta maneira.

Onde você geralmente tem problemas em ponto flutuante é se você tem um método numericamente instável e você começa com inputs FP que são aproximadamente as mesmas, mas não completamente. Se o seu método é estável, você deve ser capaz de garantir a reprodutibilidade dentro de alguma tolerância. Se você quiser mais detalhes do que isso, então dê uma olhada no artigo FP de Goldberg, acima, ou pegue um texto introdutório sobre análise numérica.

Eu acho que a sua confusão está no tipo de imprecisão em torno do ponto flutuante. A maioria dos idiomas implementa o padrão de ponto flutuante IEEE Este padrão mostra como os bits individuais dentro de um float / double são usados ​​para produzir um número. Normalmente, um float consiste em quatro bytes e oito bytes duplos.

Uma operação matemática entre dois números de ponto flutuante terá o mesmo valor todas as vezes (conforme especificado no padrão).

A imprecisão vem na precisão. Considere um int contra um float. Ambos normalmente ocupam o mesmo número de bytes (4). No entanto, o valor máximo que cada número pode armazenar é muito diferente.

  • int: aproximadamente 2 bilhões
  • float: 3.40282347E38 (um pouco maior)

A diferença está no meio. int, pode representar cada número entre 0 e aproximadamente 2 bilhões. Float no entanto não pode. Pode representar 2 bilhões de valores entre 0 e 3,40282347E38. Mas isso deixa uma gama completa de valores que não podem ser representados. Se uma equação matemática atingir um desses valores, ela deverá ser arredondada para um valor representável e, portanto, considerada “imprecisa”. Sua definição de imprecisas pode variar :).

Além disso, enquanto Goldberg é uma ótima referência, o texto original também está errado: o IEEE754 não é recomendado para ser portátil . Eu não posso enfatizar isso o suficiente, dada a freqüência com que essa afirmação é feita com base no skimming do texto. Versões posteriores do documento incluem uma seção que discute isso especificamente :

Muitos programadores podem não perceber que mesmo um programa que usa apenas os formatos numéricos e as operações prescritas pelo padrão IEEE pode calcular resultados diferentes em sistemas diferentes. De fato, os autores do padrão pretendiam permitir que diferentes implementações obtivessem resultados diferentes.

Desculpe, mas não posso deixar de pensar que todo mundo está perdendo o ponto.

Se a imprecisão é significativa para o que você está fazendo, então você deve procurar por um algoritmo diferente.

Você diz que, se os cálculos não são precisos, os erros no início podem ter grandes implicações no final da simulação.

Que meu amigo não é uma simulação. Se você está obtendo resultados extremamente diferentes devido a pequenas diferenças devido ao arredondamento e precisão, então as chances são de que nenhum dos resultados tenha qualquer validade. Só porque você pode repetir o resultado não o torna mais válido.

Em qualquer problema não-trivial do mundo real que inclua medições ou cálculos não inteiros, é sempre uma boa idéia introduzir erros menores para testar a estabilidade do seu algoritmo.

Esta resposta no FAQ C ++ provavelmente descreve o melhor:

http://www.parashift.com/c++-faq-lite/newbie.html#faq-29.18

Não é apenas que diferentes arquiteturas ou compiladores podem lhe causar problemas, os números apontando flutuantes já se comportam de maneiras estranhas dentro do mesmo programa. Como o FAQ indica se y == x é verdadeiro, isso ainda pode significar que cos(y) == cos(x) será falso. Isso ocorre porque a CPU x86 calcula o valor com 80 bits, enquanto o valor é armazenado como 64 bits na memory, portanto, você acaba comparando um valor de 64 bits truncado com um valor total de 80 bits.

O cálculo ainda é determinístico, no sentido de que executar o mesmo binário compilado lhe dará o mesmo resultado a cada vez, mas no momento em que você ajusta a fonte um pouco, os sinalizadores de otimização ou compila com um compilador diferente todas as apostas estão desativadas e nada pode acontecer.

Praticamente falando, eu não é tão ruim assim, eu poderia reproduzir matemática flutuante apontando simples com uma versão diferente do GCC em 32 bit Linux bit por bit, mas no momento em que mudei para Linux 64bits o resultado não era mais o mesmo. Demos gravações criadas em 32bit não funcionaria em 64 bits e vice-versa, mas funcionaria bem quando executado no mesmo arco.

Como sua pergunta é marcada como C #, é importante enfatizar os problemas enfrentados no .NET:

  1. A matemática do ponto flutuante não é associativa – isto é, (a + b) + c não é garantido como igual a + (b + c) ;
  2. Compiladores diferentes irão otimizar seu código de diferentes maneiras, e isso pode envolver a reordenação de operações aritméticas.
  3. No .NET, o compilador JIT do CLR compilará seu código em tempo real, portanto, a compilation depende da versão do .NET na máquina durante a execução.

Isso significa que você não deve confiar em seu aplicativo .NET produzindo os mesmos resultados de cálculo de ponto flutuante quando executado em diferentes versões do .NET CLR.

Por exemplo, no seu caso, se você gravar o estado inicial e as inputs na sua simulação, em seguida, instalar um service pack que atualize o CLR, sua simulação pode não ser reproduzida de forma idêntica na próxima vez que você executá-lo.

Veja o post do blog de Shawn Hargreaves É matemática determinística do ponto flutuante? para uma discussão mais aprofundada relevante para o .NET.

HM Como o OP pediu por C #:

O bytecode C # é determinístico ou gera código diferente entre execuções diferentes? Eu não sei, mas eu não confiaria no Jit.

Eu poderia pensar em cenários onde o JIT tem alguns resources de qualidade de serviço e decide gastar menos tempo na otimização porque a CPU está fazendo um pesado processamento de dados em algum outro lugar (pense em codificação de DVD em segundo plano)? Isso pode levar a diferenças sutis que podem resultar em enormes diferenças mais tarde.

Além disso, se o próprio JIT for aprimorado (talvez como parte de um service pack talvez), o código gerado será alterado com certeza. O problema de precisão interna de 80 bits já foi mencionado.

Esta não é uma resposta completa à sua pergunta, mas aqui está um exemplo demonstrando que os cálculos duplos em C # não são determinísticos. Não sei por quê, mas código aparentemente não relacionado pode aparentemente afetar o resultado de um cálculo duplo downstream.

  1. Crie um novo aplicativo WPF no Visual Studio versão 12.0.40629.00 Update 5 e aceite todas as opções padrão.
  2. Substitua o conteúdo de MainWindow.xaml.cs por este:

     using System; using System.Windows; namespace WpfApplication1 { ///  /// Interaction logic for MainWindow.xaml ///  public partial class MainWindow : Window { public MainWindow() { InitializeComponent(); Content = FooConverter.Convert(new Point(950, 500), new Point(850, 500)); } } public static class FooConverter { public static string Convert(Point curIPJos, Point oppIJPos) { var ij = " Insulated Joint"; var deltaX = oppIJPos.X - curIPJos.X; var deltaY = oppIJPos.Y - curIPJos.Y; var teta = Math.Atan2(deltaY, deltaX); string result; if (-Math.PI / 4 <= teta && teta <= Math.PI / 4) result = "Left" + ij; else if (Math.PI / 4 < teta && teta <= Math.PI * 3 / 4) result = "Top" + ij; else if (Math.PI * 3 / 4 < teta && teta <= Math.PI || -Math.PI <= teta && teta <= -Math.PI * 3 / 4) result = "Right" + ij; else result = "Bottom" + ij; return result; } } } 
  3. Definir configuração de compilation para "Release" e criar, mas não execute no Visual Studio.

  4. Clique duas vezes no exe incorporado para executá-lo.
  5. Note que a janela mostra "Junta Isolada Inferior".
  6. Agora adicione esta linha antes de "string result":

     string debug = teta.ToString(); 
  7. Repita os passos 3 e 4.

  8. Note que a janela mostra "Junta isolada à direita".

Esse comportamento foi confirmado na máquina de um colega. Observe que a janela mostra consistentemente "Right Insulated Joint" se qualquer uma das seguintes condições for verdadeira: o exe é executado no Visual Studio, o exe foi criado usando a configuração de Depuração ou "Prefer 32-bit" está desmarcado nas propriedades do projeto.

É muito difícil descobrir o que está acontecendo, já que qualquer tentativa de observar o processo parece mudar o resultado.

Muito poucas FPUs atendem ao padrão IEEE (apesar de suas declarações). Portanto, executar o mesmo programa em um hardware diferente realmente lhe dará resultados diferentes. É provável que os resultados estejam em casos de canto que você já deve evitar como parte do uso de um FPU em seu software.

Os bugs do IEEE geralmente são corrigidos no software e você tem certeza de que o sistema operacional que está executando atualmente inclui as armadilhas e patches apropriados do fabricante? E quanto antes ou depois do sistema operacional ter uma atualização? Todos os bugs foram removidos e correções de bugs foram adicionadas? O compilador C está sincronizado com tudo isso e o compilador C está produzindo o código correto?

Testar isso pode ser inútil. Você não verá o problema até entregar o produto.

Observe a regra número 1 do FP: nunca use uma comparação if (algo = = algo). E a regra número dois do IMO teria a ver com ascii para fp ou fp para ascii (printf, scanf, etc). Há mais problemas de erros e erros do que no hardware.

Com cada nova geração de hardware (densidade), os efeitos do sol são mais aparentes. Nós já temos problemas com os SEUs na superfície dos planetas, portanto, independente dos cálculos de ponto flutuante, você terá problemas (poucos fornecedores se importaram em atender, então espere mais falhas com novos hardwares).

Ao consumir enormes quantidades de lógica, o FPU provavelmente será muito rápido (um único ciclo de clock). Não é mais lento que um inteiro alu. Não confunda isso com o moderno fpus sendo tão simples quanto alus, os fpus são caros. (Alus também consomem mais lógica para multiplicar e dividir para reduzir a um ciclo de clock, mas não é tão grande quanto o FPU).

Cumpra as regras simples acima, estude um ponto flutuante um pouco mais, entenda as verrugas e armadilhas que o acompanham. Você pode querer verificar se há infinito ou nans periodicamente. Seus problemas são mais prováveis ​​de serem encontrados no compilador e no sistema operacional do que no hardware (em geral não apenas matemática fp). O hardware (e software) moderno é, atualmente, por definição cheio de bugs, então tente ser menos problemático do que o que seu software executa.