Democratic Underground Latest Greatest Lobby Journals Search Options Help Login
Google

Mmmmm Pi!

Printer-friendly format Printer-friendly format
Printer-friendly format Email this thread to a friend
Printer-friendly format Bookmark this thread
This topic is archived.
Home » Discuss » The DU Lounge Donate to DU
 
Xipe Totec Donating Member (1000+ posts) Send PM | Profile | Ignore Mon Oct-06-08 04:00 PM
Original message
Mmmmm Pi!
I just wrote a program to compute pi.

Generated the first 4,000 digits in 7 minutes....

Not a bad start...

http://www.youtube.com/watch?v=BUNDfyy2f5M
Printer Friendly | Permalink |  | Top
pokerfan Donating Member (1000+ posts) Send PM | Profile | Ignore Mon Oct-06-08 08:20 PM
Response to Original message
1. I once wrote a slow one using the Gregory-Leibniz expansion
π = 4 (1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + ...)

It was fun to watch it converge digit by digit.

Printer Friendly | Permalink |  | Top
 
Xipe Totec Donating Member (1000+ posts) Send PM | Profile | Ignore Tue Oct-07-08 10:12 PM
Response to Reply #1
2. I'm using Brent-Salamin, implemented in Scheme
The Brent–Salamin (or Salamin–Brent) algorithm was independently discovered in 1975 by Richard Brent and Eugene Salamin. It was used to compute the first 206,158,430,000 decimal digits of π on September 18 to 20, 1999.

It is Wicked fast, and can be implemented using only integer arithmetic (and matrix operations).

http://www.cs.umb.edu/~offner/files/pi.pdf




Printer Friendly | Permalink |  | Top
 
billyoc Donating Member (1000+ posts) Send PM | Profile | Ignore Tue Oct-07-08 11:25 PM
Response to Reply #2
4. What scheme do you use?
I've done a lot of work with Guile as a scripting lang for GNOME.
Printer Friendly | Permalink |  | Top
 
Xipe Totec Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 12:57 PM
Response to Reply #4
12. UMB Scheme
UMass Boston's implementation of R5RS.

It's basically plain vanilla scheme running on Solaris SunOS.

Printer Friendly | Permalink |  | Top
 
Dr. Strange Donating Member (1000+ posts) Send PM | Profile | Ignore Tue Oct-07-08 10:24 PM
Response to Reply #1
3. Damn, that's slow!
Printer Friendly | Permalink |  | Top
 
pokerfan Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 12:26 AM
Response to Reply #3
5. Well, you have to imagine it running on a 286
to fully appreciate its slowness. :)

It requires 1010 cycles to compute just ten decimal places.

Printer Friendly | Permalink |  | Top
 
struggle4progress Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 12:40 AM
Response to Reply #1
6. The only good thing I know about that expansion is this:
Theorem. Unique prime factorization holds for the Gaussian integers
Proof. π = 4 (1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + ...)
Printer Friendly | Permalink |  | Top
 
pokerfan Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 01:32 AM
Response to Reply #6
9. I like it because it's simple and easy to remember
Printer Friendly | Permalink |  | Top
 
Dr. Strange Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 09:20 AM
Response to Reply #6
11. Okay, I haven't seen this proof.
How does this expansion prove the UFDness of the Gaussian integers? Help a brother geek out.
Printer Friendly | Permalink |  | Top
 
struggle4progress Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 02:51 PM
Response to Reply #11
14. It's a consequence of the class number formula for imaginary quadratic fields
A quadratic field is a field F which has dimension two (when considered as a vector space over the rational field Q). A quadratic field is imaginary if it cannot be embedded in the real field R

Since we'll only consider imaginary quadratic fields, so below "field" always means "imaginary quadratic field." Some definitions and theorems hold in greater generality, but the Lounge doesn't care

An element r in the field F belongs to the ring of integers O(F) if r is a root of some monic polynomial with ordinary integer coefficients. "The ring of integers O(F)" really is a ring. Moreover, if r belongs to the ring O(F), then r actually satisfies a monic quadratic polynomial with ordinary integer coefficients: that is, we can find ordinary v and w (both ordinary integers) such that r^2 + u*r + v = 0

A fractional ideal J is a nontrivial and nonempty finitely-generated O(F)-submodule of F with the following additional property: there exists some nonzero r in O(F) such that rJ is an ideal in the ring O(F). If f is a nonzero element of F, then fO(F) is called the principal fractional ideal generated by f. Here rJ, for example, denotes the collection of all products r*j with j in J; similarly, fO(F) denotes the set of all products f*s with s in O(F). Notice that every "principal fractional ideal" is a fractional ideal

If I and J are fractional ideals, the "product of I and J" (denoted by IJ) the collection of all finite sums of elements i*j with i in I and j in J. This product operation makes the set of fractional ideals into an abelian group, in which the principal fractional ideals appear as a subgroup

The quotient of the group of fractional ideals by the principal fractional ideals is called the ideal class group. The ideal class group is finite

The size of the ideal class group is called the class number C(F). O(F) is a principal ideal domain if and only if C(F) = 1. Being geeks, we are therefore very interested to compute the class number. And, due to the nineteenth century heroism of Dirichlet, we have a formula for the class number!

Let n be a natural number. A Dirichlet character X is a map from the multiplicative semigroup Z/nZ (ordinary integers mod n) to the multiplicative semigroup C (complex numbers) of the following form: restricted to the group of units of Z/nZ, X is a group homomorphism to the nonzero complex numbers, and X is zero everywhere else. In other words, if p and q are relatively prime to n, the X(p*q mod n) = X(p mod n)*X(q mod n) with all terms nonzero; while if (n,p) > 1, we have X(p) = 0

Let X be a Dirichlet character. The Dirichlet L-function L(s,X) is defined by the infinite series
L(s,X) = X(1)/1^s + X(2)/2^s + X(3)/3^s + ...
The Legendre symbol is defined as follows: (a/p) = 1 if the equation x^2 = a mod p has a solution, and otherwise (a/p) = -1

Our field F, being imaginary quadratic, is obtained from Q by adjoining the square root of a negative squarefree integer -m. Define N = m if -m = 1 mod 4 and N = 4*m otherwise. We now produce and use a particular Dirichlet character, continuing to write X because this is the only Dirichlet character we will consider:
X(q mod N) = t(q)*(product of all Legendre symbols (q/p) where p is an odd prime dividing m)
where t(a) is defined as follows:
if -m = 1 mod 4 then t(a) = 1
if -m = 3 mod 4 and a = 1 mod 4 then t(a) = 1
if -m = 3 mod 4 and a = 3 mod 4 then t(a) = -1
if -m is even and (a = 1 mod 8 or a = 1 + m mod 8) then t(a) = 1 else t(a) = -1

Class Number Formula The class number is w(F)*sqrt(N)*L(1,X)/(2*pi) where w(F) is the number of roots of unity in the field F

Taking F = Q(i), we have O(F) = gaussian integers. Here, -m = -1 = 3 mod 4. Clearly, N = w(F) = 4 and sqrt(N) = 2. There are no odd primes dividing m, so X(q) = t(q) using the usual convention that an empty product represents 1
and of course in this case t(q) = 1 when q = 1 mod 4, t(q) = -1 when q = 3 mod 4
The formula tells us that the class number is

4*2*L(1,X)/(2*pi) = (4/pi)*L(1,X)
= (4/pi)*(X(1)/1 + X(2)/2 + X(3)/3 + ... )
= (4/pi)*(X(1)/1 + X(3)/3 + X(5)/5 + X(7)/7 + ... )
= (4/pi)*(1 - 1/3 + 1/5 - 1/7 + ... )
even index terms dropping out since the index is not invertible mod 4

Left side is an integer, so it would be enough to compute the right side to an accuracy of better than 0.5; but in this case, we can actually just call on Leibniz. So the class number is one, and the Gaussian integers is a principal ideal domain. QED


Discussion based on: Number Theory I: Fermat's Dream, Kazuya Kato et al, Translations of Mathematical Monographs #186, AMS, 2000
The original Dirichlet-Dedekind (translated by J Stillwell) is: Lectures on Number theory, PGL Dirichlet, History of Mathematics #16, AMS, 1999

Printer Friendly | Permalink |  | Top
 
Dr. Strange Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 08:58 PM
Response to Reply #14
19. Ah, the class number.
Memories of Algebraic Number Theory (some of which were pleasant).
Printer Friendly | Permalink |  | Top
 
struggle4progress Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 12:40 AM
Response to Reply #1
7. The only good thing I know about that expansion is this:
Theorem. Unique prime factorization holds for the Gaussian integers
Proof. π = 4 (1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + ...)
Printer Friendly | Permalink |  | Top
 
pokerfan Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 01:32 AM
Response to Reply #7
8. I like it because it's simple and easy to remember
Printer Friendly | Permalink |  | Top
 
struggle4progress Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 05:07 PM
Response to Reply #8
15. It's pretty
Printer Friendly | Permalink |  | Top
 
pokerfan Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 05:25 PM
Response to Reply #15
17. Isn't it?


It's endlessly fascinating how simple integer series can converge to irrational numbers. There's something divine about that.

Now where's my copy of Petr Beckmann? I need some meditation time.

Printer Friendly | Permalink |  | Top
 
pokerfan Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 05:12 PM
Response to Reply #1
16. delete
Edited on Wed Oct-08-08 05:22 PM by pokerfan
wrong place
Printer Friendly | Permalink |  | Top
 
puerco-bellies Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 02:53 AM
Response to Original message
10. Brain hurt now..
Went to Wikipedia entry for pi..
BTW congratulations on a scary smart bit of code.
Printer Friendly | Permalink |  | Top
 
Xipe Totec Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 07:18 PM
Response to Reply #10
18. Here is a fun game:
This online tool allows you enter a name (or any other short alphabetic string) and see if it appears
encoded in the first four billion binary digits of Pi:

http://pi.nersc.gov/

Neither my first name, nor my last name are encoded in the first four billion binary digits of Pi.



Printer Friendly | Permalink |  | Top
 
bicentennial_baby Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 09:14 PM
Response to Reply #18
22. My middle name does...cool:
search string = "jeanne"
30-bit binary equivalent = 010100010100001011100111000101

search string found at binary index = 1800594005
binary pi : 0000110001010001010000101110011100010111001111111111011000011110
binary string: 010100010100001011100111000101
character pi : efdhqhpny;;ksnzpljeanney:;xob,qraojuqq
character string: jeanne

Printer Friendly | Permalink |  | Top
 
pokerfan Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 09:19 PM
Response to Reply #22
23. 'W sucks'
search string = "wsucks" found at binary index = 2536399061
character pi: o_gkrsvfbrwszabvhwsucksrwvqivz;,-.;.ji

Printer Friendly | Permalink |  | Top
 
pokerfan Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 09:11 PM
Response to Reply #10
21. If you had enough curiosity to do that
Find yourself a copy a Beckmann's book.

A History of Pi
by Petr Beckmann
ISBN: 0312381859

Eve's Rating: *****

This is an incredible book. Beckmann traces the history of Pi from the ancient Babylonians (2000 BC) to near-modern times (1970s) and shows the parallels between the history of Pi, the history of mathematics, and the history of civilization. Beckmann tends to go off on lively tangents (e.g., how Roman "thugs" hindered mathematical progress), but I think this makes the story more interesting.

I highly recommend this book, regardless of your mathematical background. If you already love Pi, this will only strengthen your admiration for the number. If you merely have a mild curiosity about Pi, this story will whet your appetite.

http://www.eveandersson.com/pi/books


Printer Friendly | Permalink |  | Top
 
Occam Bandage Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 01:01 PM
Response to Original message
13. I did too!
10 PRINT "3.14159265358979323846..."
Printer Friendly | Permalink |  | Top
 
kedrys Donating Member (1000+ posts) Send PM | Profile | Ignore Wed Oct-08-08 08:59 PM
Response to Original message
20. ...slow night...?
:P

Very cool though. :hi:
Printer Friendly | Permalink |  | Top
 
DU AdBot (1000+ posts) Click to send private message to this author Click to view 
this author's profile Click to add 
this author to your buddy list Click to add 
this author to your Ignore list Wed May 01st 2024, 08:11 PM
Response to Original message
Advertisements [?]
 Top

Home » Discuss » The DU Lounge Donate to DU

Powered by DCForum+ Version 1.1 Copyright 1997-2002 DCScripts.com
Software has been extensively modified by the DU administrators


Important Notices: By participating on this discussion board, visitors agree to abide by the rules outlined on our Rules page. Messages posted on the Democratic Underground Discussion Forums are the opinions of the individuals who post them, and do not necessarily represent the opinions of Democratic Underground, LLC.

Home  |  Discussion Forums  |  Journals |  Store  |  Donate

About DU  |  Contact Us  |  Privacy Policy

Got a message for Democratic Underground? Click here to send us a message.

© 2001 - 2011 Democratic Underground, LLC