Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Implement fibonacci in Clojure using map/reduce

Is it possible to implement the fibonacci series in Clojure efficiently using reduce? What would the "accumulator" contain?

I imagine that it will have to be lazy. It's obvious how to do it using recursion or loop/recur.

like image 633
Ralph Avatar asked Dec 07 '10 12:12

Ralph


2 Answers

You could use a pair of successive fibonacci values as the accumulator, as follows:

(reduce 
  (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
  [0 1]                       ; initial pair of fibonnaci numbers
  (range 10))                 ; a seq to specify how many iterations you want

=> [55 89]

This is not particularly efficient due to the creation of lots of intermediate pairs and use of the superfluous range sequence to drive the right number of iterations, but it is O(n) from an algorithmic perspective (i.e. the same as the efficient iterative solution, and much better than the naive recursive one).

like image 173
mikera Avatar answered Nov 11 '22 03:11

mikera


Not using map/reduce, but iterate can avoid recursion too.

(defn iter [[x y]]
  (vector y (+ x y)))

(nth (iterate iter [0 1]) 10000)

This takes 21ms on an Intel 2.4 Ghz

On the same machine, reduce takes 61msec. Not sure why iterate is faster.

   (time (reduce 
     (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
     [0 1]                       ; initial pair of fibonnaci numbers
     (range 10000)))
like image 41
shark8me Avatar answered Nov 11 '22 03:11

shark8me