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

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 >>

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

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