Taules precises de Gal

Les taules precises de Gal són un método ideat per Shmuel Gal en la década de 1980 per a proporcionar valors precisos de funcions especials, utilisant una taula de busca i interpolació. És un método ràpit i eficient per a generar valors de funcions com les funcions exponencials o trigonométricas en una precisió d'últim bit per a casi tots els valors d'argument sense utilisar aritmètica de precisió estesa.

Procediment de càlcul

L'idea principal en les taules precises de Gal és una tabulació diferent per a la funció especial que s'està calculant. Comunament, el ranc es dividix en varis subrangos, cada u en valors precalculats i fòrmules de correcció. Per a calcular la funció, es busca el punt més propenc i es calcula una correcció en funció de la distància al punt buscat.

L'idea de Gal és no calcular prèviament valors equidistants, sino pertorbar els punts x de modo que tant x com a f(x) siguen casi exactament representables en el format numèric elegit. Per mig de la busca en aproximadament 1000 valors a cada costat del valor de x que es desija, es pot trobar un valor tal que f (x) es pot representar en menys de ± 1/2000 bit d'error de grosseig. Si la correcció també es calcula en una precisió de ± 1/2000 bit (que no requerix precisió adicional de punt flotant sempre que la correcció siga menor que 1/2000, la magnitut del valor almagasenat f(x) i la correcció calculada està a més de ± 1/1000 de bit d'exactament mig bit (el cas de grosseig que requerix un càlcul més), llavors se sap si el valor exacte de la funció deu redonejar-se cap a dalt o cap a avall.

La tècnica proporciona una manera eficient de calcular el valor de la funció dins de ± 1/1000 bit menys significatiu, és dir, 10 bits adicionals de precisió. Si esta aproximació està a més de ± 1/1000 d'un bit de distància d'exactament la mitat de camí entre dos valors representables (que ocorre sempre llevat 2/1000 de les voltes, és dir, en el 99.8% dels casos), llavors el resultat correctament redonejat és clar.

Combinat en un algoritme de recuperació de precisió estesa, açò pot calcular el resultat correctament redonejat en un temps promig molt raonable.

En tan sol el 0.2% de les voltes (2 de cada 1000), es requerix una evaluació de la funció de major precisió per a resoldre l'incertitut del grosseig, pero açò és tan infreqüent que té poc efecte en el temps promig de càlcul.

El problema de generar valors de funció que són precisos fins a l'últim bit es coneix com el dilema del creador de taules.

Vore també

• Menge flotant
• Grosseig

Bibliografia

• Gal (1986). «Computing elementary functions: A new approach for achieving high accuracy and good performance», Miranker (ed.). Accurate Scientific Computations, 1 edició, Proceedings of Computations, Symposium, Bad Neuenahr, Federal Republic of Germany, March 12-14, 1985: Springer-Verlag Berlin Heidelberg, p. 1–16. ISBN 978-3-540-16798-3.
• «An accurate elementary mathematical library for the IEEE floating point standard».ACM Transactions on Mathematical Software.
• Muller (2006). Elementary Functions: Algorithms and Implementation, 2 edició, Boston, MA, USA: Birkhäuser. ISBN 978-0-8176-4372-0.
• Muller, Jean-Michel (12 de decembre de 2016). Elementary Functions: Algorithms and Implementation, 3 edició, Boston, MA, USA: Birkhäuser. ISBN 978-1-4899-7981-0.

• Stehlé, Damien; Zimmermann, Paul (2005). «Gal's Accurate Tables Method Revisited», 17th IEEE Symposium on Computer Arithmetic (ARITH'05), pp. 257–264. doi:10.1109/ARITH.2005.24. ISBN 0-7695-2366-8.