Gal's nøjagtige tabeller - Gal's accurate tables

Gals nøjagtige tabeller er en metode udtænkt af Shmuel Gal til at give nøjagtige værdier for specielle funktioner ved hjælp af en opslagstabel og interpolation . Det er en hurtig og effektiv metode til at generere værdier af funktioner som de eksponentielle eller de trigonometriske funktioner inden for sidste bit nøjagtighed for næsten alle argumentværdier uden at bruge udvidet præcisionsaritmetik.

Hovedideen i Gals nøjagtige tabeller er en anden tabel for den særlige funktion, der beregnes. Normalt er området opdelt i flere underområder, hver med forudberegnede værdier og korrektionsformler. For at beregne funktionen skal du slå det nærmeste punkt op og beregne en korrektion som en funktion af afstanden.

Gal's idé er ikke at beregne værdier med lige stor afstand, men snarere at forstyrre punkterne x, så både x og f ( x ) er næsten nøjagtigt repræsentative i det valgte numeriske format. Ved at søge på ca. 1000 værdier på hver side af den ønskede værdi x , kan en værdi findes således, at f ( x ) kan repræsenteres med mindre end ± 1/2000 bit afrundingsfejl . Hvis korrektionen også beregnes til ± 1/2000 bit nøjagtighed (hvilket ikke kræver ekstra flydepunktsnøjagtighed, så længe korrektionen er mindre end 1/2000 størrelsen af ​​den lagrede værdi f ( x ), og den beregnede korrektion er mere end ± 1/1000 bit væk fra nøjagtigt en halv bit (det vanskelige afrundingssag), så vides det, om den nøjagtige funktionsværdi skal afrundes op eller ned.

Teknikken giver en effektiv måde at beregne funktionsværdien inden for ± 1/1000 mindst-signifikant bit, dvs. 10 ekstra bit præcision. Hvis denne tilnærmelse er mere end ± 1/1000 lidt væk fra nøjagtigt midt mellem to repræsentative værdier (hvilket sker 99,8% af tiden), er det korrekt afrundede resultat klart.

Kombineret med en udvidet-præcision reservealgoritme kan dette beregne det korrekt afrundede resultat i meget rimelig gennemsnitstid . I 2/1000 (0,2%) af tiden kræves en sådan højere nøjagtighedsevaluering for at løse afrundingsusikkerheden, men dette er sjældent nok til, at det har ringe effekt på den gennemsnitlige beregningstid.

Problemet med at generere funktionsværdier, der er nøjagtige til den sidste bit, er kendt som tabelproducentens dilemma .

Se også

Referencer

  • Gal, Shmuel (1986). "Computing elementære funktioner: En ny tilgang til at opnå høj nøjagtighed og god ydeevne". I Miranker, Willard L .; Toupin, Richard A. (red.). Nøjagtige videnskabelige beregninger (1 udgave). Proceedings of Computations, Symposium, Bad Neuenahr, Forbundsrepublikken Tyskland, 12.-14. Marts 1985: Springer-Verlag Berlin Heidelberg. s. 1–16. ISBN 978-3-540-16798-3.CS1 maint: placering ( link )
  • Gal, Shmuel ; Bachelis, Boris (1991). "Et nøjagtigt elementært matematisk bibliotek til IEEE floating point-standarden". ACM-transaktioner på matematisk software .
  • Muller, Jean-Michel (2006). Elementære funktioner: algoritmer og implementering (2. udgave). Boston, MA, USA: Birkhäuser . ISBN 978-0-8176-4372-0. LCCN  2005048094 .
  • Muller, Jean-Michel (12-12-2016). Elementære funktioner: algoritmer og implementering (3. udgave). Boston, MA, USA: Birkhäuser . ISBN 978-1-4899-7981-0.
  • Stehlé, Damien; Zimmermann, Paul (2005). "Gal's nøjagtige tabelmetode revideret" (PDF) . 17. IEEE-symposium om computeraritmetik (ARITH'05) . s. 257-264. doi : 10.1109 / ARITH.2005.24 . ISBN 0-7695-2366-8. Arkiveret (PDF) fra originalen den 15/01/2018 . Hentet 15-01-2018 .