[seqfan] Re: Binary Complement Sequences

[Tim Peters]

[Tom Duff]
> I ran all starting numbers from 0 to 42569 with cycle-checking
> turned on. Every one descended to zero.

Great!

> For the 425720 run, I turned cycle checking off, because the program
> runs much quicker without it (Floyd's algorithm -- Brent hadn't
> devised his until long after I was out of school and no longer paying
> attention to that sort of thing, so I hadn't heard of it)

The practical drawback of Floyd's elegant method is that it requires
evaluating the map 3 times per step. The "complement 3*x" map here
takes time proportional to the number of bits in x, so gets
ever-pricier the more bits x consumes.

The huge practical advantage of Brent's method in such cases is that
there are no "extra" map evaluations: just one map evaluation per
step. Which needs to be done regardless of whether checking for a
cycle.

Here's how it works (I hope this is of general interest, since it's a
practical solution to many "OEIS-like" subtasks):

CHECK = CHECKTOTAL = 1 # not delicate
BASE = x
loop:
    x = f(x) # iterate the map
    if x == BASE:
        found a cycle
    CHECK = CHECK - 1
    if CHECK == 0:
        BASE = x
        # any monotonically increasing sequence will do;
        # it will eventually exceed the cycle length
        CHECK = CHECKTOTAL = CHECKTOTAL * 2

So one extra "big int" to remember, and one extra "big int" equality
comparison per step. Hard to imagine anything could be cheaper. The
equality comparison is usually "almost instant", due to a bigint
implementation seeing that the comparands have a different number of
bits (or "limbs"), or differ in the first limb pair checked.

> and I thought the chance of hitting a non-zero cycle was pretty small. In any
> case, I also record the length of the numbers every million iterations and I
> think the resulting graph will likely make it obvious whether there's a chance
> it's fallen into a cycle.

As already said, the size of intermediate values across iterations
already passed my threshold for worrying about a cycle. At the moment,
I'm in the high 17 billion number of steps, and the value being worked
on is still about 400 thousand bits. It just doesn't appear to have
been trending, in either direction, for the last 6+ billion steps.

Brent's cycle detection method is, by far, the cheapest I know of - in
this particular problem, the minor bookkeeping it requires is
basically free compared to the expense of iterating the map on
multi-hundred-thousand bit values.

I used a yet different method at first, one that also requires no
extra map evaluations, and leaves behind the largest value ever seen
as a side effect. But that one needs more elaborate bookkeeping, such
that it slowed the no-detection code by about 50%.

I know that Brent slows it too, but that's more provable than measurable ;-)