[Haskell-cafe] origin of my fibonacci test

Michael Litchard michael at schmong.org
Mon May 9 23:59:40 UTC 2016


I have some code that checks to see if a number is a fibonacci number. It's
not mine, I got it from somewhere and I need to credit it. I am pretty sure
I got it from Stack Exchange but my search for it went nowhere. If this
looks familiar to you, or you can tell me better ways to search, please let
me know.

isFib :: Integer -> Bool
isFib n = n == a where (_, a, _) = unFib (1, 1) n

unFib :: (Integer, Integer) -> Integer -> (Integer,Integer,Integer)
unFib (a, b) n
  | n < a = (0, 0, 1)
  | n < e = (2*k, c, d)
  | otherwise = (2*k + 1, e, f)
      where
        (k, c, d) = unFib (fibPlus (a, b) (a, b)) n
        (e, f)    = fibPlus (a, b) (c, d)

fibPlus :: (Integer, Integer) -> (Integer, Integer) -> (Integer,Integer)
fibPlus (a, b) (c, d) = (bd - (b - a)*(d - c), a*c + bd)
  where bd = b*d
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20160509/f8190906/attachment.html>


More information about the Haskell-Cafe mailing list