如何在 Lua 中创建斐波那契数列？

Question

我写了一个小脚本来创建斐波那契数列和 returns 所有偶数的总和。

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)

该函数创建以下序列： 1, 2, 3, 5, 8, 13, 21, 34, 55

与returns其偶数之和：44

但是，当我将停止索引从 10 更改为 100 时，在 for i=3, 100 do 中返回的总和为负值 -8573983172444283806，因为值变得太大了。为什么我的代码适用于 10 而不是 100？

Answer 1

在 5.3 版之前，Lua 总是在内部将数字存储为浮点数。在 5.3 Lua 中，数字可以在内部存储为整数或浮点数。一种选择是运行 Lua 5.2，我想您会发现您的代码在那里按预期工作。另一种选择是用浮点数初始化你的数组，这将在未来将对它们的所有操作提升为浮点数：

local fib = {1.0, 2.0}

Answer 2

这是事后写的 hack。该代码利用了数学事实，即偶数斐波那契数恰好是索引为 3 的倍数的那些数。这使我们能够避免测试非常大的数字的奇偶校验，并提供在您进行浮点计算时正确的高位数字。然后我们重做它只看低位数字并组合结果。输出为 286573922006908542050，与 WA 一致。 5 到 15 之间的 d 值工作正常。

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)

如何在 Lua 中创建斐波那契数列？

How to create Fibonacci sequence in Lua?

lua

fibonacci

lua-5.3