Movatterモバイル変換
[0]ホーム
[Python-Dev] Round Bug in Python 1.6?
Tim Peterstim_one@email.msn.com
Sat, 8 Apr 2000 21:26:23 -0400
[Vladimir Marangozov]> I'm not sure that this will be of any interest to you, number crunchers,> but a research team in computer arithmetics here reported some major> results lately: they claim that they "solved" the Table Maker's Dilemma> for most common functions in IEEE-754 double precision arithmetic.> (and no, don't ask me what this means ;-)Back in the old days, some people spent decades making tables of variousfunction values. A common way was to laboriously compute high-precisionvalues over a sparse grid, using e.g. series expansions, then extend that toa fine grid via relatively simple interpolation formulas between thehigh-precision results.You have to compute the sparse grid to *some* "extra" precision in order toabsorb roundoff errors in the interpolated values. The "dilemma" isfiguring out how *much* extra precision: too much and it greatly slows thecalculations, too little and the interpolated values are inaccurate.The "problem cases" for a function f(x) are those x such that the exactvalue of f(x) is very close to being exactly halfway between representablenumbers. In order to round correctly, you have to figure out whichrepresentable number f(x) is closest to. How much extra precision do youneed to use to resolve this correctly in all cases?Suppose you're computing f(x) to 2 significant decimal digits, using 4-digitarithmetic, and for some specific x0 f(x0) turns out to be 41.49 +- 3.That's not enough to know whether it *should* round to 41 or 42. So youneed to try again with more precision. But how much? You might try 5digits next, and might get 41.501 +- 3, and you're still stuck. Try 6 next?Might be a waste of effort. Try 20 next? Might *still* not be enough -- orcould just as well be that 7 would have been enough and you did 10x the workyou needed to do.Etc. It turns out that for most functions there's no general way known toanswer the "how much?" question in advance: brute force is the best methodknown.For various IEEE double precision functions, so far it's turned out that youneed in the ballpark of 40-60 extra accurate bits (beyond the native 53) inorder to round back correctly to 53 in all cases, but there's no *theory*supporting that. It *could* require millions of extra bits.For those wondering "why bother?", the practical answer is this: if a stdcould require correct rounding, functions would be wholly portable acrossmachines ("correctly rounded" is precisely defined by purely mathematicalmeans). That's where IEEE-754 made its huge break with tradition, byrequiring correct rounding for + - * / and sqrt. The places it left fuzzy(like string<->float, and all transcendental functions) are the places yourprogram produces different results when you port it.Irritating one: MS VC++ on Intel platforms generates different code forexp() depending on the optimization level. They often differ in the lastbit they compute. This wholly accounts for why Dragon's speech recognitionsoftware sometimes produces subtly (but very visibly!) different resultsdepending on how it was compiled. Before I got tossed into this pit, it wasassumed for a year to be either a -O bug or somebody fetching uninitializedstorage.that's-what-you-get-when-you-refuse-to-define-results-ly y'rs - tim
[8]ページ先頭