[plt-scheme] Fractals

From: Joshua Zucker (joshua.zucker at gmail.com)
Date: Wed Sep 20 18:59:32 EDT 2006

Thanks so much for the help!

I improved one little bit of my inner calculation (just switching the
order of two checks, one of which was likely to be much faster on
average) and in practice see a significant speedup (more than twice as

So I agree, changing my O(n^3) algorithms and making them O(n^2 ln n)
instead, even if the constant is bigger, is the first thing to do;
implementing them in C is last.  But it's good to know how to do it!

Mostly right now the obvious place for big speedup is in my collision
detector (given a new segment, see if it hits one of a bunch of old
ones).  That's a well-known algorithm and ought to be really fast.

Also I use atan in my convex hull algorithm instead of just using y/x
to figure out the smallest slope.  That's another obvious potential
speedup.  Oddly, in timing it, I just made DrScheme unexpectedly
quit!?  Or maybe it was just a freak occurrence.  Let's see.

> (define stuff (build-list 100000 (lambda (x) (make-posn (add1 (random 100)) (add1 (random 100))))))
> (time (begin (map (lambda (p) (atan (/ (posn-y p) (posn-x p)))) stuff)

Nope, no crash this time.
The same code without atan runs in about 2/3 the time (200 msec vs 300).
So ... maybe the loop overhead is dominating?  I can't believe that /
is really that close in speed to atan.  Hm, but I was using integers.
Using floats still about the same thing (add1 -> + 1.01 ...), 180 msec
vs 250.


Anyway, none of these kinds of speedups will solve the fundamental
problem of blindly doing exponential-time searches ... so I have to
think too, more's the pity.

Again, thanks to all for your help.
--Joshua Zucker

Posted on the users mailing list.