I am new to the Lua programming language, so my first program is a factorial function which I have implemented as follows
function fact(n)
if n <= 1 then return 1
else return n * fact(n-1)
end
end
the function works as intended for number less than 20, but once I go bigger the function starts to return negative numbers and 0
I searched the internet and I found that it has something to do with the size of floating number used by Lua which is 64bits, and I've been convinced till I saw this video
Does anyone have an explanation to this? does it have something to do with my installation of Lua or there is a config that I must do?
I'm using Lua 5.3
NOTE: I'm learning Lua to customize my experience in Neovim so I won't need all this calculations but I got curious about it
EDIT In the video, the fact(100) produces a number with e expression but on my system it just gives 0
Before Lua 5.3, Lua had 64-bit floats as its only number type (*). Floats use a mantissa-exponent representation. This allows them to represent very big numbers with a loss of precision. Very big or small floats are usually formatted using exponent notation (so something like 4.2e+42).
So on on Lua 5.2 and earlier, you're getting an inaccurate result from your calculation, since the 20!, or even 100! is much larger than the maximum integer a float can accurately represent (2^53), but can still be inaccurately represented.
Lua 5.3 introduced 64-bit signed integers (*). These overflow silently. Usually they use two's complement. This is what you're seeing here: Your program only uses integers. If you multiply two large integers and the result doesn't fit, it overflows and becomes negative. (The result is correct modulo 2^64, which is often desired).
Simple example: 0xFFFFFFFF*0xFFFFFFFF = -8589934591. 0xFFFFFFFF is much smaller than 64-bit, but square it and you get a number which doesn't fit. Lua could theoretically silently "upgrade" to floats in this case, but it doesn't, so float and integer arithmetic behave differently: Integer arithmetic overflows, float arithmetic becomes inaccurate (and may result in infinities for large enough numbers).
In your particular case, 100! contains at least 50 even factors (2, 4, ..., 100). If we look at the powers of two, we have 2, 4, 8, 16, 32, 64, 128. These contribute 0 + 1 + 2 + 3 + 4 + 5 + 6 additional two's in the product. So we have 100! = 2^(50 + 21) * c where c is some integer. Now what is 2^71 mod 2^64? 0. Hence why you're getting 0.
This is among the 5.2 / 5.3 incompatibilities: If you try to "just" upgrade, you get integer arithmetic where you had float arithmetic before (division is an exception). This can lead to issues such as this one. To be on the safe side, you could make all numbers floats (append .0). This would work in your program as well.
If you really want to accurately compute big fibonacci numbers, you will need a big integer library. Lua does not have one built in.
(*) custom builds of Lua (e.g. for embedded devices) may still use integers or 32-bit floats / 32-bit integers, but by default, you can expect Lua to use 64-bit numbers.