[r-t] Exhausted search spaces
mark at snowtiger.net
Thu Feb 4 23:04:37 UTC 2010
> I can't believe hand coded assembler
> is a whole order of magnitude faster, so this suggests that
> I'm missing some tricks
There are a few tricks in SMC32, but mostly those are to do with
optimising the amount of work you do for very false methods. The main
trick for clean methods is to use the rotationally-sorted search (your
"rotation pruning") and to have a very very very tight inner loop.
What language did you write your search in? Hand-coded assembler isn't
normally an order of magnitude faster than the product of a good
optimising compiler, but remember - this is hand-coded assembler
produced by MBD. ;-) In the days of the Pentium MMX, that tight inner
loop was absolutely awesome. It still rocks, but I suspect I could do
better on the newer architectures.
Anyway, Simon H must have a pretty slow computer, because I've just run
the same search for six minutes and I got 10.89 million compositions
(not counting rotations).
> I'm also curious as to how you estimate the proportion of
> the way through.
In SMC32 it was some approximation based on a log or a power or
something like that. Elf used something a bit more sophisticated - have
a look at the Javadoc. The proper way to do it, according to my good
friend Mike Ovenden, is to use "necklaces". I was planning to implement
the algorithm, but it looked a bit scarily mathematical to me, so I
More information about the ringing-theory