[seqfan] Re: Binary Complement Sequences

[Joseph Myers]

I'd suggest accelerating it along the following lines:

Say you have some term t of the trajectory, and you wish to jump 2n terms 
ahead (*not* computing all the intermediate terms).  If, in those 2n 
terms, none are shorter than k bits, then the low-order k bits of the term 
2n ahead are the low-order k bits of (9^n)t + (9^n-1)/4.  So we split the 
computation of the term 2n ahead into computing the low-order bits and the 
high-order bits (heuristically, it probably doesn't go down by more than 
O(sqrt(n)) bits in 2n terms).

For the low-order bits, you can precompute a series of values of 9^n and 
(9^n-1)/4 (say, for n equal to various powers of 2) and use those for all 
the trajectories for which you're doing accelerated computation.  And of 
course you use multiplication algorithms that are appropriate to the size 
of n rather than naive ones (although even naive algorithms would still 
give an acceleration, e.g. multiplying directly by 9^20 < 2^64 could be 
expected to be 40 times faster than doing 40 multiplications by 3).

For the high-order bits, go term-by-term, but only use 4n + O(sqrt(n)) 
bits in the computation - where those 4n overlap with the k low-order 
bits.  In those high-order bits, after m steps, the value you've computed 
is uncertain by at most 3^m (so typically the uncertainty is within those 
4n overlapping bits).  You can readily tell at each step whether the 
uncertainly affects the position of the highest bit, and so the results of 
complementing: just check whether an appropriate sequence of high-order 
bits are exactly a power of 2 or one less than a power of 2 (depending on 
the sign of m).  If you're unlucky, abandon that accelerated computation 
jumping 2n steps at a time and try again with smaller n (or going one step 
at a time).  Otherwise, at the end of this process, you have high-order 
bits to go along with the low-order bits, but the multiplication for all 
the low-order bits was done as a single multiplication by 9^n using an 
efficient algorithm rather than as 2n multiplications by 3.

Obviously you need to tune the parameter n (depending on the length of t) 
and the implicit parameter in O(sqrt(n)); larger n speeds up the 
computation for low-order bits but slows down the computation for 
high-order bits, while the implicit parameter should probably be chosen to 
make it rare that there's any need to recompute with smaller n.  And when 
the terms get small enough, switch back to computing term by term; this 
approach probably doesn't make sense for less then several hundred bits, 
maybe several thousand, and in any case you need to detect exactly when 
you reach 0.

-- 
Joseph S. Myers
jsm at polyomino.org.uk

On Thu, 22 Dec 2022, Allan Wechsler wrote:

> While we wait breathlessly to learn the fate of 425720, I have started
> wondering if there is some way of accelerating the computation. I don't
> have any big insights to report, but I would like to mention that one
> doesn't need to know *all *the bits of one term of the trajectory in order
> to *begin* calculating the next.
> 
> For example, if we know that the most significant bits of one term are
> 11101, then we can be sure that the next term starts 10, and that the first
> bit has index one greater than the first bit of the previous term.
> 
> So if we had a term with 400,000 bits, and accidentally lost the least
> significant bit, we would still be able to predict the binary order of
> magnitude of the next couple of hundred thousand terms before our
> ignorance swallowed up everything we knew about the numbers. This doesn't
> actually put a real dent in the problem, but it's fun to think about, and
> maybe there might be more profound accelerations to be had if we thought
> harder about it.
> 
> On Wed, Dec 21, 2022 at 2:02 AM Christian Sievers <seqfan at duvers.de> wrote:
> 
> > On Fri, Dec 16, 2022 at 04:38:07PM -0500, Allan Wechsler wrote:
> >
> > > As long as the iterates remain large, the low-order bits quickly enter
> > > cycles, in which they remain until the number shrinks to the
> > corresponding
> > > order of magnitude. The low-order bit alternates between 1 and 0; the two
> > > low-order bits read [0, 3, 2, 1] and repeat, and the low three bits read
> > > [0, 7, 2, 1, 4, 3, 6, 5]. I don't know if there is always a single cycle
> > of
> > > length 2^n, but this is an obvious early question.
> >
> > There is always one cycle of full length.
> >
> > Looking at the last n bits and assuming that the complement flips all
> > bits because there is enough going on at higher bits amounts to
> > considering the residues modulo 2^n of the values of the iterations of
> > the function
> >   f(x) = -3*x-1.
> >
> > If we have a cycle of length 2^n in the residues modulo 2^n, then
> > there are only two possibilities for mod 2^(n+1):
> > We can start the cycle at 0. Then we know that after 2^n steps the
> > value is 0 (mod 2^n), so it is 0 or 2^n (mod 2^(n+1)). In the first
> > case, the cycle repeats after 2^n steps, in the second case it has
> > length 2^(n+1).
> >
> > So we have to show that for all n,
> >    f^{2^n}(0) is divisible by 2^n but not by 2^(n+1).
> > (Here f^k denotes the composition f \circ f \circ ... \circ f (k times).)
> >
> > In general, if       g(x)  = a*x+b,
> >             then   g(g(x)) = a^2*x + ab+b   (*).
> >
> > Now define sequences a_n and b_n by
> >    f^{2^n}(x) = a_n * x + b_n.
> >
> > We have a_0=-3 and b_0=-1.
> > Using (*) and induction, we see that each a_n is a power of -3,
> > so 1 (mod 4), so it can be written as 4k+1 for some integer k.
> >
> > Then by (*),
> >   b_{n+1} = a_n * b_n + b_n = (4k+1) * b_n + b_n = (2k+1)*2*b_n.
> >
> > So b_n gains exactly one factor of 2 each time we increase n,
> > and since b_0 is odd and f^{2^n}(0)=b_n, this shows the divisibility
> > property we wanted.
> >
> >
> > All the best
> > Christian
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/