Contents

Recalling the definitions of § 1, we write for , and for . Consider first how one would compute these quantities using an approximation to the real number . If an approximation to is used which has , then the error in the corresponding approximation to is about . Thus, for large

On the other hand, if is an algebraic integer, then all lie in
. Specifically, if has degree **d** and minimal polynomial **P**,
and if is the polynomial of degree **d-1** definied by , where is as in § 1, then . The thus
provide an exact representation of , so the question can
be effectively answered. Since the satisfy the recurrence

The only difficulty is the determination of . This can be computed using an approximation to of modest
accuracy unless is unusually close to an integer **c**. If
is a Salem number, standard arguments from transcendence theory show that

In practice, we can simply choose an approximation to of fixed accuracy . (We usually chose to be or .) The number is an approximation to whose accuracy is easily estimated. If , and if , then . Thus, if the distance from to the nearest integer is at least , then .

Our algorithm begins with (double precision). If at
some point in the computation, the criterion of the previous paragraph fails, the
computation of is repeated with a having accuracy (quadruple precision). If the criterion fails at this level of accuracy, then
the computation is terminated. This occurred for only five values of in our
entire project, one of which can be recognized in Table 2: is not given, but the
corresponding lower bound on **D** is .
For each , the values of **n** for which a change from double precision to
quadruple precision was necessary were recorded in a file during the computation. We
indicate below how these values were used in some cases to determine some of the larger
values of .

As a sample of the accuracy needed, suppose we were to take for
the with . Then for **n = 167305** one computes , suggesting that , while in fact , so . On the other hand, for most values of **n**, a far less
accurate value of would suffice. The two-tier arrangement described in the
previous paragraph allows one to make use of the fast double-precision multiplication on
the machine used (an Amdahl 5860) while retaining the benefits of a higher-precision
calculation when required. One could easily envision a multiple-tier approach.
The sequence is periodic if and only if is bounded. Thus,
if is a beta number, its expansion can be computed using an approximation
of some fixed accuracy (which depends on , of course).

Contents