Закрытое выражение Фибоначчи в Хаскеле

Question

Как будет выглядеть код *1001* закрытой формы Фибоначчи в haskell ?

Answer 1

Вот простой перевод формулы в 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

Это дает точный ответ.

---

Даниэль Фишер указывает, что мы можем использовать формулу 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

Answer 2

Тривиально, формула Бине, из страница Haskell wiki представлена ​​в Haskell как:

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

Что включает в себя разделение результата квадратного корня. Например:

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

Для произвольных целых чисел вам нужно быть немного более осторожным в отношении преобразования в значения с плавающей запятой. Обратите внимание, что значение Бине отличается от рекурсивной формулы на совсем немного на данный момент:

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

Вам может потребоваться больше точности: -)