In paragraph 6.3, a divide and conquer method will be described to accelerate all these different flavours of the Bezout algorithm. But, before that, a precise meaning has to be given to the speed we want accelerate. We begin this discussion by describing some numerical experiments.
These experiments are starting from a lot of 
"random
numbers" 
chosen in the following
way : integers 
were picked at (uniform) random in the range
and 
has been assigned to 
or 
to enforce 
. We have ran the confrac algorithm,
starting successively from these and some statistics have
been collected.
First of all, the length of all these runs were not really different,
ranging from 
to 
and inducing a total of 
elementary steps.
Figure 9 describe the experimental frequences (circles)
of all the encountered 
, tallyied into 
intervals of
equal length. The regular curve is 
.
The 
factor is obvious to normalize the distribution. The
shape factor will be discussed in next paragraph.
Figure 10 describe the repartition of all the encountered
. The left plot describe the experimental frequence (circles)
of those in 
and the right one those in
(the scale of ordinates has been magnified 
in the second graph). There were 
of outside
, the greatest being 
. The regular curve is:
From Eq. 10, we obtain that 
looks like 
i.e. great
values of are so frequent that the arithmetical mean of the
's tends to infinity (the experimental mean is 
). On
the other hand, 
looks like 
, leading
to the Khinchin's rule :
This rule is checked Figure 12, where we have
plotted the max, the min and the arithmetical mean of all the obtained
values for each 
.
To conclude this experimental part, Eq. 9 (if valid...
) implies that 
.
Denoting 
the denominator of the 
th convergent of ,
we obtain the Heilbronn-Levy's rule :
This rule is checked Figure 12, where we have
plotted the max, the min and the arithmetical mean of all the obtained
values for each 
, Moreover, the (arithmetical)
mean of all the obtained 
was 
.
It's time now to discuss the validity of formulae 9,
10, 11 and 12. First
thing to say, these formulae are not appliable to
any of the previously described expansions ! When is rational,
the process stops at some 
where 
. When is
a quadratic number, the process is periodic, leading to special limiting
values (for example, 
leads to 
,
, 
and 
). When
is related to numbers like 
, the 's are
forming an arithmetic sequence implying 
and 
too.
But these formulae nevertheless describe what happens when you randomly
chose the starting point , i.e. for almost every number
in 
. Precise proofs can be found in litterature,
and only the mainlines are given now.
Defining the Gauss operator as:
, i.e. for almost
every ) 
. The key point is
that, for almost every in , the 
are Monte-Carlo distributed, with density given by Eq. 9
i.e. 
.
In other words, for any fixed 
such that 
,
we have :
As an immediate by-product, the associated measure remains invariant
under the action of 
. This can also be checked by direct computation :
, the process
is ergodic. Therefore, the mean over a sequence 
,
taken as the limit of the means over the partial paths starting from
almost any given , is equal to the mean taken over all the
and we have, for any regular function
:
Therefore, the number of steps required for the Bezout algorithm is,
for almost all , equivalent to a linear function of the size
(in binary digits) of the last denominator obtained. Thus the whole
algorithm has, at first sight, a 
complexity
at the bit level. But a 
complexity
can be reached when using fast arithmetic, providing multiplications
at cost 
, together with a divide
and conquer strategy that will reduce the number of steps to 
.
.
.
