<div dir="ltr">Good catch. Adding and subtracting over and over relying on massive cancellation over and over is a recipe for floating point disaster! <div><br></div><div>That said, so is adding small things to a large thing over and over, you'll accumulate the rounding error from the addition of small numbers to the large base.<div><br></div><div>An even better fix would be then to track the base and the current accumulated total delta from the base and do a final addition at the end. Then you only ever add like sized step sizes together before adding them to the base. This would stage the additions such that you get another matissa sized window of possible accumulation.</div><div><br></div><div>Something like:</div><div><br></div><div>enumFromThen n m = go (n - m) n 0 where</div><div>  go !d !b !a = db `seq` db : go d b (a + d) where</div><div>    db = d + b</div><div><br></div><div>which probably beats Kahan in practice, Kahan-Babuška-Neumaier should be more stable still, and there are other techniques that go further into accuracy at the cost of significant performance.</div><div><br></div><div>But we don't need a general number summation algorithm. All the numbers except the base are the same, we have a final hammer available to us: just do multiplication of the delta by the number of steps and add it to the base. </div><div><br></div><div>That should be the most numerically stable thing possible, given that we are forced to do at least the first massive cancellation between the from and then steps by the API we have to meet, but I don't have benchmarks to say which technique wins in practice.</div><div><br></div><div><div>-Edward</div></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Aug 9, 2016 at 11:22 PM, Andrew Farmer <span dir="ltr"><<a href="mailto:xichekolas@gmail.com" target="_blank">xichekolas@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Noticed this today:<br>
<br>
ghci> let xs = [0.0,0.1 .. 86400.0] in maximum xs<br>
86400.0000005062<br>
<br>
enumFromThenTo is implemented by numericEnumFromThenTo:<br>
<br>
<a href="https://github.com/ghc/ghc/blob/a90085bd45239fffd65c01c24752a9bbcef346f1/libraries/base/GHC/Real.hs#L227" rel="noreferrer" target="_blank">https://github.com/ghc/ghc/<wbr>blob/<wbr>a90085bd45239fffd65c01c24752a9<wbr>bbcef346f1/libraries/base/GHC/<wbr>Real.hs#L227</a><br>
<br>
Which probably accumulates error in numericEnumFromThen with the (m+m-n):<br>
<br>
numericEnumFromThen n m = n `seq` m `seq` (n : numericEnumFromThen m (m+m-n))<br>
<br>
Why not define numericEnumFromThen as:<br>
<br>
numericEnumFromThen n m = let d = m - n in d `seq` go d n<br>
where go delta x = x `seq` (x : go delta (x + delta))<br>
<br>
(or with BangPatterns)<br>
<br>
numericEnumFromThen n m = go (m - n) n<br>
where go !delta !x = x : go delta (x + delta)<br>
<br>
Seems like we'd save a lot of subtractions by using the worker function.<br>
______________________________<wbr>_________________<br>
ghc-devs mailing list<br>
<a href="mailto:ghc-devs@haskell.org">ghc-devs@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-<wbr>bin/mailman/listinfo/ghc-devs</a><br>
</blockquote></div><br></div>