StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>TL;DR: <strong>F# PowerPack's <code>BigRational</code> type is the way to go</strong>.</p> <hr> <h2>What's Wrong with Floating-point Loops</h2> <p>As many have pointed out, <code>float</code> values are not suitable for looping:</p> <ul> <li>They do have Round Off Error, just like with <code>1/3</code> in decimal, we inevitably lose all digits starting at a certain exponent;</li> <li>They do experience Catastrophic Cancellation (when subtracting two <em>almost</em> equal numbers, the result is rounded to zero);</li> <li>They always have non-zero <a href="http://en.wikipedia.org/wiki/Machine_epsilon">Machine epsilon</a>, so the error is <strong>increased</strong> with every math operation (unless we are adding different numbers many times so that errors mutually cancel out -- but this is not the case for the loops);</li> <li>They do have different accuracy across the range: the number of unique values in a range <code>[0.0000001 .. 0.0000002]</code> is equivalent to the number of unique values in <code>[1000000 .. 2000000]</code>;</li> </ul> <h2>Solution</h2> <p>What can instantly solve the above problems, is switching back to integer logic.</p> <p>With <a href="http://fsharppowerpack.codeplex.com/">F# PowerPack</a>, you may use <code>BigRational</code> type:</p> <pre><code>open Microsoft.FSharp.Math // [1 .. 1/3 .. 20] [1N .. 1N/3N .. 20N] |> List.map float |> List.iter (printf "%f; ") </code></pre> <p><strong>Note</strong>, I took my liberty to set the step to <code>1/3</code> because <code>0.5</code> from your question actually has an exact binary representation 0.1<sub>b</sub> and is represented as +1.00000000000000000000000 * 2<sup>-1</sup>; hence it does not produce any cumulative summation error.</p> <p>Outputs:</p> <blockquote> <p>1.000000; 1.333333; 1.666667; 2.000000; 2.333333; 2.666667; 3.000000; <strong>(skipped)</strong> 18.000000; 18.333333; 18.666667; 19.000000; 19.333333; 19.666667; 20.000000;</p> </blockquote> <pre><code>// [0.2 .. 0.1 .. 3] [1N/5N .. 1N/10N .. 3N] |> List.map float |> List.iter (printf "%f; ") </code></pre> <p>Outputs:</p> <blockquote> <p>0.200000; 0.300000; 0.400000; 0.500000; <strong>(skipped)</strong> 2.800000; 2.900000; 3.000000;</p> </blockquote> <h2>Conclusion</h2> <ul> <li><code>BigRational</code> uses integer computations, which are <em>not slower</em> than for floating-points;</li> <li>The round-off occurs only once for each value (upon conversion to a <code>float</code>, but not within the loop);</li> <li><code>BigRational</code> acts as if the machine epsilon were zero;</li> </ul> <p>There is an obvious limitation: you can't use irrational numbers like <code>pi</code> or <code>sqrt(2)</code> as they have no exact representation as a fraction. It does not seem to be a very big problem because usually, we are not looping over <em>both</em> rational and irrational numbers, e.g. <code>[1 .. pi/2 .. 42]</code>. If we do (like for geometry computations), there's usually a way to reduce the irrational part, e.g. switching from radians to degrees.</p> <hr> <p>Further reading:</p> <ul> <li><a href="http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html">What Every Computer Scientist Should Know About Floating-Point Arithmetic</a></li> <li><a href="http://tomasp.net/blog/powerpack-numeric.aspx">Numeric types in PowerPack</a></li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload