[seqfan] Re: Binary Complement Sequences

[Tim Peters]

[hv at crypt.org]
> I can't check right now what Floyd's and Brent's algorithms are, but
> one trick I've used in the past is to simultaneously calculate the same
> sequence at half the speed: if it cycles, at some point the n'th and
> 2n'th iterations will give the same value.

Yes, that's Floyd's algorithm. It requires 3 map evaluations per step,
so is unattractive here (our problem cases so far have
multi-hundred-thousand bit integers, and so evaluating the map is
expensive).

But I'm all but wholly persuaded that trying to detect cycles here is
a waste of time. So long as the iterates remain over n bits wide, we
already know the last n bits cycle through all 2^n possibilities. Even
if n is as small as 64, if there is a cycle, the program will run
longer than my lifetime before it could possibly find a repeat in the
last 64 bits alone. The specific cycle detection algorithm is
irrelevant to that: there are no repeats to _be_ found across a "mere"
range of 2^64 values.

That would be OK if it routinely dipped below 64 bits too, but that's
not  what I'm seeing: the iterates reach hundreds of thousands of bits
and can stay that large across billions of iterations.

The largest completed number of steps I've seen so far starts with
717,657. That hit 0 after about 26 billion iterations. The highest
value it reached was around step 11 billion, and had 320,890.bits.

425,720 is still running after over 45 billion iterations, but, a bit
surprisingly, the iterates have fallen back down into the 200,000-bit
range. Or a stray cosmic ray flipped a bit: we've done quadrillions of
bit operations by now, so I won't believe any result without
independent replication.