Unexpected calculation result with Lua53

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

Unexpected calculation result with Lua53

Tony Papadimitriou
I noticed a problem (which I suspect is related to the introduction of integers in Lua53), and I’d like to know if this is ‘official’ behavior, or some sort of bug.  The behavior can be seen in this small example:
 
function fact(n)
  if n == 0 then return 1 end
  return fact(n-1) * n
end
 
print(fact(66),fact(66.))
 
Using fp parameter, return correct (?) result
Using integer parameter, return 0 (zero) result!!!!
 
I don’t know what the root of this problem but if it happens to be related to integer overflow, should it be converted to floating point, and continue ‘crunching’ rather than give a completely wrong result?
 
Thanks.
Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Enrico Colombini
On 02-May-15 22:13, [hidden email] wrote:
> function fact(n)
>    if n == 0 then return 1 end
>    return fact(n-1) * n
> end
>
> print(fact(66),fact(66.))
>
> Using fp parameter, return correct (?) result
> Using integer parameter, return 0 (zero) result!!!!

This can be simplified to:

 > -9223372036854775808 * 65
-9223372036854775808

 > -9223372036854775808 * 66
0

 > -9223372036854775808 * 67
-9223372036854775808

 > -9223372036854775808 * 68
0

I am by no means expert of the new int/fp dualism, so I do not try to
explain the above alternance, but I note that the integer maxed out:

 > string.format("%x", -9223372036854775808)
8000000000000000

You can also get signed integer wrap:

 > fact(60)
-8718968878589280256

The last result that can be contained in a 64-bit integer seems to be
fact(20):

 > fact(20.0) < 2^64
true

 > fact(21.0) < 2^64
false

--
   Enrico

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Roberto Ierusalimschy
In reply to this post by Tony Papadimitriou
> I noticed a problem (which I suspect is related to the introduction of integers in Lua53), and I’d like to know if this is ‘official’ behavior, or some sort of bug.  The behavior can be seen in this small example:
>
> function fact(n)
>   if n == 0 then return 1 end
>   return fact(n-1) * n
> end
>
> print(fact(66),fact(66.))
>
> Using fp parameter, return correct (?) result
> Using integer parameter, return 0 (zero) result!!!!
>
> I don’t know what the root of this problem but if it happens to be related to integer overflow, should it be converted to floating point, and continue ‘crunching’ rather than give a completely wrong result?

Integer arithmetic uses "wrap around" for overflows, so the 0 result.

Convert an overflow result to floating point seems tempting, but
we do not see it as a useful/practical option. First, it is quite
expensive to check multiplication overflows in ANSI C. Second, if you
are computing with integers, you probably need a correct result, not a
rough aproximation.

Raising an error would be a better option than converting to float, but
again it is expensive; the wrap around behavior, besides being cheap,
has practical uses (e.g., unsigned arithmetic).

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

aryajur

Convert an overflow result to floating point seems tempting, but
we do not see it as a useful/practical option. First, it is quite
expensive to check multiplication overflows in ANSI C. Second, if you
are computing with integers, you probably need a correct result, not a
rough aproximation.


I was wondering so does it mean we have to be careful when we use integer number and floating number into our programs? If that is the case wouldn't it be easier if integer type was defined separately allowing its usage explicitly when needed and thought out?

Milind

 

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Dirk Laurie-2
In reply to this post by Tony Papadimitriou
2015-05-02 22:13 GMT+02:00  <[hidden email]>:

> I noticed a problem (which I suspect is related to the introduction of
> integers in Lua53), and I’d like to know if this is ‘official’ behavior, or
> some sort of bug.  The behavior can be seen in this small example:
>
> function fact(n)
>   if n == 0 then return 1 end
>   return fact(n-1) * n
> end
>
> print(fact(66),fact(66.))
>
> Using fp parameter, return correct (?) result
> Using integer parameter, return 0 (zero) result!!!!
>
> I don’t know what the root of this problem but if it happens to be related
> to integer overflow, should it be converted to floating point, and continue
> ‘crunching’ rather than give a completely wrong result?

The mathematical number 66! would need 309 bits to represent
without loss, which is equally impossible in integer or floating-point
in Lua.

Since 66! is divisible by 2^n, where n=33+16+8+4+2+1 = 64, its last
64 bits are all zeros. So the result using integers is not "completely
wrong", it has 64 correct bits.

If you did the work in double precision, you would have got the exponent
right, and the mantissa nearly right (the last bit comes out wrong in IEEE
arithmetic), so it has 52 correct bits, but those are at the other end. Just
saying where the other end is uses up 10 bits.

Moral of the story: if bits at the high-order end are important to you, use
floating-point. If bits at the low-order end are important, use integers.
Lua 5.3 gives you that choice (just change 1 to 1. on the second line),
Lua 5.2 did not.

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Dirk Laurie-2
In reply to this post by aryajur
2015-05-03 3:14 GMT+02:00 Milind Gupta <[hidden email]>:

>>
>> Convert an overflow result to floating point seems tempting, but
>> we do not see it as a useful/practical option. First, it is quite
>> expensive to check multiplication overflows in ANSI C. Second, if you
>> are computing with integers, you probably need a correct result, not a
>> rough aproximation.
>>
>
> I was wondering so does it mean we have to be careful when we use integer
> number and floating number into our programs? If that is the case wouldn't
> it be easier if integer type was defined separately allowing its usage
> explicitly when needed and thought out?

You always have to be careful when using computer arithmetic
instead of exact arithmetic. It is true that the results of integer
overflow tend to to be very dramatic, for example causing a rocket
destined for space to reverse direction and crash [1], but the
results of naive reliance on floating point can be no less disastrous,
for example causing an anti-missile system to fail [2].

In the first case, US$370 million, in the second 28 lives, were lost
because programmers did not understand computer arithmetic
properly.

In both cases, integer and float, usage should be "thought out".
Anything that contributes to a false sense of security just makes
it harder to find bugs already at the design stage. I guess that
one in every 100 programmers does the kind of work for which
the distinction between integer and float is so important that the
"type" function should be overridden [3]. For the sake of the
other 99, this is not standard in Lua, but that one programmer
had better do it.

[1]   http://en.wikipedia.org/wiki/Cluster_(spacecraft)
[2]   http://en.wikipedia.org/wiki/MIM-104_Patriot#Failure_at_Dhahran
[3]   I.e. every program should start with the following lines:

local default_type = type
type = function(x)
   local T=default_type(x)
   if T=="number" then T=math.type(x) end
   return T
end

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Jonathan Goble
On Sun, May 3, 2015 at 1:12 AM, Dirk Laurie <[hidden email]> wrote:
> local default_type = type
> type = function(x)
>    local T=default_type(x)
>    if T=="number" then T=math.type(x) end
>    return T
> end

According to the manual, math.type(x) returns nil if x is not a
number. So I think you could shorten that code to this:

local default_type = type
type = function (x)
    return math.type(x) or default_type(x)
end

In addition, code that needs this behavior is probably going to call
type() on numbers far more often than any other type, so you gain
efficiency by calling the more common case first, and by not having to
create a local variable or perform a string equality test.

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Rena
In reply to this post by Dirk Laurie-2
On Sun, May 3, 2015 at 1:12 AM, Dirk Laurie <[hidden email]> wrote:

> 2015-05-03 3:14 GMT+02:00 Milind Gupta <[hidden email]>:
>>>
>>> Convert an overflow result to floating point seems tempting, but
>>> we do not see it as a useful/practical option. First, it is quite
>>> expensive to check multiplication overflows in ANSI C. Second, if you
>>> are computing with integers, you probably need a correct result, not a
>>> rough aproximation.
>>>
>>
>> I was wondering so does it mean we have to be careful when we use integer
>> number and floating number into our programs? If that is the case wouldn't
>> it be easier if integer type was defined separately allowing its usage
>> explicitly when needed and thought out?
>
> You always have to be careful when using computer arithmetic
> instead of exact arithmetic. It is true that the results of integer
> overflow tend to to be very dramatic, for example causing a rocket
> destined for space to reverse direction and crash [1], but the
> results of naive reliance on floating point can be no less disastrous,
> for example causing an anti-missile system to fail [2].
>
> In the first case, US$370 million, in the second 28 lives, were lost
> because programmers did not understand computer arithmetic
> properly.
>
> In both cases, integer and float, usage should be "thought out".
> Anything that contributes to a false sense of security just makes
> it harder to find bugs already at the design stage. I guess that
> one in every 100 programmers does the kind of work for which
> the distinction between integer and float is so important that the
> "type" function should be overridden [3]. For the sake of the
> other 99, this is not standard in Lua, but that one programmer
> had better do it.
>
> [1]   http://en.wikipedia.org/wiki/Cluster_(spacecraft)
> [2]   http://en.wikipedia.org/wiki/MIM-104_Patriot#Failure_at_Dhahran
> [3]   I.e. every program should start with the following lines:
>
> local default_type = type
> type = function(x)
>    local T=default_type(x)
>    if T=="number" then T=math.type(x) end
>    return T
> end
>

I think Lua is not certified for use in rockets... :-) (but your point
still stands)

--
Sent from my Game Boy.

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

aryajur
In reply to this post by Dirk Laurie-2


On Sat, May 2, 2015 at 10:12 PM, Dirk Laurie <[hidden email]> wrote:
2015-05-03 3:14 GMT+02:00 Milind Gupta <[hidden email]>:
>>
>> Convert an overflow result to floating point seems tempting, but
>> we do not see it as a useful/practical option. First, it is quite
>> expensive to check multiplication overflows in ANSI C. Second, if you
>> are computing with integers, you probably need a correct result, not a
>> rough aproximation.
>>
>
> I was wondering so does it mean we have to be careful when we use integer
> number and floating number into our programs? If that is the case wouldn't
> it be easier if integer type was defined separately allowing its usage
> explicitly when needed and thought out?

You always have to be careful when using computer arithmetic
instead of exact arithmetic. It is true that the results of integer
overflow tend to to be very dramatic, for example causing a rocket
destined for space to reverse direction and crash [1], but the
results of naive reliance on floating point can be no less disastrous,
for example causing an anti-missile system to fail [2].

In the first case, US$370 million, in the second 28 lives, were lost
because programmers did not understand computer arithmetic
properly.

In both cases, integer and float, usage should be "thought out".
Anything that contributes to a false sense of security just makes
it harder to find bugs already at the design stage. I guess that
one in every 100 programmers does the kind of work for which
the distinction between integer and float is so important that the
"type" function should be overridden [3]. For the sake of the
other 99, this is not standard in Lua, but that one programmer
had better do it.

[1]   http://en.wikipedia.org/wiki/Cluster_(spacecraft)
[2]   http://en.wikipedia.org/wiki/MIM-104_Patriot#Failure_at_Dhahran
[3]   I.e. every program should start with the following lines:

local default_type = type
type = function(x)
   local T=default_type(x)
   if T=="number" then T=math.type(x) end
   return T
end

Thank you for explaining. It just seems that people or new comers who are developing apps that are not as critical as you refer would expect the behavior to revert to float when there is no explicit type system defined for the number type. Adding a floating point makes Lua understand and distinguish but hard for new comers, especially people who are not professional programmers and would not read the suttle points of the internal integer and float handling. 
         So to make these suttle behavior come out it may have been good to have the integer type.
Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Enrico Colombini
In reply to this post by Dirk Laurie-2
On 03-May-15 06:39, Dirk Laurie wrote:
> Since 66! is divisible by 2^n, where n=33+16+8+4+2+1 = 64, its last
> 64 bits are all zeros

Thanks, I missed that point (and I mistakenly assumed fact() would
behave like my odd/even examples, while in fact it stays 0 beyond 66, as
expected).

--
   Enrico

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Enrico Colombini
In reply to this post by Dirk Laurie-2
On 03-May-15 07:12, Dirk Laurie wrote:
> It is true that the results of integer
> overflow tend to to be very dramatic, for example causing a rocket
> destined for space to reverse direction and crash [1]

And, just the other day:
http://www.engadget.com/2015/05/01/boeing-787-dreamliner-software-bug/

--
   Enrico

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Andrew Starks
In reply to this post by aryajur


On Saturday, May 2, 2015, Milind Gupta <[hidden email]> wrote:

Convert an overflow result to floating point seems tempting, but
we do not see it as a useful/practical option. First, it is quite
expensive to check multiplication overflows in ANSI C. Second, if you
are computing with integers, you probably need a correct result, not a
rough aproximation.


I was wondering so does it mean we have to be careful when we use integer number and floating number into our programs? If that is the case wouldn't it be easier if integer type was defined separately allowing its usage explicitly when needed and thought out?

Milind

 


Do you mean something stronger than math.type?

It almost never matters, so the provided approach seems reasonable, I think. 
Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Luiz Henrique de Figueiredo
In reply to this post by Tony Papadimitriou
> print(fact(66),fact(66.))
>
> Using fp parameter, return correct (?) result
> Using integer parameter, return 0 (zero) result!!!!

This will happen in C as well. So, why it is surprising?

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Jay Carlson

>> print(fact(66),fact(66.))
>>
>> Using fp parameter, return correct (?) result
>> Using integer parameter, return 0 (zero) result!!!!
>
> This will happen in C as well. So, why it is surprising?

Well, this *may* happen in C. :-)



Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Tony Papadimitriou
In reply to this post by Luiz Henrique de Figueiredo
(This is meant as a general reply to all responses so far, not only to
yours.)

Yes, and it will happen in many other languages, also.  What's your point?
In C, Pascal, and most traditional non-interpreted languages, you decide
what types the parameters will be, and if you pass the wrong thing, the
compiler will complain.

(BTW, it won't happen in previous Lua versions.  So, since you asked, that's
enough of a reason for it to be surprising.)

Unfortunately several responses are saying pretty much this: "that's how
integer math works, deal with it".  Well, anybody who's been in computing
long enough is aware of all that trivia.

Let me ask you this: Is Lua's audience computer scientists?  If yes, then we
can stop the discussion here.

The real problem then is not my assumed misconception about how integer math
works but how Lua opts to use integers when float 'should obviously' be the
better choice.

And it also seems to somehow contradict this statement (3.4.3 – Coercions
and Conversions) although I know it does not refer to this issue -- but it
is related conceptually:

"Lua provides some automatic conversions between some types and
representations at run time. Bitwise operators always convert float operands
to integers. Exponentiation and float division always convert integer
operands to floats.  *** All other arithmetic operations applied to mixed
numbers (integers and floats) convert the integer operand to a float; this
is called the usual rule. ***"
(My emphasis)

So, float is the 'usual rule' but apparently not when passing numbers to
functions, which I would consider similar to mixing integers and floats
since the caller does not necessarily know what the called function expects
(integer or float), and the reverse, the function *cannot* possibly predict
what the user will pass in (an integer or a float).

As to the response about needing "a correct result instead of a rough
approximation" when using integers, from a purely theoretical point of view
I might agree totally, but from a practical point of view, how in the world
can a zero answer be considered more accurate than even a rough
approximation that's a lot-lot-lot-lot closer to the real answer, is beyond
me.

(One 'cute' response claimed that zero is not "completely wrong" but
partially wrong -- and, therefore, partially correct -- because the true
result has all zeros is the least significant portion of the result that can
fit in the available size integer.  Well, yes, if you go that route, we
could also accept a 0 or 1 as partially correct if we lower our tolerance to
one bit, as all numbers in binary will end with either zero or one!  There
you have it: correctness ... to one bit.)

Anyway, a simple function that worked for Lua 5.2 and before now has to be
augmented with code like:
n = n + 0.0
on entry to convert the n parameter to float, just in case the caller didn't
think about passing a float when switching from Lua52 to Lua53, for example.
Or, simply, because the users are not so computer savvy to even know the
exact implications of their choice, or even that adding a single dot to a
constant or + 0.0 to a variable is actually meant to make a difference on
the calculations, and so on.

In my view, if there should be a needed change in existing code (in respect
with this issue) it should be only in the opposite direction.  That is, if I
want to enforce an integer (a new thing in Lua53), use something like: n = n
// 1 on entry to the function.  That would keep it compatible with previous
versions, and also prevent 'surprises' that code that worked suddenly
stopped working, without any errors, but incredibly, with very 'wrong' (OK,
OK, ... 'unexpected' yet not 'surprising' from a computer science viewpoint)
results.

Oh well, I guess it all comes down to personal design preferences, and since
I'm on the user side, I can only get what I'm served! :)  And, I'm really
grateful, of course (even if I complain).

I suppose then, the only real solution that would possibly keep all of us
pleased would be the introduction of infinite precision integer arithmetic,
like in Python.

Thanks to all for your interesting (and to some, for their amusing)
responses.

-----Original Message-----
From: Luiz Henrique de Figueiredo
Sent: Sunday, May 03, 2015 10:55 PM
To: Lua mailing list
Subject: Re: Unexpected calculation result with Lua53

> print(fact(66),fact(66.))
>
> Using fp parameter, return correct (?) result
> Using integer parameter, return 0 (zero) result!!!!

This will happen in C as well. So, why it is surprising?


Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Tim Hill

On May 3, 2015, at 5:20 PM, <[hidden email]> <[hidden email]> wrote:

As to the response about needing "a correct result instead of a rough approximation" when using integers, from a purely theoretical point of view I might agree totally, but from a practical point of view, how in the world can a zero answer be considered more accurate than even a rough approximation that's a lot-lot-lot-lot closer to the real answer, is beyond me.

But is it really so bad? I agree with your point about a less sophisticated user being puzzled when a 64-bit integer wraps, but is it better to silently coerce to a float? A silent coercion also causes nasty things to happen; that nice factorial algorithm still generates incorrect results (as a result of FP precision), but now instead of the results being wildly wrong they are slightly wrong. Both are wrong, but which is more likely to go unnoticed?

—Tim

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Dirk Laurie-2
In reply to this post by Tony Papadimitriou
2015-05-04 2:20 GMT+02:00  <[hidden email]>:

> The real problem then is not my assumed misconception about how
> integer math works but how Lua opts to use integers when float
> 'should obviously' be the better choice.

You presumably use "assumed misconception" in the sense of
"pretended misconception", since you quite clearly know how it works.

It is a bad idea to argue from a pretended position on Lua-L. We're
a bunch of Sheldons somewhere on the Asperger syndrome spectrum
and can't handle that sort of thing.

Anyway, "should obviously" is a vague term depending strongly
on prejudice.

> As to the response about needing "a correct result instead of a rough
> approximation" when using integers, from a purely theoretical point of view
> I might agree totally, but from a practical point of view, how in the world
> can a zero answer be considered more accurate than even a rough
> approximation that's a lot-lot-lot-lot closer to the real answer, is beyond
> me.

Lua 5.3, for better or words, has a syntactic convention that "1" is
an exact integer whereas "1." is a (by coincidence exact) approximation
to it. In  Lua 5.3, when approximations are preferred one should always
code "1.", and in a situation where exactness is needed, one should
always code "1". Even computer users who are not computer scientists
can surely be trained to do that. Heck, even some pure mathematicians
have been known to grasp this point.

> Anyway, a simple function that worked for Lua 5.2 and before now has to be
> augmented with code like:
> ...
> In my view, if there should be a needed change in existing code (in respect
> with this issue) it should be only in the opposite direction.

Every version of Lua has had breaking changes. There is no substitute
for reading the manual, and the matter is quite clearly explained there.

    "In case of overflows in integer arithmetic, all operations wrap
    around, according to the usual rules of two-complement arithmetic.
    (In other words, they return the unique representable integer that is
    equal modulo 2⁶⁴ to the mathematical result.)"

> Oh well, I guess it all comes down to personal design preferences, and since
> I'm on the user side, I can only get what I'm served! :)  And, I'm really
> grateful, of course (even if I complain).

Finally, something that we agree on.

> I suppose then, the only real solution that would possibly keep all of us
> pleased would be the introduction of infinite precision integer arithmetic,
> like in Python.

And another! While we're are it, what about infinite precision rational
arithmetic, like in Guile?

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Alex Queiroz
Hello,

On 4 May 2015 at 10:45, Dirk Laurie <[hidden email]> wrote:
>
> Lua 5.3, for better or words, has a syntactic convention that "1" is
> an exact integer whereas "1." is a (by coincidence exact) approximation
> to it. In  Lua 5.3, when approximations are preferred one should always
> code "1.", and in a situation where exactness is needed, one should
> always code "1". Even computer users who are not computer scientists
> can surely be trained to do that. Heck, even some pure mathematicians
> have been known to grasp this point.
>

Time for a quick Scheme REPL:

===============
11:38 $ gsi
Gambit v4.7.5

> (exact? 1)
#t
> (exact? 1.)
#f
===============

The different obviously being that Scheme exact numbers are unbounded.

Cheers,
--
-alex
http://unendli.ch/

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Roberto Ierusalimschy
In reply to this post by Dirk Laurie-2
I must confess I learned something new from this discution. From now
one, whenever I teach the factorial function in C, I will write it like
this:

double fact (double n) {
  double a = 1;
  while (n > 0) a *= n--;
  return a;
}

After all, it gives "better" results then the old-fashined version :-)

-- Roberto

Reply | Threaded
Open this post in threaded view
|

Re: Unexpected calculation result with Lua53

Jay Carlson
On May 4, 2015, at 11:56 AM, Roberto Ierusalimschy <[hidden email]> wrote:

> I must confess I learned something new from this discution. From now
> one, whenever I teach the factorial function in C, I will write it like
> this:
>
> double fact (double n) {
>  double a = 1;
>  while (n > 0) a *= n--;
>  return a;
> }
>
> After all, it gives "better" results then the old-fashioned version :-)

Down vs up is fun.

> n=1 for i = 1,80 do n = n * i end print(n) n1=n
7.1569457046264e+118
> n=1 for i = 80,1,-1 do n = n * i end print(n) n2=n
7.1569457046264e+118
> return n2-n1
1.7917957937422e+103

Only a few googols of difference....
12