Below is a note of mine from 1995-November-12,
verbatim, including bad spelling.

Joerg Arndt

--------------------------------------------
--------------------------------------------


consider the map
f: [-2,+2] -> [-2,+2],  x |-> x^2 - 2
( i.e. the one at the more interesting end of the feigenbaum diagram,
the 'fully chaotic' case )

we are interested in the symbolic dynamics of the variable b
derived from the sequence {x_0,x_1,...}
( that is defined by x_{n+1}:=f(x_n), given x_0 )
by
d_n:= 1 if x_n<=0
      0 else


define {b_1,b_2,...}:
 acos(x_0/2)/Pi =: \sum_{k=1}^{\infty}{2^k * b_k}

then

------------------------------------------------------
 d_n=1 if b_n!=b_{n-1}
    =0 if b_n==b_{n-1}
------------------------------------------------------

( i.e. d_n=1 if there is a change in the bit pattern of acos(x_0/2)/Pi )


hint:
recall the formula
cos(2u) = 2*cos(u)^2-1
and consider
x:=u/2

cf. the C++ program predict.cc



the above observation allows us to find a
reduced complexity computation of the dynamics of {d_n}:

if we want to find the value of some d_N:

1.we normally had to do N squarings of a number with the precision of
  (proportional to, depending on lyapunov exponent) N bits (=:full_precision).
  This is at the cost of proportional N N-bit multiplications.

2.now we only need to compute one full_precision acos and watch for
  the changes in the bit pattern.
  Using the agm approach this is proportional log(N) N-bit multiplications (?).




Note that there must be implied nice & clean formulas for lyapunov exponents,
points that in the end remain in one box etc.