# [plt-scheme] Fractals

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
fast).
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)
* 'done))
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.
Interesting!
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