info prev up next book cdrom email home

Ferguson-Forcade Algorithm

A practical algorithm for determining if there exist integers $a_i$ for given real numbers $x_i$ such that

\begin{displaymath}
a_1x_1+a_2x_2+\ldots+a_nx_n=0,
\end{displaymath}

or else establish bounds within which no such Integer Relation can exist (Ferguson and Forcade 1979). A nonrecursive variant of the original algorithm was subsequently devised by Ferguson (1987). The Ferguson-Forcade algorithm has shown that there are no algebraic equations of degree $\leq 8$ with integer coefficients having Euclidean norms below certain bounds for $e/\pi$, $e+\pi$, $\ln\pi$, $\gamma$, $e^\gamma$, $\gamma/e$, $\gamma/\pi$, and $\ln\gamma$, where e is the base for the Natural Logarithm, $\pi$ is Pi, and $\gamma$ is the Euler-Mascheroni Constant (Bailey 1988).

Constant Bound
$e/\pi$ $6.1030\times 10^{14}$
$e+\pi$ $2.2753\times 10^{18}$
$\ln\pi$ $8.7697\times 10^{9}$
$\gamma$ $3.5739\times 10^{9}$
$e^\gamma$ $1.6176\times 10^{17}$
$\gamma/e$ $1.8440\times 10^{11}$
$\gamma/\pi$ $6.5403\times 10^9$
$\ln\gamma$ $2.6881\times 10^{10}$

See also Constant Problem, Euclidean Algorithm, Integer Relation, PSLQ Algorithm


References

Bailey, D. H. ``Numerical Results on the Transcendence of Constants Involving $\pi$, $e$, and Euler's Constant.'' Math. Comput. 50, 275-281, 1988.

Ferguson, H. R. P. ``A Short Proof of the Existence of Vector Euclidean Algorithms.'' Proc. Amer. Math. Soc. 97, 8-10, 1986.

Ferguson, H. R. P. ``A Non-Inductive GL($n,Z$) Algorithm that Constructs Linear Relations for $n$ $Z$-Linearly Dependent Real Numbers.'' J. Algorithms 8, 131-145, 1987.

Ferguson, H. R. P. and Forcade, R. W. ``Generalization of the Euclidean Algorithm for Real Numbers to All Dimensions Higher than Two.'' Bull. Amer. Math. Soc. 1, 912-914, 1979.




© 1996-9 Eric W. Weisstein
1999-05-26