Re: [PATCH] Loop Overflow Bug Fix

[Paige DePol <lual@...>]

Coda Highland <chighland@gmail.com> wrote:

> On Mon, Nov 20, 2017 at 4:03 PM, Paige DePol <lual@serfnet.org> wrote:
>> I would also like it if 2.5,3.0,0.1 actually iterated on 3.0, but that
>> sure seems to be quite the complex problem in general.
> 
> Well, I mean, I already explained a couple different ways to do that one. ;)

Oh yes, I know and I was going to take a deeper look at some of the ideas
you proposed, as well as others I have found in the links I posted, and
other places online. I hadn't done that yet as I was still reading about
floating points (and their quirks) while trying my hand at figuring out a
solution before looking deeper into existing solutions.

There appears to be a number of solutions, each of which has their pros and
cons. I just need to figure out which one I prefer and then implement it for
my flavor of Lua... and of course provide a patch for vanilla Lua for those
who may want it!


> One of the ways I quoted is numerically ideal: Computing the number of
> steps and then multiplying the iteration number by the step size is
> the most stable way to do it because it doesn't accumulate error.
> Unfortunately, it's also got more overhead because multiplication is
> so expensive relative to addition, but I imagine that it's not going
> to have a noticeable impact on most use cases.

I have read that floating point multiplications are more expensive, I
will have to run a benchmark to see just how expensive soon. I do like
the simplicity of this approach.


> There are a variety of techniques you can use to minimize or mitigate
> the rounding error even without using multiplication. Accumulating
> steps starting at 0 instead of at the lower bound is a good start
> because it means you're more likely to be adding numbers of similar
> magnitudes (you add the accumulator to the lower bound and set the
> loop variable to that). You could also compute the actual error in
> advance and use that to adjust the upper bound if it would miss.

Yes, I was playing with ULPs at one point, and that actually worked
for some cases, but it still was a fragile solution. 


> Obviously none of these techniques come without cost, but it actually
> IS a well-researched field and the solutions are understood.

I wasn't intimating it wasn't, or that there was no solution to the
problem... just that given the nature of floating point numbers the
issue itself can be complex depending on your requirements.

At least now I have a much better understanding of how floating point
numbers work and why they behave the way they do! Thank you for your
feedback and suggestions for techniques to solve the issue!

~Paige