How to create Fibonacci sequence in Lua?

Question

I wrote a small script that creates Fibonacci sequence and returns a sum of all even integers.

function even_fibo()
  -- create Fibonacci sequence
  local fib = {1, 2}  -- starting with 1, 2
  for i=3, 10 do
    fib[i] = fib[i-2] + fib[i-1]
  end
  -- calculate sum of even numbers
  local fib_sum = 0
  for _, v in ipairs(fib) do
    if v%2 == 0 then
      fib_sum = fib_sum + v
    end
  end
  return fib_sum
end

fib = even_fibo()
print(fib)

The function creates the following sequence: 1, 2, 3, 5, 8, 13, 21, 34, 55

And returns the sum of its even numbers: 44

However, when I change the stop index from 10 to 100, in for i=3, 100 do the returned sum is negative -8573983172444283806 because the values become too big. Why is my code working for 10 and not for 100?

What version of lua are you running (`lua -v`)? – Turn Dec 18 '15 at 21:15 — Turn, Dec 18 '15 at 21:15
I run this script with Lua 5.3 – minerals Dec 18 '15 at 21:18 — minerals, Dec 18 '15 at 21:18

score 3 · Accepted Answer · answered Dec 18 '15 at 21:24

3

Prior to version 5.3, Lua always stored numbers internally as floats. In 5.3 Lua numbers can be stored internally as integers or floats. One option is to run Lua 5.2, I think you'll find your code works as expected there. The other option is to initialize your array with floats which will promote all operations on them in the future to floats:

local fib = {1.0, 2.0}

answered Dec 18 '15 at 21:24

Turn

6,656
32
41

1

This will not solve the OP's problem "to calculate the sum of even fib numbers", even approximately. Because when using floats, all numbers above 2^53 (that is, starting from `fib[78]`) are considered to be even. The result value `fib_sum` will be wrong anyway. – Egor Skriptunoff Dec 18 '15 at 21:51
Using floats in array `{1.0, 2.0}` I get `1.5005088278427e+21` – minerals Dec 18 '15 at 23:59

lhf · Answer 2 · 2015-12-19T10:02:20.857

Here is a hack written in hindsight. The code exploits the mathematical fact that the even Fibonacci numbers are exactly those at indices that are multiple of 3. This allows us to avoid testing the parity of very large numbers and provides high-order digits that are correct when you do the computation in floating-point. Then we redo it looking only at the low-order digits and combine the results. The output is 286573922006908542050, which agrees with WA. Values of d between 5 and 15 work fine.

a,b=0.0,1.0
s=0
d=10
for n=1,100/3 do
    a,b=b,a+b
    a,b=b,a+b
    s=s+b
    a,b=b,a+b
end
h=string.format("%.0f",s):sub(1,-d-1)
m=10^d
a,b=0,1
s=0
for n=1,100/3 do
    a,b=b,(a+b)%m
    a,b=b,(a+b)%m
    s=(s+b)%m
    a,b=b,(a+b)%m
end
s=string.format("%0"..d..".0f",s)
print(h..s)

In the line `print(h..s)` value `s` may require left-padding with zeroes when converting to string. — Egor Skriptunoff, Dec 19 '15 at 01:34

How to create Fibonacci sequence in Lua?

2 Answers2