有没有更好的方法来使用有理数来实现斐波那契公式？

Question

我正在看Learn you some Haskell for the Greater Good这本书，因为我在Haskell中玩递归我实现了斐波那契函数，递归版本很简单，可能可以改进：

-- recursive fibonacci numbers
rfib :: Int -> Int
rfib 0 = 0
rfib 1 = 1
rfib n =   rfib (n-1) + rfib(n-2)

当我在谷歌上搜索以了解更多信息时，我偶然发现了这篇文章： http://java.dzone.com/articles/what-fibonacci-taught-me-about

作者展示斐波那契公式：

我决定在 Haskell 中使用有理数来实现它以避免浮点不精确。我的实现如下所示：

fibMultiplier   = (toRational 1) / (toRational (sqrt 5))
firstFibTerm  n = (((toRational 1)  + (toRational (sqrt 5))) / toRational 2) ^ n
secondFibTerm n = (((toRational 1)  - (toRational (sqrt 5))) / toRational 2) ^ n

fib :: Int -> Int
fib n = truncate (fromRational (fibMultiplier * firstFibTerm n) - (fibMultiplier * secondFibTerm n))

作为初学者，我相信上面的代码可以大大改进，你能指出我可以改进的地方或我犯的一些错误吗？

感谢您的帮助。

更新

因此，在尝试了这些建议之后，我发现使用 Data.Real.Constructible 既快速又精确，没有舍入错误。我的最终实现是：

fib :: Int -> Construct
fib n = ( ( (1 / (sqrt 5)) * ( (( 1 + (sqrt 5) ) / 2) ^ n ) ) -
          ( (1 / (sqrt 5)) * ( (( 1 - (sqrt 5) ) / 2) ^ n ) ) )::Construct

我还实现了一个函数，returns n 个斐波那契数的列表：

fibList :: Int -> [Construct]
fibList n = [fib(x) | x <- [0..n]]

使用这个函数我们可以比较不同实现的结果：

-- recursive fibonacci numbers
rfib :: Int -> Int
rfib 0 = 0
rfib 1 = 1
rfib n =   rfib (n-1) + rfib(n-2)

-- recursive fibonacci sequence
rfibList :: Int -> [Int]
rfibList n = [rfib(x) | x <- [0..n]]
-- rfibList 20 returns: [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]


-----------------------------------


-- fibonacci number using Double and truncate
doubleFib :: Integer -> Integer
doubleFib n = truncate ( ( (1 / (sqrt 5)) * ( (( 1 + (sqrt 5) ) / 2) ^ n ) ) -
                         ( (1 / (sqrt 5)) * ( (( 1 - (sqrt 5) ) / 2) ^ n ) ) )

-- fibonacci list using Double and truncate
doubleFibList :: Integer -> [Integer]
doubleFibList n = [doubleFib(x) | x <- [0..n]]
-- doubleFibList 20 returns: [0,1,0,2,3,5,8,13,21,34,55,89,143,232,377,610,986,1597,2584,4181,6764]


-----------------------------------


-- fibonacci number using Construct
constructFib :: Int -> Construct
constructFib n = ( ( (1 / (sqrt 5)) * ( (( 1 + (sqrt 5) ) / 2) ^ n ) ) -
                   ( (1 / (sqrt 5)) * ( (( 1 - (sqrt 5) ) / 2) ^ n ) ) )::Construct

-- fibonacci list using construct
constructFibList :: Int -> [Construct]
constructFibList n = [constructFib(x) | x <- [0..n]]
-- constructFibList 20 returns: [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765]

请注意，我们在 doubleFibList 上出现舍入错误，第 16 个数字应该是 987，但我们得到 986。递归实现很慢，Double 实现不精确，但是使用 Construct 我们可以得到一个快速而精确的斐波那契数列，比我以前使用 toRational 的实现要好得多。

Answer 1

（您不能使用 sqrt 版本，请改用 Data.Real.Constructible）

import Data.Real.Constructible 

fib :: Int -> Construct 
fib n = (((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)/sqrt(5)

有没有更好的方法来使用有理数来实现斐波那契公式？

Is there a better way to implement the fibonacci formula using rational numbers?

haskell