About big integers in Lua 5.3.

classic Classic list List threaded Threaded
29 messages Options
12
Reply | Threaded
Open this post in threaded view
|

About big integers in Lua 5.3.

Xpol Wan
Hi,

When writing a big integer bigger than INT64_MAX, lua 5.3 not correctly parsed:


Lua 5.3.1  Copyright (C) 1994-2015 Lua.org, PUC-Rio

> print(9223372036854775808)

-9223372036854775808


Is this a bug or limitation?

Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Dirk Laurie-2
2016-01-13 5:14 GMT+02:00 Xpol Wan <[hidden email]>:

> When writing a big integer bigger than INT64_MAX, lua 5.3 not correctly
> parsed:
>
> Lua 5.3.1  Copyright (C) 1994-2015 Lua.org, PUC-Rio
>> print(9223372036854775808)
> -9223372036854775808
>
> Is this a bug or limitation?

Neither. It is in fact correct, provided that you understand
twos complement notation.

> math.maxinteger+1
-9223372036854775808
> string.format("%x",math.maxinteger+1)
8000000000000000

Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

David Given
On 13/01/16 05:00, Dirk Laurie wrote:
[...]
> Neither. It is in fact correct, provided that you understand
> twos complement notation.

If the value won't fit in an int64, shouldn't it be parsed as a double?

--
┌─── dg@cowlark.com ───── http://www.cowlark.com ─────
│ "There is nothing in the world so dangerous --- and I mean *nothing*
│ --- as a children's story that happens to be true." --- Master Li Kao,
│ _The Bridge of Birds_


signature.asc (845 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Coda Highland
On Wed, Jan 13, 2016 at 12:11 PM, David Given <[hidden email]> wrote:
> On 13/01/16 05:00, Dirk Laurie wrote:
> [...]
>> Neither. It is in fact correct, provided that you understand
>> twos complement notation.
>
> If the value won't fit in an int64, shouldn't it be parsed as a double?

We've been over THAT debate more than once. The basic conclusion is
"if you want a double, it's easy enough to get one; we're going to do
the thing that minimizes data loss."

/s/ Adam

Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Tom Sutcliffe
> On 13 Jan 2016, at 9:27 pm, Coda Highland <[hidden email]> wrote:
>
> We've been over THAT debate more than once. The basic conclusion is
> "if you want a double, it's easy enough to get one; we're going to do
> the thing that minimizes data loss."

In particular, from http://www.lua.org/manual/5.3/manual.html#8
"The main difference between Lua 5.2 and Lua 5.3 is the introduction of an integer subtype for numbers. Although this change should not affect "normal" computations, some computations (mainly those that involve some kind of overflow) can give different results."

and also in 3.4.3
"The conversion from strings to numbers goes as follows: First, the string is converted to an integer or a float, following its syntax and the rules of the Lua lexer. (The string may have also leading and trailing spaces and a sign.) Then, the resulting number (float or integer) is converted to the type (float or integer) required by the context (e.g., the operation that forced the conversion)."

The key bit there is "following its syntax and the rules of the Lua lexer". Which say something like that if it looks like an integer (and doesn't have a decimal point), it gets parsed as a lua_Integer.

Regards,

Tom


Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Chris Berardi-2
In reply to this post by David Given

> On Jan 13, 2016, at 3:11 PM, David Given <[hidden email]> wrote:
>
>> On 13/01/16 05:00, Dirk Laurie wrote:
>> [...]
>> Neither. It is in fact correct, provided that you understand
>> twos complement notation.
>
> If the value won't fit in an int64, shouldn't it be parsed as a double?

I don't think that would work since a double can only precisely represent integers up to 2^53.
Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Roberto Ierusalimschy
>
> > On Jan 13, 2016, at 3:11 PM, David Given <[hidden email]> wrote:
> >
> >> On 13/01/16 05:00, Dirk Laurie wrote:
> >> [...]
> >> Neither. It is in fact correct, provided that you understand
> >> twos complement notation.
> >
> > If the value won't fit in an int64, shouldn't it be parsed as a double?
>
> I don't think that would work since a double can only precisely represent integers up to 2^53.

Maybe it could parse as "Inf"?

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Coda Highland
On Thu, Jan 14, 2016 at 5:59 AM, Roberto Ierusalimschy
<[hidden email]> wrote:

>>
>> > On Jan 13, 2016, at 3:11 PM, David Given <[hidden email]> wrote:
>> >
>> >> On 13/01/16 05:00, Dirk Laurie wrote:
>> >> [...]
>> >> Neither. It is in fact correct, provided that you understand
>> >> twos complement notation.
>> >
>> > If the value won't fit in an int64, shouldn't it be parsed as a double?
>>
>> I don't think that would work since a double can only precisely represent integers up to 2^53.
>
> Maybe it could parse as "Inf"?
>
> -- Roberto
>

Inf feels worse than just losing the low-order bits of the value. It
would have to be an extremely large value that's somehow posing as an
int (at least 308 digits long) to not even be able to fit in a double.

/s/ Adam

Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Roberto Ierusalimschy
> Inf feels worse than just losing the low-order bits of the value. It
> would have to be an extremely large value that's somehow posing as an
> int (at least 308 digits long) to not even be able to fit in a double.

Inf means the value is larger than what we can represent correctly.

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Dirk Laurie-2
In reply to this post by Roberto Ierusalimschy
2016-01-14 15:59 GMT+02:00 Roberto Ierusalimschy <[hidden email]>:

>>
>> > On Jan 13, 2016, at 3:11 PM, David Given <[hidden email]> wrote:
>> >
>> >> On 13/01/16 05:00, Dirk Laurie wrote:
>> >> [...]
>> >> Neither. It is in fact correct, provided that you understand
>> >> twos complement notation.
>> >
>> > If the value won't fit in an int64, shouldn't it be parsed as a double?
>>
>> I don't think that would work since a double can only precisely represent integers up to 2^53.
>
> Maybe it could parse as "Inf"?

What about parsing it as a string? Lossless. Will cause an error
if compared to a number. Error in arithmetic depends on whether
Lua was compiled with coercion on or off.

Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Sean Conner
It was thus said that the Great Dirk Laurie once stated:

> 2016-01-14 15:59 GMT+02:00 Roberto Ierusalimschy <[hidden email]>:
> >>
> >> > On Jan 13, 2016, at 3:11 PM, David Given <[hidden email]> wrote:
> >> >
> >> >> On 13/01/16 05:00, Dirk Laurie wrote:
> >> >> [...]
> >> >> Neither. It is in fact correct, provided that you understand
> >> >> twos complement notation.
> >> >
> >> > If the value won't fit in an int64, shouldn't it be parsed as a double?
> >>
> >> I don't think that would work since a double can only precisely represent integers up to 2^53.
> >
> > Maybe it could parse as "Inf"?
>
> What about parsing it as a string? Lossless. Will cause an error
> if compared to a number. Error in arithmetic depends on whether
> Lua was compiled with coercion on or off.

  There are a number of ways to handle it (convert to double, current
behavior, return nil, throw an error) and some ways are better in some
contexts than others, so I don't think there's one good way to deal with
this.

  -spc (Just my 18446744073709551615 zorkmids)


Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Chris Berardi-2

> On Jan 14, 2016, at 2:12 PM, Sean Conner <[hidden email]> wrote:
>
> It was thus said that the Great Dirk Laurie once stated:
>> 2016-01-14 15:59 GMT+02:00 Roberto Ierusalimschy <[hidden email]>:
>>>>
>>>>>> On Jan 13, 2016, at 3:11 PM, David Given <[hidden email]> wrote:
>>>>>>
>>>>>> On 13/01/16 05:00, Dirk Laurie wrote:
>>>>>> [...]
>>>>>> Neither. It is in fact correct, provided that you understand
>>>>>> twos complement notation.
>>>>>
>>>>> If the value won't fit in an int64, shouldn't it be parsed as a double?
>>>>
>>>> I don't think that would work since a double can only precisely represent integers up to 2^53.
>>>
>>> Maybe it could parse as "Inf"?
>>
>> What about parsing it as a string? Lossless. Will cause an error
>> if compared to a number. Error in arithmetic depends on whether
>> Lua was compiled with coercion on or off.
>
>  There are a number of ways to handle it (convert to double, current
> behavior, return nil, throw an error) and some ways are better in some
> contexts than others, so I don't think there's one good way to deal with
> this.

I'd be tempted to upgrade the number to some sort of arbitrary precision big number (a third number sub-type?) when it overflows an int or float.
Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Tom N Harris
On Thursday, January 14, 2016 03:00:14 PM Chris Berardi wrote:
> I'd be tempted to upgrade the number to some sort of arbitrary precision big
> number (a third number sub-type?) when it overflows an int or float.

This is getting silly.

What if I meant for the number to be an integer with overflow? If the parser is
trying to guess my intent of whether the value should be an integer, float, or
error then what do I do if it guesses wrong? When the assumption is error then
every time I want to guarantee a non-error value will have to be written
carefully. When the assumption is float then how do I force integer overflow or
flag loss of precision? The assumption of integer I think is safest because I
can force a float by adding ".0".

To show some practical examples instead of speaking in vague abstractions, I
expect the issue will arise when writing number constants in hex. You can have
the surprise behavior of 9223372036854775808 being less than
9223372036854775807, or the surprise of 9223372036854775808 not being equal to
0x80000000000000000000. Programmers working with natural numbers would be
annoyed by the former, while programmers working with binary data would be
annoyed by the later.

While making sure that for any number N, N+1 > N makes sense to mathematicians
that's not how the underlying representation works and ultimately Lua operates
on number representations, not number theory. We're all familiar with
0.1+0.1+0.1 not being equal to 0.3. Lua doesn't hide the imprecision of floats,
nor do I think it should hide the overflow of integers.

--
tom <[hidden email]>

Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Coda Highland
On Thu, Jan 14, 2016 at 12:39 PM, Tom N Harris <[hidden email]> wrote:

> On Thursday, January 14, 2016 03:00:14 PM Chris Berardi wrote:
>> I'd be tempted to upgrade the number to some sort of arbitrary precision big
>> number (a third number sub-type?) when it overflows an int or float.
>
> This is getting silly.
>
> What if I meant for the number to be an integer with overflow? If the parser is
> trying to guess my intent of whether the value should be an integer, float, or
> error then what do I do if it guesses wrong? When the assumption is error then
> every time I want to guarantee a non-error value will have to be written
> carefully. When the assumption is float then how do I force integer overflow or
> flag loss of precision? The assumption of integer I think is safest because I
> can force a float by adding ".0".
>
> To show some practical examples instead of speaking in vague abstractions, I
> expect the issue will arise when writing number constants in hex. You can have
> the surprise behavior of 9223372036854775808 being less than
> 9223372036854775807, or the surprise of 9223372036854775808 not being equal to
> 0x80000000000000000000. Programmers working with natural numbers would be
> annoyed by the former, while programmers working with binary data would be
> annoyed by the later.
>
> While making sure that for any number N, N+1 > N makes sense to mathematicians
> that's not how the underlying representation works and ultimately Lua operates
> on number representations, not number theory. We're all familiar with
> 0.1+0.1+0.1 not being equal to 0.3. Lua doesn't hide the imprecision of floats,
> nor do I think it should hide the overflow of integers.
>
> --
> tom <[hidden email]>
>

+1. This is exactly my opinion on the matter. If I'm working with a
64-bit integer, and I KNOW I'm working with a 64-bit integer, then
give me a 64-bit integer; I'm aware enough of the circumstances to be
able to deal with the implications, and at the very least I can
reconstruct the original positive number from the negative one because
there hasn't been any actual data loss.

/s/ Adam

Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

aryajur


+1. This is exactly my opinion on the matter. If I'm working with a
64-bit integer, and I KNOW I'm working with a 64-bit integer, then
give me a 64-bit integer; I'm aware enough of the circumstances to be
able to deal with the implications, and at the very least I can
reconstruct the original positive number from the negative one because
there hasn't been any actual data loss.

/s/ Adam

I would have liked having inf for integers to make it consistent with the behavior with floats since they both are supposed to be "number" types. For me this detail that a number type may or may not overflow seems inconsistent, probably they should be 2 separate types like in C so that anyone using them are more directly aware of their data type. Although math.type does give that information but that's a level down
Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Dirk Laurie-2
In reply to this post by Tom N Harris
2016-01-14 22:39 GMT+02:00 Tom N Harris <[hidden email]>:
> While making sure that for any number N, N+1 > N makes sense to
> mathematicians that's not how the underlying representation works
> and ultimately Lua operates on number representations, not number
> theory.

Well, actually all that switching transparently from integer to float
would achieve is to make sure that for any number N, N+1 >= N,
and while that might sense to mathematicians (they're good at
redefining "makes sense") I can't see them thinking it's a useful
thing to achieve.

> Lua doesn't hide the imprecision of floats, nor do I think it should
> hide the overflow of integers.

I grew up in a time when integer overflow caused a program to
crash unless you had explicitly set a CPU flag that would make
it wrap around. Don't modern machines have such a flag, only
by default it is off? And if so, is the feature accessible from C?

Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Dirk Laurie-2
In reply to this post by Coda Highland
2016-01-14 22:46 GMT+02:00 Coda Highland <[hidden email]>:

> This is exactly my opinion on the matter. If I'm working with a
> 64-bit integer, and I KNOW I'm working with a 64-bit integer, then
> give me a 64-bit integer; I'm aware enough of the circumstances to be
> able to deal with the implications, and at the very least I can
> reconstruct the original positive number from the negative one because
> there hasn't been any actual data loss.

Basically I agree with you. Here is a non-technical example of basically
the same point.

People are by and large quite happy with "one o'clock" being later
than "twelve o'clock". That is to say, if the only numbers at your
disposal are 1 2 3 4 5 6 7 8 9 10 11 12, and you use them over
and over, people adapt to it easily. Context and usage make it
obvious what is meant.

It's not conceptually different when you get to integers. As long as
you know where they tick over, you can adapt.

Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Dirk Laurie-2
In reply to this post by aryajur
2016-01-15 3:45 GMT+02:00 Milind Gupta <[hidden email]>:

> I would have liked having inf for integers to make it consistent with the
> behavior with floats

When I was about seven years old, the big argument on the
playground among the more mathematically minded kids was
what the largest number was that you could think of. After
"billion" was shot down ("billion and one") inevitably we came
to "uncountable", for which the trick does not work.

Somehow "inf for integers" reminds me very strongly of
"uncountable".

Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Sean Conner
In reply to this post by Dirk Laurie-2
It was thus said that the Great Dirk Laurie once stated:
> 2016-01-14 22:39 GMT+02:00 Tom N Harris <[hidden email]>:
> > Lua doesn't hide the imprecision of floats, nor do I think it should
> > hide the overflow of integers.
>
> I grew up in a time when integer overflow caused a program to
> crash unless you had explicitly set a CPU flag that would make
> it wrap around. Don't modern machines have such a flag, only
> by default it is off? And if so, is the feature accessible from C?

  The only architecture I know of [1] that can do that is the VAX
architecture [2].  The MIPS can trap overflow, but it requires the use of
separate instructions (ADD instead of ADDU that every C compiler seems to
use).  Such features aren't necessarily accesible from C in a portable
manner, although compilers might support options to enable/disable such
actions.

  I did some microbenchmarks on this [3] and it doesn't seem to add that
much overhead on modern machines [4].

  -spc

[1] I'm not saying it's the only one, just that it's the only one I know
        of.

[2] Sweet system and the most regular and orthogonal CISC architecture
        I've come across.

[3] http://boston.conman.org/2015/09/07.1

[4] Intel.

Reply | Threaded
Open this post in threaded view
|

Re: About big integers in Lua 5.3.

Jorge Visca
In reply to this post by Roberto Ierusalimschy
On 14/01/16 14:11, Roberto Ierusalimschy wrote:
>> Inf feels worse than just losing the low-order bits of the value. It
>> would have to be an extremely large value that's somehow posing as an
>> int (at least 308 digits long) to not even be able to fit in a double.
> Inf means the value is larger than what we can represent correctly.
>
> -- Roberto

Yeah, that seems right from the basic user's point of view. A basic user
only knows "number", double or int being something that happens inside
the VM and mostly does the "right thing". Having sometimes inf and
sometimes overflow is leaking detail the user might not want to know.
For most people 2 and 2.0 are the same number.

Other approach is to think how you explain away to a final user some of
the usual float weirdness (like the mentioned 0.1+0.1...): you say
something like "you know, computers work like this", and then mention
something about periodic numbers and finite memory, and the user is
happy because he learned something about computers. Now, if he asks "why
this sometimes gives infinity, and sometimes some random negative
number?", and you explain it, he will say "you mean i have to always
remember to type .0 after each number?" and will roll his eyes.

Jorge

12