[r-t] Big searches

Mark Davies mark at snowtiger.net
Mon Jan 7 22:55:20 UTC 2008

Mike Ovenden writes,

> Mine's basically the FKM algorithm (see below) with some pruning for
> falseness.

WTF is the FKM algorithm?? Could it be that the difference between my node
counts and yours is that you are using a super-cool-esoteric-TLA-mathmo
algorithm and I'm just using a bog-standard rotationally-sorted search? :-)

Looking at your mate Gordon's explanation, there does appear to be some
familiar bits. I could almost imagine that a "Lyndon word" is a one-part
composition, and a "periodic necklace" is a multipart, but I might be
horribly wrong. A "pre-necklace" looks like something you'd drop because
it's a multipart you've already found with a better prefix. I seem to 
remember something like that in my rotational sort, bit hacky but it works.

Have you tried running SMC32 on those short lengths of MUG, to see if we
start agreeing at any stage?


More information about the ringing-theory mailing list