• Subject: Re: [PATCH] Loop Overflow Bug Fix
• From: KHMan <keinhong@...>
• Date: Sat, 18 Nov 2017 18:44:36 +0800

```On 11/17/2017 10:38 PM, Coda Highland wrote:
```
```On Fri, Nov 17, 2017 at 5:58 AM, Hisham <h@hisham.hm> wrote:
```
```On 17 November 2017 at 04:38, Dirk Laurie <dirk.laurie@gmail.com> wrote:
```
```2017-11-17 0:26 GMT+02:00 Paige DePol <lual@serfnet.org>:
```
```Paige DePol <lual@serfnet.org> wrote

```
```In lvm.c:

#define forstepcheck(ns,ni,nl) \
(luai_numne(ns, luai_numsub(L, luai_numadd(L, ni, ns), ni)) || \
luai_numne(ns, luai_numsub(L, nl, luai_numsub(L, nl, ns))))

```
```
This worked... until it didn't. Floating point numbers are so strange!

3.2 == (1.0 + 3.2) - 1.0  [3.2]
3.2 == (16.0 + 3.2) - 16.0  [3.2]

Looks like that should pass the test... but it failed (sorry for the excessive width):

3.200000000000000177636 == (1.000000000000000000000 + 3.200000000000000177636) - 1.000000000000000000000  [3.200000000000000177636]
3.200000000000000177636 == (16.000000000000000000000 + 3.200000000000000177636) - 16.000000000000000000000  [3.199999999999999289457]
```
```
A for loop with floating-point increment, and what appears to be an
integer multiple of it as upper limit, is obscene code. In a numerical
analysis course, it is a standard example of what one should not do,
and a fix is taught. (It basically involves adding half the increment
to the upper limit.)

I know only one language that on a routine basis accepts that its
users may not know all that, and therefore provides a built-in fix for
the problem. I won't mention its name since it is a language that
people either love or hate. If the same idea is implemented in Lua, it
would involve two additional predefined constants math.abstol and
math.reltol. A floating-point loop 'for x in start,stop,inc' would be
equivalent to

do local x=start
while math.abs(x-stop) <= math.max(math.abstol,math.reltol*math.abs(x)) do
-- loop body
x = x+inc
end

The defaults are such that loops like "for x=1,5,0.1" give the
intuitively expected behaviour, but the user is permitted to change
either tolerance. Most commonly one would set one of them to 0, so
that the test simplifies to either relative or absolute tolerance.

I guess that the bottom line is that the VM instruction should right
at the start determine whether integer or floating-point arithmetic is
to be used, and that different algorithms coping with the different
problems (integer overflow, floating-point inexactness) should be
applied.
```
```
If one were to be true to Lua's original spirit as a scripting
language to be used by domain specialists in other fields, this would
be an excellent choice. But if we're considering an epsilon in for
loops, then I'd also expect the same tolerances to be taken into
account in equality comparisons of floating-point numbers.

The next question, then, would be "what are good default values for
math.abstol and math.reltol"?

-- Hisham

```
```
Absolute tolerance is numerical bupkis. No constant epsilon could ever
be meaningful across scales -- an epsilon that gives good behavior on
loops between 0 and 1 isn't going to give you good behavior on loops
between 1 and 1,000,000, and if you find a reasonable compromise there
then that epsilon is going to be unsuitable for a loop between 1e20
and 1e30.

[snip snip snip]

Better yet, screw the numerical methods.

As I said, the problem is that the rounding error is compounded each
time the addition takes place. But what if I told you there was a way
to run that loop without doing ANY floating-point additions?

Just convert the whole silly thing to integers: min=0,
max=(stop-start)/step+2^-50, increment=1. Each iteration, x = i *
step.
[snip snip snip]
```
```
I would do the same, most loops can be rewritten.

Fascinating discussion.

```
Let me just state for the record that I have no objection to the current Lua 5.3.x behaviour. Corner cases have to be handled; there are no beautiful solutions. So they are handled, but is it a good idea to start habitually relying on corner cases?
```
```
I would just steer well and truly clear of all things slippery. No fractions in loops. No mixed numbers. No out of range numbers. No numbers close to data type limits. Just loops with zero surprises.
```
--
Cheers,
Kein-Hong Man (esq.)
Selangor, Malaysia

```