From: Jonathan Aldrich
Subject: Infinite data structure example
My idea was not nearly so creative as Dan's Turing machine, but you are
welcome to use it if you'd like. As stated on my homework, it computes
successive approximations to Pi using an algorithm that converges
quadratically.
2) This Haskell code computes a series of successive approximations to Pi.
The
series converges quadratically; that is, the number of significant
digits doubles from one element of the series to the next. As you
will see, this very quickly exhausts the precision of Haskell
floating point numbers.
I used a series documented in a recent Scientific American
article, and described in detail at
http://pw1.netcom.com/~hjsmith/Pi/PiWhy.html. The following
pseudocode should make the algorithm clear:
y = sqrt(0.5)
x = 0.5
for i = 1 to n do
y = (1 - sqrt(1 - square(y))) / (1 + sqrt(1 - square(y)))
x = square(1 + y) * x - 2^n * y
pi = 1/x
done
Here is the Haskell code that defines a series piapprox (along
with a couple of "helper series") that converges using this algorithm.
All three series are infinite:
-- helper square function
square x = x * x
-- sy represents successive y values in the pseudocode above. It
-- starts out being sqrt(0.5) and is recursively calculated.
sy = (sqrt 0.5) : syrest sy
where
syrest (y:ys) = (1 - sqrt(1 - square y))/(1 + sqrt(1 - square y))
: syrest ys
-- sx represents successive x values in the pseudocode above. It
-- starts out being 0.5 and is recursively calculated from there.
sx = 0.5 : sxrest sx (tail sy) 2
where
sxrest (x:xs) (y:ys) n2 =
(square (1+y) * x) - n2 * y : sxrest xs ys (n2*2)
-- the nth element of piapprox is 1/x[n]
piapprox = extractpi sx
where
extractpi (x:xs) = (1/x) : extractpi xs
We can test the code by taking the first 10 members of the series:
take 10 piapprox
[2.0, 2.91421, 3.14058, 3.14159, 3.14159, 3.14159, 3.14159,
3.14159, 3.14159, 3.14159]
As you can see, in only 4 steps we have approximated pi to 5
decimal places.