Ferguson-Forcade and PSLQ algorithm

----------------
Helaman Ferguson
----------------

<< Ferguson is exactly that abstract artist who fully possesses
and has cultivated his ability to express his mathematical
conceptions as sculpture. He has discovered the common ground
of mathematics and art upon which he has placed his own
creativity. >>

<< I refuse to be diminished by being described as just
a mathematician, by being described as just a sculptor
-- I persist in both >>

http://www.helasculpt.com/

--------------------------
Integer relation algorithm
--------------------------

<< Let x = (x1, x2, ... , xn) be a vector of real numbers. x is
said to possess an integer relation if there exist integers
ai not all zero such that a1x1 + a2x2 + ... + anxn = 0. By
an integer relation algorithm, we mean an algorithm that is
guaranteed (provided the computer implementation has sufficient
numeric precision) to recover the vector of integers ai, if it
exists, or to produce bounds within which no integer relation
can exist >>

<< The problem of finding integer relations among a set of
real numbers was first studied by Euclid, who gave an
iterative algorithm (the Euclidean algorithm), which when
applied to two real numbers, either terminates, yielding
an exact relation, or produces an infinite sequence of
approximate relations. The generalization of this problem
for n > 2 has been attempted by Euler, Jacobi, Poincare,
Minkowski, Perron, Brun, Bernstein, among others. However,
none of their algorithms has been proven to work for n > 3,
and numerous counterexamples have been found. The first
integer relation algorithm with the desired properties
mentioned above was discovered by Ferguson and Forcade in
1977. In the intervening years a number of other integer
relation algorithms have been discovered, including the
"LLL" algorithm, the "HJLS" algorithm, and the "PSOS"
algorithm. >>

http://www.cecm.sfu.ca/organics/papers/bailey/paper/html/node2.html

<< Brun's algorithm is a natural generalization of Euclid
anthyphairesis(*) from a pair of number to a list of numbers.
This generalization is rediscovered by almost everyone
working in this area. [..] Brun's algorithm can cycle and
does not always find relations. However, according to a
theorem of Forcade, Brun's algorithm find relations almost
everywhere. >>

(*) anthyphairesis means << continually subtracted in turn from >>

Analysis of PSLQ, an Integer Relation Finding Algorithm
Helaman R.P. Ferguson, David H. Bailey, and Steve Arno

-- See post PSLQ technical --

-------------------------
Algorithms of the century
-------------------------

David Bailey wrote

<< In January 2000, the PSLQ algorithm, which was developed
by Helaman Ferguson, Stephen Arno and myself, was named
one of the ten "algorithms of the century" by the editors
of the publication Computing in Science and Engineering >>

<< One notable recent result in this area was the discovery
in 1996, by myself, Peter Borwein and Simon Plouffe, of a
new formula(*) for the mathematical constant pi [..] This
formula has the remarkable property that it permits one to
directly calculate the n-th digit in the binary or hexadecimal
expansion of pi, without computing any of the first n-1 digits,
by means of a simple algorithm that can easily be implemented
on a personal computer. [..] Numerous other results of this
type have now been found in mathematics and physics >>

oo 1 4 2 1 1
(*) pi = sum ---- ( ------ - ------ - ----- - ------ )
i=0 16^i 8i + 1 8i + 4 8i + 5 8i + 6

---------------
Online articles
---------------

Paul Preuss
Algorithm for the Ages: Better Way to find Integer Relations
http://www.lbl.gov/Science-Articles/Archive/pi-algorithm.html
http://www.nersc.gov/news/bailey1-20-00.html

Science News online
Jazzing up Euclid's algorithm
http://www.sciencenews.org/20000212/mathtrek.asp

PSLQ Among Top 10 Algorithm Of The Century
http://www.unisci.com/stories/20001/0121006.htm