斐波那契在Haskell中的闭式表达式 [英] Fibonacci's Closed-form expression in Haskell

问题描述

页面在Haskell中给出：

 n = round $ phi ^ n / sq5 
其中
 sq5 = sqrt 5 
 phi =（1 + sq5）/ 2 
  

其中包括共享平方根的结果。例如：

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

对于任意整数，您需要对转换为浮点值时更加小心。
请注意，在这一点上，Binet的值与递归公式相差很多：

  *主> let fibs = 0：1：zipWith（+）fibs（tail fibs）
 * Main> fibs！ 1000 
 4346655768693745643568852767504 
 0625802564660517371780402481729 
 0895365554179490518904038798400 
 7925516929592259308032263477520 
 9689623239873322471161642996440 
 9065331879382989696499285160037 
 04476137795166849228875 
  

您可能需要更高的精度： - ）

How would the Fibonacci's closed form code look like in haskell?

解决方案

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 :-)

这篇关于斐波那契在Haskell中的闭式表达式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！