Daniel Martin
7/8/2006 10:58:00 AM
Christoffer Lernö <lerno@dragonascendant.com> writes:
> This is really crazy.
>
> Either people have optimized things a whole lot better than me (not
> unlikely, I haven't made any real attempts at optimizing things), or
> I am using a bad algorithm.
>
> I didn't time the solution:
>
> ...but it took my program 8018361 iterations.
>
> Is it the optimization or the algorithm I got wrong?
I agree that Simon must be using a different, better algorithm. I
think I'm using the same one that you are, (the randomized Robinsoning
described on the linked page, which is what the perl program there
uses) and with the same prefix get an answer in 16990348 iterations
(so twice as long) and it takes just over 83 minutes.
I /really/ don't think that the difference between this and the
sub-10-second versions is just luck. I'm going to run the program in
a loop in the background today just to check the luck angle - if every
run takes on the order of an hour to produce output, then clearly
there's another approach we're missing.