On Feb 23, 2:51 pm, "Stephen C. Gilardi" <squee...@mac.com> wrote:
> The fibs implementation in clojure.contrib.lazy-seqs is not a function
> that returns fib(n) given n.
> I think defining a fib(n) function somewhere in contrib or core that
> operates as efficiently as we can manage would be a good idea.
There was a thread on comp.lang.lisp a while ago where a number of
people went back and forth trying to come up withe the fastest fib(n)
algorithm (again, *not* returning a sequence, but just the nth fib
given n). Here is the winner of that informal competition translated
to clojure:
(defn fib
([n]
(fib n 1))
([n b]
(if (zero? b) ;calculate lucas numbers
(cond
(zero? n) 2
(= n 1) 1
:otherwise
(if (even? n)
(let [ k (/ n 2)
l (fib k 0)]
(+ (* l l) (if (even? k) -2 2)))
(let [ k (- n 1)
l (fib k 0)
f (fib k 1)]
(/ (+ (* 5 f) l) 2))))
(cond ;calculate fibonacci numbers
(zero? n) 0
(= n 1) 1
:otherwise
(if (even? n)
(let [ k (/ n 2)
l (fib k 0)
f (fib k 1)]
(* f l))
(let [ k (- n 1)
l (fib k 0)
f (fib k 1)]
(/ (+ f l) 2)))))))
btw, the relatively naive algorithm:
(defn fib-naive [n]
(first (nth (iterate (fn [[a b]] [b (+ a b)]) [0 1]) n)))
takes over 85 seconds, or more than 40 times as long as the lucas
number based algorithm at top to compute the one millionth fibonacci
number. The simple loop version:
(defn fib-naive2 [n]
(loop [a 0 b 1 counter 0]
(if (= counter n) a
(recur b (+ a b) (inc counter)))))
fares exactly the same as one might expect.
for comparison, here are some timings under different lisps on the
same machine. All timings are after several runs to warm up caches
and, in the case of clojure, hotspot optimizations.
Time to calculate the one millionth fibonacci number using the lucas
number based algorithm at top:
clojure: 2 seconds
ccl: 0.5 seconds
lispworks: 1.7 seconds
mzscheme: 0.15 seconds
sbcl: 0.8 seconds
larceny: 13 seconds
ecl: 0.04 seconds
as you can see, clojure is competitive with other lisps/schemes,
faster than some, slower than others. this is really just a benchmark
of the bignum package used by the lisp implementation. I think ecl
uses GMP which is quite fast.
btw, I tried adding type annotations to the clojure version but it
didn't seem to make much difference.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
