Gauss-legendre Algorithm

The Gauss-Legendre algorithm is an algorithm to compute the digits of π. The method is based on the individual work of Carl Friedrich Gauss (1777-1855) and Adrien-Marie Legendre (1752-1833) combined with modern algorithms for multiplication and square roots. It repeatedly replaces two numbers by their arithmetic and geometric mean, in order to approximate their arithmetic-geometric mean. The version presented below is also known as the Salamin-Brent algorithm; it was independently discovered in 1976 by Eugene Salamin and Richard Brent. It was used to compute the first 206,158,430,000 decimal digits of π on September 18 to 20, 1999, and the results were checked with Borwein's algorithm. 1. Initial value setting;
a = 1\qquad b = \frac{1}{\sqrt{2}}\qquad t = \frac{1}{4}\qquad p = 1
2. Repeat the following instructions until the difference of a and b is within the desired accuracy:
x = \frac{a + b}{2}
y = \sqrt{ab}
t = t - p(a-x)^2
a = x
b = y
p = 2p
3. π is approximated with a, b and t as:
\pi \approx \frac{(a+b)^2}{4t}
The algorithm has second order convergent nature, which essentially means that the number of correct digits doubles with each step of the algorithm.

 

<< PreviousWord BrowserNext >>
gilbert arthur a beckett
glaucus
george gordon, 1st earl of aberdeen
george hamilton gordon, 4th earl of aberdeen
gnucash
george robert aberigh mackay
gallon
gini coefficient
government communications headquarters
gerard hoffnung
gary powers
gospel of james
gene therapy
galatea
gulf of oman
gestapo
grammatical conjugation
gomoku
gegenschein
glyph
goth
girl group
global warming potential
grothendieck topology
greens
ghost in the shell
great internet mersenne prime search
game.com
general packet radio service
gnosis
georgian
georgian architecture
goshen, indiana
gallipoli
grammatical voice
gram staining
gram positive
gram negative
greyhound
geometric algebra
gate house
george benson
grigory barenblatt
grammatical tense