Re: [9front] seq: fix infinite loop

[Amavect <amavect@gmail.com>]

On Sun, 15 Aug 2021 15:02:38 -0700
Sean Hinchee <henesy.dev@gmail.com> wrote:
>     ; seq 2e16 20000000000000002
> would loop forever.
At this range, 2e16 and 20000000000000002 are represented by the same
double floating point value.

> + if(val == max)
> + break;
We can cover more cases.
For example, your patch does not fix the following:
seq 9007199254740992 9007199254740996
The issue is with floating point precision.

A double has a 52 bit mantissa, meaning that it allows 2^52 different
values before the exponent is incremented (thus, floating point.)
A double has a 11 bit exponent, and 1 sign bit.
Exponents range from −1022 to +1023, with exponents −1023 and
+1024 reserved for special numbers.

At an exponent e, the mantissa represents a value between [2^e,2^(e+1)).
The precision is range/buckets, so we can calculate the precision.
At an exponent e and mantissa m, the precision is 2^(e-m)
(2^(e+1)-2^e)/2^m = 2^e/2^m = 2^(e-m)

Between [1, 2), the exponent is 0.
The precision is 2^(0-52) ≈ 0.0000000000000002220446
Between [2^52, 2^53), the exponent is 52.
The precision is 2^(52-52) = 1.

2e16 is between [2^54, 2^55), so the exponent is 54.
The precision is 2^(54-52) = 4.
Halfway ties round to the even bucket.

This is demonstrated by the following.

# infinite loop
seq 2e16 19999999999999998

# 2^53-1, halts
seq 9007199254740991 9007199254740991

# 2^53, infinite loop due to halfway tie rounding down to even bucket.
seq 9007199254740992 9007199254740992
# halts, halfway tie rounds up to even bucket, 9007199254740996
seq 9007199254740994 9007199254740994

# different due to rounding error in loss of precision
seq 5000000000000000 1.1 5000000000000002
seq 0 1.1 2


I don't believe that there is an ideal resolution to rounding error in
that last example (libmp would be too complex), but we can cover more
cases if we check that the previous val value is different from the
current val.
The correct thing to do is to throw an error warning about precision.

Thanks,
Amavect