2 ms·
> I’m missing something here… what do you mean by “advance both sides?” Instead of checking `state == advance(state, 2*32-1)`, which takes 32 multiplies, it's
by o11c 3y ago
> I’m missing something here… what do you mean by “advance both sides?”
Instead of checking `state == advance(state, 2*32-1)`, which takes 32 multiplies, it's cheaper to do `advance(state, 1) == advance(state, 2*32), which only takes 2 multiplies (they both still take 32 squares unless you cache those). And actually the special case of 1 didn't require constructing the matrix at all, allowing a cheaper direct computation.
> The cycles of length 6 will fail the test because they will be in a different state after advancing 15 steps.
Okay, now this rings a bell. It has been quite a while since I actually played with this all.
The only other thing that was surprising was that you wrote out your taps including both ends (thus they look to have an odd rather than even), but that's purely a matter of convention.
- dietrichepp 3y ago> Instead of checking `state == advance(state, 232-1)`, which takes 32 multiplies, it's cheaper to do `advance(state, 1) == advance(state, 232), which only takes 2 multiplies (they both still take 32 squares unless you cache those). And actually the special case of 1 didn't require constructing the matrix at all, allowing a cheaper direct computation. Ah! That makes sense. But for N=2^32-1, there are also checks for N/3, N/5, N/17, N/257, and N/65537.
- o11c 3y agoI think the rule is: as long as there is a sequence of at least 3 adjacent 1-bits, you can replace them with 2 1-bits (1 on each side). The new 1-bit can of course merge into an existing run. This only fails to decrease the needed work for the N/3 and N/5 cases here, which form small regular patterns. For larger regular patterns, or for irregular patterns (2^odd-1), chances are that there will be at least some simplification (unless the pattern is mostly zeros in which case it isn't needed anyway).