challenge: best fibo implementation under the new laziness?

54 views
Skip to first unread message

Stuart Halloway

unread,
Feb 23, 2009, 11:43:31 AM2/23/09
to clo...@googlegroups.com
I have updated the sample source from the book (http://tinyurl.com/clojure-samples
) to the new laziness. Along the way, I replaced the lazy-cons based
implementation of the fibonacci numbers with this:

(defn fibo
([]
(concat [0 1] (fibo 0 1)))
([a b]
(let [n (+ a b)]
(lazy-seq
(cons n (fibo b n))))))

Is there a better/more idiomatic approach, without resorting to code
in clojure-contrib? Test your code against the following expression to
flush out stack and heap overflows.

(rem (nth (fibo) 1000000) 1000)
-> 875

Also, the current 'fibs' implementation in clojure.contrib.seq fails
the test above, because it holds the entire sequence as it goes. We
should replace it with whatever the community comes up with on this
thread.

Cheers,
Stu

Christophe Grand

unread,
Feb 23, 2009, 1:24:01 PM2/23/09
to clo...@googlegroups.com
Using a good old sequence of vectors:
(defn fibo []
(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

Christophe

Stuart Halloway a écrit :
--
Professional: http://cgrand.net/ (fr)
On Clojure: http://clj-me.blogspot.com/ (en)


Stephen C. Gilardi

unread,
Feb 23, 2009, 2:51:15 PM2/23/09
to clo...@googlegroups.com

On Feb 23, 2009, at 11:43 AM, Stuart Halloway wrote:

> Also, the current 'fibs' implementation in clojure.contrib.seq fails
> the test above, because it holds the entire sequence as it goes. We
> should replace it with whatever the community comes up with on this
> thread.

The fibs implementation in clojure.contrib.lazy-seqs is not a function
that returns fib(n) given n. Instead, it is an infinite sequence of
all the fibonacci numbers. It holds onto its head because it's
intended to. It's surely not the right way to deal with fibonacci
numbers in every context, but I don't think it needs replacing because
it requires a large java heap to pass this test:

(rem (nth clojure.contrib.lazy-seqs/fibs 1000000) 1000)
-> 875

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.

--Steve

chris

unread,
Feb 23, 2009, 4:01:04 PM2/23/09
to Clojure
As the sequence is very cheap to calculate it is difficult to see the
benefit of keeping it in memory under any circumstances. I would
replace the one in contrib with Christophe's short, easy to understand
implementation. Caching values isn't getting you anywhere; just
wasting resources.

Chris
>  smime.p7s
> 3KViewDownload

Stuart Halloway

unread,
Feb 23, 2009, 5:20:30 PM2/23/09
to clo...@googlegroups.com
Beautiful-thanks.

Raffael Cavallaro

unread,
Feb 23, 2009, 5:46:05 PM2/23/09
to Clojure


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.

Jeffrey Straszheim

unread,
Feb 23, 2009, 9:31:15 PM2/23/09
to clo...@googlegroups.com
The speed of the JVM's big ints, and therefore Clojure's, doesn't seem to be competitive.

Raffael Cavallaro

unread,
Feb 23, 2009, 10:26:43 PM2/23/09
to Clojure


On Feb 23, 9:31 pm, Jeffrey Straszheim <straszheimjeff...@gmail.com>
wrote:
> The speed of the JVM's big ints, and therefore Clojure's, doesn't seem to be
> competitive.

Clearly the JVM's big ints doesn't compare favorably with GMP. On the
other hand, Clojure falls near the middle of the range of the various
lisps and schemes. It's about as fast as LispWorks 32-bit for example.

Michel Salim

unread,
Feb 23, 2009, 11:11:16 PM2/23/09
to clo...@googlegroups.com

Too bad GMP is LGPLv3+, while Java is GPLv2 only, so we'll not see
Java using GMP in the foreseeable foture. Kaffe's JVM uses GMP,
though. If Clojure runs on it, it'd be interesting to see what sort of
numbers it produces.

I've not seen a decent GMP wrapper for Java -- does anyone know of any
such implementation?

Regards,

--
miʃel salim • http://hircus.jaiku.com/
IUCS • msa...@cs.indiana.edu
Fedora • sal...@fedoraproject.org
MacPorts • hir...@macports.org

Laurent PETIT

unread,
Feb 24, 2009, 12:04:43 AM2/24/09
to clo...@googlegroups.com
Hello,
What about giving back 'lazy-cons (or lcons as a shortcut), with the optional possibility to give the cons an internal name ?
This could allow for self-recursive definition, such as this one for a fibonacci generator function as :

user=>(defn fib-fn [] (lcons [fib] 1 (lcons 1 (map + fib (rest fib)))))
#'user/fib-fn
user=> (take 10 (fib-fn))
(1 1 2 3 5 8 13 21 34 55)

If you think it's interesting, see the detailed explanation below, and find the patch to play with it in google groups files section :
http://groups.google.com/group/clojure/web/lazy-cons.patch

I wanted to try a definition closer to the one I had in my Haskell book. This definition needs the ability for the lazy-seq to reference itself.
For example, it can in straight clojure be written as :

(def fib (lazy-seq (cons 1 (lazy-seq (cons 1 (map + fib (rest fib)))))))

But of course, the above version, while interesting, leaks memory since the lazy seq is bound to a global var.

So I've played with clojure core to allow the creation of lazy-sequences that can refer to themselves inside their body, and get rid of the memory leak problem.

I've called this 'named-lazy-seq : (named-lazy-seq [a-name] ... )
And since the pattern (lazy-seq (cons ...)) may well be a common one, I've also recreated 'lazy-cons (or lcons for brevity) that is just a macro calling either 'lazy-seq or 'named-lazy-seq depending on its arity :

(lazy-cons a-first-elem a-tail) <=> (lazy-seq (cons a-first-elem a-tail))
or
(lazy-cons [a-name] a-first-elem a-tail) <=> (named-lazy-seq [a-name] (cons a-first-elem a-tail))

With these additions, one can write the fibonacci lazy sequence as :

(lcons [fib] 1 (lcons 1 (map + fib (rest fib))))

and, of course, a fibonacci lazy sequence generator :
(defn fib-fn []
  (lcons [fib] 1 (lcons 1 (map + fib (rest fib)))))

HTH,

--
Laurent

2009/2/23 Stuart Halloway <stuart....@gmail.com>

Beautiful-thanks.
- Afficher le texte des messages précédents -

Christophe Grand

unread,
Feb 24, 2009, 3:28:35 AM2/24/09
to clo...@googlegroups.com
Laurent PETIT a écrit :

> Hello,
> What about giving back 'lazy-cons (or lcons as a shortcut), with the
> optional possibility to give the cons an internal name ?
It would work and that's why Stuart said "without resorting to code in
clojure-contrib":
(defn fibo[]
(seq-utils/rec-cat fib [0 1] (map + fib (rest fib))))

(Btw, Stuart, due to latest changes in Clojure's lazy-seq
implementation, rec-seq is atom-based again.)

Christophe

Laurent PETIT

unread,
Feb 24, 2009, 3:41:42 AM2/24/09
to clo...@googlegroups.com

2009/2/24 Christophe Grand <chris...@cgrand.net>


Laurent PETIT a écrit :
> Hello,
> What about giving back 'lazy-cons (or lcons as a shortcut), with the
> optional possibility to give the cons an internal name ?
It would work and that's why Stuart said "without resorting to code in
clojure-contrib":
(defn fibo[]
 (seq-utils/rec-cat fib [0 1] (map + fib (rest fib))))

Wow, I think now is time for me to also try to learn more the stuff that is in clojure-contrib !

Anyway, it was interesting to try doing it by tweaking clojure itself :-)

Could'nt it be interesting to consider adding the possibility to make self recursive calls inherent to lazy-seqs, as I proposed ?

It's a one line change in a clojure class, and a one line change in lazy-seq also.

And I don't think it would have performance impacts for people not willing to use that.

Have you looked at the patch I provided ?

Regards,

--
Laurent

Christophe Grand

unread,
Feb 24, 2009, 4:13:49 AM2/24/09
to clo...@googlegroups.com
Laurent PETIT a écrit :
>
> 2009/2/24 Christophe Grand <chris...@cgrand.net
> <mailto:chris...@cgrand.net>>

>
>
> Laurent PETIT a écrit :
> > Hello,
> > What about giving back 'lazy-cons (or lcons as a shortcut), with the
> > optional possibility to give the cons an internal name ?
> It would work and that's why Stuart said "without resorting to code in
> clojure-contrib":
> (defn fibo[]
> (seq-utils/rec-cat fib [0 1] (map + fib (rest fib))))
>
>
> Wow, I think now is time for me to also try to learn more the stuff
> that is in clojure-contrib !
>
> Anyway, it was interesting to try doing it by tweaking clojure itself :-)

Prior to r1300 it was even easier: no change to Clojure was required.

> Could'nt it be interesting to consider adding the possibility to make
> self recursive calls inherent to lazy-seqs, as I proposed ?

While having played a lot with rec-cons, rec-cat and rec-seq — which can
prove useful in simplifying some code —, I'm still ambivalent about the
general case of recursive data structures in functional programming
that's why I'm not lobbying for their inclusion in core.

> Have you looked at the patch I provided ?

Yes: simple and clever.

Christophe

Dimiter "malkia" Stanev

unread,
Feb 24, 2009, 4:14:15 AM2/24/09
to Clojure
And this is by using "java -server", not "java -client", right?

On Feb 23, 2:46 pm, Raffael Cavallaro <raffaelcavall...@gmail.com>
wrote:

Raffael Cavallaro

unread,
Feb 24, 2009, 11:55:03 AM2/24/09
to Clojure
On Feb 24, 4:14 am, "Dimiter \"malkia\" Stanev" <mal...@gmail.com>
wrote:
> And this is by using "java -server", not "java -client", right?

yes

Luke VanderHart

unread,
Feb 24, 2009, 1:18:56 PM2/24/09
to Clojure
Just out of curiosity - did you by any chance "warm up" the JVM to
make sure that the fib function was JIT'd before you did this
benchmark?

On Feb 23, 5:46 pm, Raffael Cavallaro <raffaelcavall...@gmail.com>
wrote:

Raffael Cavallaro

unread,
Feb 24, 2009, 4:52:46 PM2/24/09
to Clojure


On Feb 24, 1:18 pm, Luke VanderHart <luke.vanderh...@gmail.com> wrote:
> Just out of curiosity - did you by any chance "warm up" the JVM to
> make sure that the fib function was JIT'd before you did this
> benchmark?
>
> On Feb 23, 5:46 pm, Raffael Cavallaro <raffaelcavall...@gmail.com>
> wrote:
> > 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.
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

yes
Reply all
Reply to author
Forward
0 new messages