Tabelas precisas de Gal - Gal's accurate tables

As tabelas precisas de Gal é um método desenvolvido por Shmuel Gal para fornecer valores precisos de funções especiais usando uma tabela de pesquisa e interpolação . É um método rápido e eficiente para gerar valores de funções como funções exponenciais ou trigonométricas com a precisão do último bit para quase todos os valores de argumento, sem usar aritmética de precisão estendida.

A ideia principal nas tabelas precisas de Gal é uma tabulação diferente para a função especial que está sendo calculada. Normalmente, o intervalo é dividido em vários subintervalos, cada um com valores pré-calculados e fórmulas de correção. Para calcular a função, procure o ponto mais próximo e calcule uma correção em função da distância.

A ideia de Gal é não pré-calcular valores igualmente espaçados, mas sim perturbar os pontos x de modo que tanto x quanto f ( x ) sejam quase exatamente representáveis ​​no formato numérico escolhido. Ao pesquisar aproximadamente 1000 valores em cada lado do valor desejado x , um valor pode ser encontrado tal que f ( x ) pode ser representado com menos de ± 1/2000 bit de erro de arredondamento . Se a correção também for calculada para ± 1/2000 bit de precisão (o que não requer precisão extra de ponto flutuante, desde que a correção seja menor que 1/2000, a magnitude do valor armazenado f ( x ) e a correção calculada está a mais de ± 1/1000 de um bit de distância de exatamente meio bit (o caso de arredondamento difícil), então sabe-se se o valor exato da função deve ser arredondado para cima ou para baixo.

A técnica fornece uma maneira eficiente de calcular o valor da função dentro de ± 1/1000 bit menos significativo, ou seja, 10 bits extras de precisão. Se essa aproximação estiver a mais de ± 1/1000 de um bit de distância exatamente do meio entre dois valores representáveis ​​(o que acontece 99,8% do tempo), o resultado arredondado corretamente é claro.

Combinado com um algoritmo de fallback de precisão estendida, isso pode calcular o resultado arredondado corretamente em um tempo médio muito razoável . Em 2/1000 (0,2%) do tempo, tal avaliação de maior precisão é necessária para resolver a incerteza de arredondamento, mas isso é raro o suficiente para ter pouco efeito no tempo médio de cálculo.

O problema de gerar valores de função precisos até o último bit é conhecido como o dilema do fabricante de mesa .

Veja também

Referências

  • Gal, Shmuel (1986). "Funções elementares de computação: uma nova abordagem para alcançar alta precisão e bom desempenho". Em Miranker, Willard L .; Toupin, Richard A. (eds.). Accurate Scientific Computations (1 ed.). Proceedings of Computations, Symposium, Bad Neuenahr, República Federal da Alemanha, 12-14 de março de 1985: Springer-Verlag Berlin Heidelberg. p. 1-16. ISBN 978-3-540-16798-3.Manutenção CS1: localização ( link )
  • Gal, Shmuel ; Bachelis, Boris (1991). "Uma biblioteca matemática elementar precisa para o padrão de ponto flutuante IEEE". Transações ACM em software matemático .
  • Muller, Jean-Michel (2006). Funções Elementares: Algoritmos e Implementação (2 ed.). Boston, MA, EUA: Birkhäuser . ISBN 978-0-8176-4372-0. LCCN  2005048094 .
  • Müller, Jean-Michel (2016-12-12). Funções Elementares: Algoritmos e Implementação (3 ed.). Boston, MA, EUA: Birkhäuser . ISBN 978-1-4899-7981-0.
  • Stehlé, Damien; Zimmermann, Paul (2005). "Método de tabelas precisas de Gal revisitado" (PDF) . 17º Simpósio IEEE em Aritmética Computacional (ARITH'05) . pp. 257–264. doi : 10.1109 / ARITH.2005.24 . ISBN 0-7695-2366-8. Arquivado (PDF) do original em 15/01/2018 . Recuperado em 15/01/2018 .