2 ms·
> 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 take
by 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).