当前位置：文江博客话题详情

Haskell 中的 Fibonacci 封闭式表达式

发布于 2024-11-08 01:57:08 字数 236 浏览 1 评论 0原文

斐波那契闭合形式代码在haskell?

在此处输入图像描述

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

只为一人 2024-11-15 01:57:08

以下是该公式到 Haskell 的简单翻译：

fib n = round $ (phi^n - (1 - phi)^n) / sqrt 5
  where phi = (1 + sqrt 5) / 2

它只能给出 n = 75 以内的正确值，因为它使用 Double 精度浮点运算。

但是，我们可以通过使用 a + b * sqrt 5 形式的数字来避免浮点运算！让我们为它们创建一个数据类型：

data Ext = Ext !Integer !Integer
    deriving (Eq, Show)

instance Num Ext where
    fromInteger a = Ext a 0
    negate (Ext a b) = Ext (-a) (-b)
    (Ext a b) + (Ext c d) = Ext (a+c) (b+d)
    (Ext a b) * (Ext c d) = Ext (a*c + 5*b*d) (a*d + b*c) -- easy to work out on paper
    -- remaining instance methods are not needed

我们免费获得幂运算，因为它是根据 Num 方法实现的。现在，我们必须稍微重新排列公式才能使用它。

fib n = divide $ twoPhi^n - (2-twoPhi)^n
  where twoPhi = Ext 1 1
        divide (Ext 0 b) = b `div` 2^n -- effectively divides by 2^n * sqrt 5

这给出了准确的答案。

Daniel Fischer 指出，我们可以使用公式 phi^n = fib(n-1) + fib(n)*phi 并处理 a + b * phi< 形式的数字/代码>（即ℤ[φ]）。这避免了笨拙的除法步骤，并且仅使用一次求幂。这提供了一个更好的实现：

data ZPhi = ZPhi !Integer !Integer
  deriving (Eq, Show)

instance Num ZPhi where
  fromInteger n = ZPhi n 0
  negate (ZPhi a b) = ZPhi (-a) (-b)
  (ZPhi a b) + (ZPhi c d) = ZPhi (a+c) (b+d)
  (ZPhi a b) * (ZPhi c d) = ZPhi (a*c+b*d) (a*d+b*c+b*d)

fib n = let ZPhi _ x = phi^n in x
  where phi = ZPhi 0 1

Here's a straightforward translation of the formula to Haskell:

fib n = round $ (phi^n - (1 - phi)^n) / sqrt 5
  where phi = (1 + sqrt 5) / 2

This gives correct values only up to n = 75, because it uses Double precision floating-point arithmetic.

However, we can avoid floating-point arithmetic by working with numbers of the form a + b * sqrt 5! Let's make a data type for them:

data Ext = Ext !Integer !Integer
    deriving (Eq, Show)

instance Num Ext where
    fromInteger a = Ext a 0
    negate (Ext a b) = Ext (-a) (-b)
    (Ext a b) + (Ext c d) = Ext (a+c) (b+d)
    (Ext a b) * (Ext c d) = Ext (a*c + 5*b*d) (a*d + b*c) -- easy to work out on paper
    -- remaining instance methods are not needed

We get exponentiation for free since it is implemented in terms of the Num methods. Now, we have to rearrange the formula slightly to use this.

fib n = divide $ twoPhi^n - (2-twoPhi)^n
  where twoPhi = Ext 1 1
        divide (Ext 0 b) = b `div` 2^n -- effectively divides by 2^n * sqrt 5

This gives an exact answer.

Daniel Fischer points out that we can use the formula phi^n = fib(n-1) + fib(n)*phi and work with numbers of the form a + b * phi (i.e. ℤ[φ]). This avoids the clumsy division step, and uses only one exponentiation. This gives a much nicer implementation:

data ZPhi = ZPhi !Integer !Integer
  deriving (Eq, Show)

instance Num ZPhi where
  fromInteger n = ZPhi n 0
  negate (ZPhi a b) = ZPhi (-a) (-b)
  (ZPhi a b) + (ZPhi c d) = ZPhi (a+c) (b+d)
  (ZPhi a b) * (ZPhi c d) = ZPhi (a*c+b*d) (a*d+b*c+b*d)

fib n = let ZPhi _ x = phi^n in x
  where phi = ZPhi 0 1

回复收藏 0 原文

茶花眉 2024-11-15 01:57:08

在 Haskell 中给出为：

fib n = round $ phi ^ n / sq5
  where
    sq5 = sqrt 5 
    phi = (1 + sq5) / 2

简单地说，来自 Haskell wiki 页面的 Binet公式包括共享平方根的结果。例如：

*Main> fib 1000
4346655768693891486263750038675
5014010958388901725051132915256
4761122929200525397202952340604
5745805780073202508613097599871
6977051839168242483814062805283
3118210513272735180508820756626
59534523370463746326528

对于任意整数，您需要在转换为浮点值时更加小心。
请注意，此时 Binet 的值与递归公式有很大不同：

*Main> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 
*Main> fibs !!   1000
4346655768693745643568852767504
0625802564660517371780402481729
0895365554179490518904038798400
7925516929592259308032263477520
9689623239873322471161642996440
9065331879382989696499285160037
04476137795166849228875

您可能需要更高的精度:-)

Trivially, Binet's formula, from the Haskell wiki page is given in Haskell as:

fib n = round $ phi ^ n / sq5
  where
    sq5 = sqrt 5 
    phi = (1 + sq5) / 2

Which includes sharing of the result of the square root. For example:

*Main> fib 1000
4346655768693891486263750038675
5014010958388901725051132915256
4761122929200525397202952340604
5745805780073202508613097599871
6977051839168242483814062805283
3118210513272735180508820756626
59534523370463746326528

For arbitrary integers, you'll need to be a bit more careful about the conversion to floating point values.
Note that Binet's value differs from the recursive formula by quite a bit at this point:

*Main> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs) 
*Main> fibs !!   1000
4346655768693745643568852767504
0625802564660517371780402481729
0895365554179490518904038798400
7925516929592259308032263477520
9689623239873322471161642996440
9065331879382989696499285160037
04476137795166849228875

You may need more precision :-)

回复收藏 0 原文

~没有更多了~