How to find out if a number is in the Fibonacci Sequence

Question

I have created a function that gives the Fibonacci number for a given input. I now want to create a function to check if a given number is in the Fibonacci Sequence.

Here is what I have done so far:

-- Basic Fib Function 
fib :: Int -> Int 
fib x =
  if x < 1
    then 0
    else if x < 2
           then 1
           else fib (x - 1) + fib (x - 2)

-- Outputs list of all the functions 
fibList :: [Int]
fibList  = map fib [1..]
--  function that takes an Integer, and returns True if the argument is a Fibonacci number and False otherwise
isFib :: Int -> [Int] -> Bool
isFib n fibList
    |n `elem` fibList = True
    |otherwise = False

fibList works but the computation is taking very long time. Also, I have done this:

fibList' :: [Int]
fibList'  = map fib [1..100]

isFib' :: Int -> [Int] -> Bool
isFib' n fibList'
    |n `elem` fibList' = True
    |otherwise = False

With a smaller number, it still takes a long time to compute

ghci

Willem Van Onsem · Accepted Answer · 2022-01-08T19:48:57.787

5

The problem is that n is an Int and fibList is an [Int], you can not check if an Int and [Int] are the same, since these have a different type.

Using elem will also fail in case the given number is not a Fibonacci number, since Haskell will keep enumerating over the list looking for the next candidate and will only return False if it reaches the end of the list, but if you generate an infinite list, then this will never end.

You can implement the isFib function where we check if the first item of the list is greater than n. If that is the case, we know that all remaining elements will be larger, and thus we can stop searching:

isFib :: Int -> [Int] -> Bool
isFib _ [] = False
isFib n (x:xs)
    | x >= n = -- ...  🖘 to implement
    | otherwise = isFib n xs

where I leave filling in the … part as an exercise.

Your fib function is not very efficient: it will take exponential time to determine the n-th element. You can generate the Fibonacci numbers through recursion and check if one of the items we generate is indeed a Fibonacci number:

isFib :: Int -> Bool
isFib n = go 0 1
  where go f1 f2
          | f1 >= n = …
          | otherwise = go f2 (f1 + f2)

edited Jan 08 '22 at 19:48

answered Jan 08 '22 at 17:33

Willem Van Onsem

443,496
30
428
555

4

You should probably also not define `fibList` as a top-level value, causing it to be retained. It would be nearly as fast to recompute it each time it's used, since addition is very cheap. – amalloy Jan 08 '22 at 19:39
1

@amalloy The compiler may float a list to a top-level CAF anyway. There's some ways to avoid that such as https://stackoverflow.com/q/6090932 but it's not as simple as "don't define it as a top-level value". – ephemient Jan 08 '22 at 22:23
Also, the `isFib` defined here will still loop for inputs above 7540113804746346429 (assuming 64-bit Int) due to wrapping, but that could be handled by cutting off the Fibonacci generator if necessary (or switching to Integer). – ephemient Jan 08 '22 at 22:30
1

I think there are much less inefficient ways to solve the problem. One simple thing is to use the inverse of the closed form of the Fibonacci sequence to come up with a reasonable lower bound for where in the sequence the number could appear. Multiplication by squaring with matrices can jump you to the lower bound efficiently, and you can work your way up from there. I imagine there are much more sophisticated approaches as well. – dfeuer Jan 09 '22 at 03:34
1

@ephemient there's only 92 elements below that. :) `Int`s are definitely not good here at all. – Will Ness Jan 09 '22 at 08:15

How to find out if a number is in the Fibonacci Sequence

1 Answers1