Cálculo de reais: ponto flutuante vs TTE vs teoria de domínio vs etc

19

Atualmente, o cálculo de reais nas línguas mais populares ainda é feito através de operações de ponto flutuante. Por outro lado, teorias como a efetividade do tipo dois (ETT) e a teoria do domínio há muito prometem o cálculo exato dos reais. Claramente, o problema da precisão do ponto flutuante não diminuiu em relevância; portanto, por que essas teorias não se tornaram mais comuns e por que não há implementações mais visíveis delas?

Por exemplo, existem domínios de aplicativos em que não nos importamos muito com erros de ponto flutuante? Existem preocupações significativas de complexidade?

Feiticeiro de DM
fonte

Respostas:

17

Eu trabalho com computação em número real e gostaria de saber a resposta real. Mas eu posso especular. É um problema sociológico, eu acho.

A comunidade de pessoas que trabalham com aritmética real exata consiste em teóricos que não estão acostumados a desenvolver software. Portanto, eles geralmente relegam a tarefa de implementação aos alunos (uma exceção notável é o iRRAM de Norbert Müller ), ou eles têm suas próprias implementações de brinquedos .

As pessoas que fazem têm a programação necessária mojo não têm o fundo teórico necessário. Sem base teórica sólida, é difícil projetar a aritmética real exata corretamente. Por exemplo, é um erro adicionar muitos números reais em um forloop, pois você terá um desempenho inaceitável devido à perda de precisão. Se você deseja adicionar muitos e muitos reais, deve fazê-lo com uma estrutura semelhante a uma árvore, levando em consideração as magnitudes das somas parciais. Outra coisa que é difícil de passar é que <e =como função booleana total com os reais simplesmente não existem (você pode ter =, mas isso retorna falseou diverge, e <diverge quando dado dois reais iguais).

Por fim, não está claro que sabemos como implementar bibliotecas para aritmética real exata. Eles não são as peças usuais de bibliotecas que apenas definem alguns tipos de dados e algumas funções neles. Frequentemente, a aritmética real exata requer modos especiais de controle. Por exemplo, o iRRAM assume a execução principal do programa (literalmente, seqüestra main), bem como a entrada e saída padrão, para que possa executar novamente o programa quando ocorrer perda de precisão. Minha biblioteca de aritmética real em Haskell acontece em uma Stagedmônada (que é essencialmente a Readermônada). A maioria das pessoas espera que os números reais sejam "apenas outro tipo de dados", mas tenho minhas dúvidas sobre isso.

Andrej Bauer
fonte
Sou quase totalmente ignorante da aritmética real exata, mas não é possível implementar a soma de Kahan nela?
Jjg 16/07
11
Hmm, acho que não. Pense na aritmética real exata como a aritmética de intervalo que ajusta automaticamente a precisão intermediária para alcançar a precisão de saída desejada.
Andrej Bauer
3
Além da falta de entendimento dos programadores sobre o fato de que números reais são objetos infinitos e suas consequências para o que pode ser feito programaticamente, acho que a falta de suporte de hardware também é importante. É difícil convencer as pessoas a usar algo com sobrecarga significativa de tempo e memória apenas para correção.
Kaveh
11
Vi que há alguma atividade na implementação de computação real com tipos coindutivos. Parece-me que os tipos coindutores ainda são bastante difíceis de acertar (certamente não sou especialista nisso), mas você acha que isso é promissor para o uso mais amplo da computação exata exata?
SorcererofDM
3
Qualquer implementação que use fluxos de dígitos, ou qualquer outra coisa que tenha uma taxa fixa de convergência, é prejudicada desde o início, pois convergirá muito lentamente. Além disso, as implementações baseadas em fluxo tendem a forçá-lo a calcular todas as aproximações anteriores para obter a próxima, o que também é um erro de design.
Andrej Bauer
10

Em geral, as pessoas sempre se preocupam com erros de ponto flutuante. No entanto, eu discordo de Andrej e não acho que os carros alegóricos sejam preferíveis a reais de precisão arbitrários (na maioria das vezes) por motivos sociológicos.

Eu acredito que o principal argumento contra o cálculo exato dos reais é um dos desempenho . Portanto, a resposta curta é: sempre que o desempenho for mais importante que a precisão, convém usar números de ponto flutuante .

A aplicação que vem à mente é o uso da dinâmica de fluidos computacional para projetar a aerodinâmica de carros ou aviões, onde pequenos erros de computação são facilmente compensados ​​com os ganhos astronômicos do uso de unidades de ponto flutuante dedicadas encontradas em muitos processadores comuns.

Em particular, o problema de representar uma grande variedade de números reais usando um número fixo de bits não é tão trivial quanto pode parecer à primeira vista. Na simulação numérica, os valores podem variar amplamente (por exemplo, quando há turbulência), portanto, os cálculos de ponto fixo não são apropriados.

Mesmo quando a precisão não é fixada pelo hardware, o uso de números de precisão arbitrários pode ser várias ordens de magnitude mais lento que o uso de números de ponto flutuante. De fato, mesmo no bom caso em que todos os números são racionais, operações simples como inverter uma matriz podem resultar em denominadores grandes e difíceis de controlar (veja aqui um exemplo). Muitos pacotes grandes de otimização linear usam pontos flutuantes com modos de arredondamento apropriados para encontrar soluções aproximadas devido a esse problema exato (veja, por exemplo, a maioria dos programas encontrados aqui ).

cody
fonte
11
existem lacunas comprovadas entre alguma forma de computação real exata e computação de ponto flutuante?
SorcererofDM
11
Não que eu saiba, eu tenho medo. Sean Gao tem alguns resultados interessantes sobre a complexidade dos procedimentos de decisão aproximados em relação aos reais (veja o resumo de sua tese ) e, é claro, o denominador no inverso de uma matriz cresce, na pior das hipóteses, como seu determinante .
Cody
-6

π -ness"? Essencialmente, os números reais são definidos por vários processos limite; muitos desses processos limitados receberam nomes especiais, e alguns deles são especiais o suficiente para formar subconjuntos significativos dos reais (por exemplo, números algébricos)

O que quero dizer é que, para calcular exatamente, é necessário ter espaços reservados para nomes especiais e nomes familiares para naturais. Em algum momento, você desejará aproximar o valor exato para aplicá-lo a algo no mundo real. Como se vê, é muito mais eficiente lidar com todo o problema como aproximações desde o início, a menos que você tenha necessidades muito especializadas.

R

david rush
fonte