Leave a comment

Comments 22

nancylebov October 2 2012, 11:46:00 UTC
I'm curious about why the digits in/digits out relationship for fractional approximation of pi is so tight.

Reply

andrewducker October 2 2012, 12:18:29 UTC
I'm going to guess it's because there's no pattern to the digits.

Data with no pattern is impossible to encode in a smaller amount of space, so it's probably a mathematical corollary of that.

*waits for a mathematician to turn up and tell him just how wrong he is*

Reply

simont October 2 2012, 12:41:30 UTC
No, that sounds about right to me. Generally, you expect that a rational approximation and a decimal approximation to the same value using the same number of digits will be about as accurate as each other (plus or minus a digit or so for fiddly edge cases), simply on the grounds that you've got about the same number of possible representations covering the same amount of space. Equivalently, if it worked any other way then you'd have a magic compression algorithm of the form "express your file as a decimal, convert to a fraction, aha! it takes fewer digits" or vice versa, and we know magic compressors can't exist by the obvious counting argument.

It's slightly more subtle than there being no pattern to the digits, in that some numbers with no obvious digit pattern can be encoded cheaply. (Proof: just evaluate small fractions until one doesn't have an obvious pattern, and you've found one! E.g. if you happened to want to approximate 0.052631578947365, you'd happen to be in luck, since it's extremely close to 1/19 ( ... )

Reply

nancylebov October 2 2012, 15:54:51 UTC
Thank you. I think I understand that.

I also looked at continued fractions a bit, and it's exceedingly weird that some of them shake out into simple patterns. Pi remains intractable, and I begin to admire its stubbornness.

Is there anything interesting about the fact that some uncompressible numbers can be expressed as simple concepts?

Reply


a_pawson October 2 2012, 12:19:03 UTC
That article about Pi brings back memories of my undergraduate days - specifically writing a FORTRAN program to calculate Pi using the Monte Carlo method. As I recall it was compiled and sent to run on what was the department's only "mainframe" computer - a behemoth the size of a room running VAX/VMS. I remember it took about 12 hours to run, and the output was only accurate to about 0.001%.

Ah memories - you could probably run the same calculation on a modern desktop in 10 seconds.

Reply

andrewducker October 2 2012, 12:52:06 UTC
I just grabbed the code for a simulation off the web, and put together a quick test program.

Running it for 10 seconds got me a difference of 0.0005. And then -0.0002, then -0.0005 and then 0.0001. An average of around 430,000 "throws" each run.

So your guess wasn't bad :->

Reply


drdoug October 2 2012, 21:04:51 UTC
Rational approximations of pi are no good.

You want something that'll give you a lot of digits of pi in a single shot. Like, for instance the integral from x=0 to infinity of cos(2x) *cos(x)*cos(x/2)*cos(x/3)*cos(x/4)... which matches pi/8 to 43 digits, and then doesn't. See this (fantastic) paper for explanation (http://www.ams.org/notices/201110/rtx111001410p.pdf [PDF, p1418). It turns out that this is the first term in a series expansion which does equal pi/8, and converges very, very quickly. One term gives you 43 digits, two terms give you 500!

Reply

simont October 3 2012, 08:55:32 UTC
But why would you go to all the effort of not only evaluating an infinite product of cosines but also integrating it from 0 to inf, just to get a measly 43 digits? If you're allowing your expression to contain transcendental functions at all then you might as well stop at 4*atan(1) = π exactly.

For an approximation to π to be useful, it has to be not only short to remember but also convenient to compute!

Reply

drdoug October 4 2012, 05:20:24 UTC
True! I wouldn't use that one in anger - I just came across it recently so it was uppermost in my mind when thinking about iterative methods for generating digits of pi. And as you point out, the iterative formulae used to generate vast numbers of digits of pi perform very well, but aren't exactly memorable by humans. (Evidence: I can't remember any off the top off my head, despite having played with this some years ago. :-) )

I always thought the 22/7 and 355/133 approximations were an ancient thing for people who weren't particularly comfortable with decimals. Or, less condescendingly, for people who were operating in a world where most sums were done in your head or by hand - multiplying by 22 then dividing by 7 is easier to do mentally or on paper than multiplying by 3.14.

The original linked article does mention the notion of pi being 'just over three' which I am slightly ashamed to admit is what I use for mental arithmetic estimates.

Reply

simont October 4 2012, 08:01:21 UTC
multiplying by 22 then dividing by 7 is easier to do mentally

I must say that for me the primary use of the 22/7 approximation is that if during a mental BOTEC I find the thing I want to multiply by π happens to be a multiple of 7 then I say "aha!" and multiply the same thing by 22 instead. The rest of the time, other approaches are easier.

For the kind of mental estimation where you're satisfied to merely get about the right order of magnitude, I find two very useful approximations are π ≈ sqrt(10), and that a year contains about π × 10^7 seconds. (The latter is particularly convenient for thinking about the Earth's orbital motion!)

Reply


ipslore October 4 2012, 03:08:55 UTC
I came here expecting to see some Orson Scott Card jokes, and was disappointed.

Reply


apostle_of_eris October 4 2012, 16:46:06 UTC
. . . for a disappointingly constricted value of "useless".
Math is "right" or "wrong"; engineering is good enough or not good enough: if it won't fall down, it's good enough, and 355/113 is good enough for a whole lot of uses.
So is 22/7.

Reply

andrewducker October 4 2012, 20:06:39 UTC
The point is that memorising 22/7 doesn't gain you anything. You're as well off memorising 3.14 - because it's the same number of digits, just as accurate, and you're memorising the thing you want to know, rather than some other set of numbers.

And the same goes for 355/113. Why memories _those_ digits rather than just remembering 3.141592? You're spending brain space memorising something that's not the thing you want to remember, for no gain.

Reply

apostle_of_eris October 4 2012, 20:38:51 UTC
"1-1-3-3-5-5" is a lot easier than "3-141592".
(I'm not going back to check, but I don't recall easy mnemonic from the piece.)

Reply


Leave a comment

Up