Posts Tagged ‘fibonacci’

Programming Praxis – Zeckendorf Representation

July 24, 2012

In today’s Programming Praxis exercise, our goal is to find a series of non-consecutive fibonacci numbers that sum up to a given number. Let’s get started, shall we?

First, we define the fibonacci sequence:

fibs :: [Integer]
fibs = 1 : scanl (+) 1 fibs

The algorithm to find the numbers is pretty trivial as well: take the largest fibonacci number less than or equal to the target value and repeat on the remainder.

zeck :: Integer -> [Integer]
zeck 0 = []
zeck n = f : zeck (n - f) where f = last $ takeWhile (<= n) fibs

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ zeck 100 == [89,8,3]
          print $ zeck (3^15) == [9227465, 3524578, 1346269,
                                  196418, 46368, 6765, 987, 55, 2]
          print $ zeck $ 10^100

Programming Praxis – Fibonacci Primes

October 29, 2010

Today’s Programming Praxis exercise comes from the same challenge as the longest palindrome exercise from two weeks ago. The goal is to write a function that calculates the sum of the factors of 1 plus the first prime fibonacci number higher than the input number. Let’s get started, shall we?

To generate the fibonacci numbers, we use the well-known one-liner.

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Getting the factors of a number is done via simple trial division. Unlike the Scheme solution, we don’t repeat factors, since the original challenge says not to.

factors :: Integer -> [Integer]
factors = f 2 where
    f d n | n < d        = []
          | mod n d == 0 = d : f (d + 1) (div n d)
          | otherwise    = f (d + 1) n

We could write some fancy algorithm to check primality, but since we already have a function to calculate factors, why bother? Since the only factor of a prime number will be itself, we can just use that as a check. Initally I just used the isPrime function from Data.Numbers.Primes for this, but looking through the source code I realized I could replace it with this version. Obviously this won’t work too well on large numbers, but for our test case it’s fast enough.

isPrime :: Integer -> Bool
isPrime n = factors n == [n]

The top-level function does what it says on the tin: look through the fibonacci numbers to find one that’s greater than n and prime, add one and return the sum of the factors.

greplin :: Integer -> Integer
greplin n = head [sum $ factors (f + 1) | f <- fibs, f > n, isPrime f]

All that’s left is to apply it to the test number:

main :: IO ()
main = print $ greplin 227000

As expected, we get 352 as a result. And, in the spirit of the contest, which is to do these challenges quickly, I think this one took me about 20 minutes.

Programming Praxis – Fibonacci Numbers

July 30, 2010

In today’s Programming Praxis we have to provide three different methods of calculating the ever-popular Fibonacci numbers; one exponential, one linear and one logarithmic. Let’s get started, shall we?

Some imports:

import Data.List
import Criterion.Main

The naive exponential solution is trivial:

fibexp :: Int -> Integer
fibexp 0 = 0
fibexp 1 = 1
fibexp n = fibexp (n - 1) + fibexp (n - 2)

For the linear method, we use the textbook lazy evaluation-based approach:

fiblin :: Int -> Integer
fiblin n = fibs !! n where fibs = 0:1:zipWith (+) fibs (tail fibs)

The logarithmic solution requires two helper functions: the matrix multiplication function from a previous exercise and a way of raising a matrix to a power in log(n) time.

mult :: Num a => [[a]] -> [[a]] -> [[a]]
mult a b = [map (sum . zipWith (*) r) $ transpose b | r <- a]

matrixpower :: [[Integer]] -> Int -> [[Integer]]
matrixpower m 1 = m
matrixpower m n = (if even n then id else mult m) $
                  matrixpower (mult m m) (div n 2)

All that’s left to do to calculate Fibonacci numbers is raise the given matrix to the correct power and taking the lower-left element.

fiblog :: Int -> Integer
fiblog 0 = 0
fiblog n = matrixpower [[1,1],[1,0]] n !! 1 !! 0

To benchmark the different solutions, we use the Criterion library.

main :: IO ()
main = defaultMain [bench "exp" $ nf fibexp 25
                   ,bench "lin" $ nf fiblin 25000
                   ,bench "log" $ nf fiblog 25000

This gives the following timings: 174 ms for the exponential version, 69 ms for the linear one and 643 microseconds for the logarithmic solution, so we get a 100-fold speedup between the linear and logarithmic version at the cost of a factor of 6 increase in code size. Not a bad trade-off.