Looking over my program for computing the value of pi, I realized that the method I had labeled as 'classic' was actually a copy of the BBP method, so I set about correcting this mistake. Turns out the classic method (the infinite sum of alternating positive and negative fractions of ever decreasing magnitude) is poorly suited for implementation on a modern computer. Where all the other methods can calculate pi to the limit of the machine's precision in 25 steps or so, the classic method takes something like two trillion steps to get anywhere close. After a bit of futzing about, I find it gets pretty close after about two million steps. Up until then the difference between the computed value of pi and our reference value keeps getting smaller, but at that point it inexplicably gets larger. It starts getting smaller again, but nobody wants to wait for hours for a demo to run, so we call it quits.
Then I got to wondering just how do we know just what the digits of π are? A physical measurement is only going to get us a handful of digits. How do we know what the rest of the digits are? Well, you need to have a little faith. You come up idea of how it can be calculated, and then you implement that idea in a computer program, turn the machine on and let the program run. If it's a well behaved program it will run forever or until it runs into it's limitations (like my demo program) or it runs out of space to store the result. Asking for a zillion digits of π is like asking how far your car can drive. It's a machine and it will keep running until it breaks down. It's kind of pointless actually.
Still, it's a good exercise for the computationally inclined, kind of like target practice in archery.
The Ridiculous Way We Used To Calculate Pi
Veritasium
I'm thinking about how calculating a zillion digits of π is like the intellectual equivalent of peacock feathers (I am sure I am quoting someone here), or as the bald guy (Professor Alex Kontorovich from Rutgers) says:
So this goes way beyond precision for any practical purpose, this is now a matter of flexing your muscles, this is showing off just how much mathematical power you have that you can work out a constant like π to very high precision.
Then it comes to me that what we all want is to be entertained, something that absorbs all of our attention, because when our attention is totally occupied, we don't concern ourselves with boring stuff. We are occupied and we are entertained. And nothing captures our attention better than competition. Trying to beat the other guy is what everyone is striving for. Sometimes it's just a matter of slipping in the right word to stab an opponent with a nasty insult, sometimes it's just an embellishment to your clothing to catch someone's eye, often it's a matter of making more money. Competitions can become heated and result in pushing, escalate into fighting and eventually boil over into war. And when we go to war, there is no end to the complexity of the weapons we build, and when you are building complex weapons you need math, and so you might want the guys who display the intellectual equivalent of peacock feathers helping out on designing weapons.
I'm watching this video and I realize that I wrote a program to compute π using several different techniques, one of which was very similar to the method used in the beginning of the video of cutting up a circle into triangles. I thought I had posted it earlier, but I could not find it on my blog. I rooted around on my computer and found it (it's from 2012). I posted it on github.
My program uses floating point numbers to perform the calculations, so it is going to be limited to only a few digits of pi. I should modify it to use the GMP math package so I can get as many digits as Ludolph did.
I figured out why I don't do any web programming: it's not that interesting, at least not from a puzzle solving point of view. Putting up a web page mostly involves displaying a bunch of data. You might also want to collect some data from the user which you will pack up and send to the host, but it's all pretty straight forward. Now it might get a bit gnarly when you have to interact with a complex data base system residing on the server, but that's mostly a matter of minding your p's and q's in the protocol you use. Once you have a web page up, things could get a little complicated, but it takes a bit of work to get to that point.
I enjoy working on the programming puzzles on Coding Games because all that boring display stuff is cut out of the problem. On the downside, they ask that you don't publicize your solutions because their main purpose (aside from keeping me entertained) is to screen people as candidates for companies that want to hire programmers. Since the world is full of people who would be willing to pass off somebody else's work as their own, and I am opposed to that sort of thing, I keep my Coding Game solutions to myself.
When a puzzle shows up out in the real world that lends itself to being solved with a computer program, I am very happy. Plus I am free to share the results of my genius / obsession with the world.
The 10,958 Problem - Numberphile
I came across this video from Numberphile the other day talking
about using a sequence of digits in a mathematical expression and then, by changing the operators between the digits, you could end up with
pretty much any number you wanted. For instance:
Some
whiz kid who didn't have anything else to do compiled a list of
expressions for all the numbers up to 11,111. He found an expression
for every number except 10,958.
Not too long ago I wrote a program to solve a Coding Game
puzzle that involved computing the value for some simple expressions,
so that gets me to thinking that I could write a program to generate all
possible expressions using the same sequence of numbers and see if I
can find one that will produce 10,958. If I do, well, yahoo! But if I
don't, well at least I'll have some confirmation of this guy's results. I'm working on that. I'll let you know how it turns out. Assuming I get that far.
Meanwhile, at the beginning of the video, Matt Parker writes the expressions for some random numbers. How did he do that? Does he have some rule he follows that allows him to do this? No. He did it by memorizing the first one thousand expressions. Okay then. That is not something that interests me in the least. Matter of fact, it sounds downright painful. But it takes all kinds to make the world go round, so if that's how Matt wants to spend his time, well fine, go ahead on.
This memorization bit reminds me of a penance doled out to inmates of the cloister in Anathem by Neal Stevenson. If an inmate was found guilty of an infraction, the penance was to memorize a number of pages of a book that contained a zillion digits of pi. Minor infractions might be punished with memorizing a single page, but more severe infractions, or repeat offenders might be assigned entire chapters. I suppose there might be a feeling of accomplishment in being able to complete the assigned memorization, but it sounds awful to me.
There was also a show I saw once, it might have been an episode of The Twilight Zone, or maybe the tail end of Fahrenheit 451. In any case, the society had banned books, so a small group of dissidents had formed their own community. They lived in some shacks along a river, kind of reminded me of Tom Cruise's place in Oblivion. Anyway, their whole thing was memorizing books. Each person would memorize a book, and then they would teach their children the book and so the knowledge would be maintained without having to resort to the actual printed copy.
While we are on the subject of memorization, it recently occurred to me that merely having a pretty face and showing up (per Woody Allen) are not really enough to be an actor. Memorizing your lines and then being able to repeat them is a prime skill.
'Hitting your marks' is another one. That is, walk where you are supposed to walk, when you are supposed to. When shooting a scene, you need people to be in certain places so the audience will be able to see what is going on. Okay, this is a non-sequitur but I came across the phrase recently and it stuck with me. And since I am talking about actors, I thought I'd throw it in.
Being a successful actor might bring great financial rewards, which can bring great freedom, but getting there is going to be a lot of work. Some people have talents that lie in that direction, and that's good. They keep us entertained. Like I said, it takes all kinds to make the world go round.
One last word about books. We accumulated a number of books while the kids were growing up, but now they are gone and we are in material reduction mode, so a couple of weeks ago I started hauling them off to Powell's a couple of grocery bags at a time. I took a total of eight bags of books there. They bought maybe 6, 6 books for which I got about $20 in store credit. I hauled the rejects home and this weekend we had a garage sale. Out of maybe 200 books we sold about 10. We ended up taking the rest to Goodwill.
There are novels that are entertaining and you might read them once and once you have forgotten the story you might read them again. You might run into a few books that you will want to read again. There aren't too many of those. Most books aren't worth the paper they are printed on. Comes from paper being so cheap I suppose.
Stu turned me on to an obscure little math trick for determining if a number is a prime number or not. It's not generally useful as it involves factorials, which get really big really fast. But there is a computer math package that can deal with numbers of any size, as long as you have enough computer memory to accommodate them, so I thought I would take Stu's formula and the GMP math package and see if I could make them play together.
Dealing with really long numbers is not very difficult, you just have to keep track of overflows. Any half competent programmer should be able to write a set of routines to perform the basic operations, but it's a common enough job that some people got together and wrote a complete library of functions and procedures.
Like any bit of software there are rules for how to use it. For me the easiest way to learn these rules is find a sample piece of code and start messing with it, so I went looking and I found this: randPi.c by Mitch Richling, which to purports to make Pi out of nothing but random numbers. He uses the GMP library to deal with his really long random numbers, so it was good example to start with. Plus it was weird. Pi from nothin'? How can that be?
It depends on the observation that between any two random numbers, there is a statistical probability that they are relatively prime, i.e. the only factor they have in common is one. 3 and 4 are relatively prime. 3 and 6 are not, they have a factor of 3 in common. 4 and 6 are not, they have the factor 2 in common. Two numbers by themselves won't tell you much, but if you have big pile of them and start counting the number of pairs that are relatively prime and those that aren't, you end up with a ratio that (if you munge it just a bit) looks just like Pi.
I got to thinking about this and realized you don't really need random numbers. After all, random numbers are just one number out of a range of numbers. You run long enough and you will cover all numbers in the range. You should be able to get the same effect by just testing the relative primeness of all the numbers in a range. I wrote a small program to test this and it indeed works. Running a cross tabulation of all the numbers from 1 to ten thousand resulted in value of 3.141534, which is not bad considering I made it from nothin'.
Okay, we have GMP library and we think we know how to use it. Let's test Stu's formula, so I wrote another little program, it works and so Stu's formula seems to be valid. My program only goes up to 31, but that's only because we are starting to fill up the screen with the giant numbers that come from computing factorials. 31! (31 factorial) is like a zillion digits.
P.S. I have decided I don't like github because they don't handle tabs. Google Drive / Docs has a viewer that works okay and the two programs are stored there. It doesn't support highlighting, and there may be some argument over tabs, but it's not bad, and it doesn't require any extra fooling around.
A while back Stu put up a post that had a newish formula for computing the value of pi. Just for grins, I thought I would see if I could implement the formula in code, that is, write a computer program to compute the value of pi using this formula. I mean, you never know about these things. Sometimes you get formulas that look nice, but when you try and turn them into code you find out there is one piece of psycho-babble in the formula that cannot be implemented in any kind of straight forward manner. Anyway, I tried it and I was successful, and it did indeed compute an accurate value of pi. Bear in mind that accurate is a relative term.
It is claimed that this particular formula is unique in that it can compute any digit of pi without having to compute any of the previous digits. I tried to figure out how this was being done. I failed. The formula computes a series of values and each value is added to the previous total. Each successive value makes the total a little bit more precise. Each successive value is several times smaller than the previous one, so if the first value computes the first digit, then the second value will have no effect on the first digit, but it will have an impact on the second digit, and so on. However, each value that is computed is an insane decimal number in it's own right, and so the string of digits to the right of the decimal point goes on indefinitely. So while computing the Nth value of this series will not effect earlier digits, the Nth digit is still going to be the sum of all the Nth digits from all the previously computed values.
I eventually figured out what they meant. Typically these formulas include a section that needs to be repeated several times in order to achieve the required accuracy. Most of these formulas require that after you have completed the necessary number of steps and have arrived at some total, you now subject this total to another formula for further manipulation. This newish formula does not require this second step.
I took a look at the article on Pi in Wikipedia and it has a whole list of formulas for calculating Pi. And that's when it struck me that although we have these formulas, we have no explanation for how they work. Matter of fact, all we have is someone's word that they do work. And how do you know what the 10,000th digit of Pi is anyway? You can only verify the value empirically (by measuring a physical circle) out to ten or maybe 20 digits. Beyond that we are talking the intellectual equivalent of peacock feathers: very pretty but totally useless. I imagine each one of these formulas was the result of someone's doctoral thesis in mathematics and the proof of each one is probably 400 pages of inscrutable squiggles. Presumably they can all be tested against each other by writing and running a computer program.
One of the formulas was developed by an Indian prodigy about 100 years ago. It is able to compute the value of pi to the limits of my machine in three steps. The new formula takes about a dozen steps.
So now I'm wondering if I can compute the value of pi straight up from nothing. The standard way to do something like this is to divide a circle into a bunch of triangles, like cutting up a pie, and then add the lengths of the bases of all the triangles. The smaller you make the triangles, the more closely the bases of these triangle will approximate the circle, and the closer you will get to the true value of pi. So I figured out how to calculate the base of ever smaller triangles using the pythagorean formula, and put it in a program, and in a couple dozen steps or so I had a pretty good approximation.
So I was thinking about that program for calculating the value of π that I posted yesterday, and I realized that the algorithm was quite capable of calculating the value of pi to an indefinite number of digits. The code would take some work, quit a bit of work actually, but feasible. The algorithm calculates a new value of x with every iteration. This new value of x starts 4 bits to the right of the place of the last value of x. So you could keep adding these new values of x to this string of bits for however long you wanted to. Eventually you would get tired or bored, or run out of disk space, but you could go quite a while.
The problem you would run into is that each value of x would be an infinitely repeating pattern, so you would have to keep replicating this pattern as you went, and with each iteration, the pattern would get longer. It might be necessary, or even easier to keep a separate pattern for each new value of x. Then when you get a new value of x, you add the appropriate section of each pattern to it and append that value to your infinitely extending value of pi.
There is going to be some point where the addition of the new x is not going to propagate any farther towards the binary point. Then you can say you know the value of pi to that point and can safely store it away.
Recognizing how many bits go into each pattern is going to be another trick. I imagine someone has already figured out how to do that.
Yesterday was pi day and Stu put up a post with a formula for calculating the value of pi, so naturally I had to try it out. This one promised to be a little better than the traditional one. I had written a program to implement that algorithm a while back, and while it worked, it was very slow to close in on the value of pi, requiring hundreds of iterations.
This formula closes in on pi in only 8 iterations. Well, it gets as close as it can. It is limited by the format of double precision floating point numbers.
/* Simple program to calculate the value of pi.
Original formula:
/ 4 2 1 1 \
16^-K * ( ------ - ------ - ------ - ------ )
\ 8K + 1 8K + 4 8K + 5 8K + 6 /
The caret (^) indicates raising to a power: 16^K means 16 to the power of K.
Multiplying by 16^-K is the same as dividing by 16^K
A double precision floating point number has 64 bits (8 bytes).
1 bit for the sign
11 bits for the exponent
52 bits for the mantissa
Three decimal digits require approximately 10 bits. 2^9 = 1 << 10 ~= 1024
We were able to get 13 decimal digits, which works out to about 43 bits.
The double angle brackets (<<) indicate a bitwise shift,
in this case to the left.
*/
#include <stdio.h>
#include <math.h>
int main(void)
{
int k;
int n;
double pi;
double x;
pi = 0;
for (k=0; k<8; k++)
{
n = 8 * k;
x = ( 4.0/(n + 1)
- 2.0/(n + 4)
- 1.0/(n + 5)
- 1.0/(n + 6))
/ (1 << (4 * k)); // 16^K
pi += x;
printf("%16.12f ", x);
printf("%16.12f\r\n", pi);
}
return 0;
}
Results:
x pi
3.133333333333 3.133333333333
0.008089133089 3.141422466422
0.000164923924 3.141587390347
0.000005067221 3.141592457567
0.000000187893 3.141592645460
0.000000007768 3.141592653228
0.000000000345 3.141592653573
0.000000000016 3.141592653589
My wife has been trying to teach some elementary school kids about perimeter and circumference. For circumference you need our old friend π (Pi): 3.14159... To illustrate this concept we came up with a little demonstration:
Take a can and make a mark on the rim. Make sure the can has a rim on the top and bottom. Otherwise it won't roll straight.
Place the can on its side on a sheet of paper with the mark at the bottom.
Make a corresponding mark on the paper.
Roll the can along for one revolution until the mark is at the bottom again.
Make another mark on the paper.
Measure the distance between the two marks.
Measure the diameter of the can.
Divide.
It worked out okay. They came up answers around 3.2 on their calculators. Considering their age and dexterity and the precision of their instruments, I think they did okay.
One web site I enjoy is Rocketboom.com. One video has the host(ess?) reciting the first billion or so digits of Pi:
All this talk about Pi got me to thinking. What if Pi isn't really an infinitely long number? What if it really stops after, say, ten digits or so? Would anyone be able to tell the difference? I know mathematicians would argue that no, no, no, it must go into infinity, but all they really have is their precious theories. I mean they don't have any real concrete evidence, do they? And what if their theories are wrong? Who would know?
Okay, I'm probably all wrong about this. I sure they have a whole set of interlocking explanations that tie back to the real world.
