[r-t] Exhausted search spaces

[Mark Davies]

RAS writes,

 > 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 
never did.

MBD