The speed of the JVM's big ints, and therefore Clojure's, doesn't seem to be competitive.
On Mon, Feb 23, 2009 at 5:46 PM, Raffael Cavallaro < raffaelcavall...@gmail.com> wrote: > > > > 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 -~----------~----~----~----~------~----~------~--~---
