▼
Posts: 1,619
Threads: 147
Joined: May 2006
What's Pi day with out a Pi computation?
Yes, there have been a few short and fast solutions posted in this forum to compute Pi, but what about something painfully slow?
I submit for your consideration:
1 LBL A
2 0
3 STO 0
4 STO 1
5 LBL 0
6 RAN#
7 RAN#
8 ->P # P is for Pythagoras
9 1
10 TEST 9 # x>=y
11 STO+ 1
12 0
13 1
14 STO+ 0
15 RCL 1
16 RCL/ 0
17 4
18 *
19 PSE
20 GTO 0
IANS, 2 random numbers are generated. The numbers represent the x and y coordinates of a point. If the distance to the point from the origin is <= 1, then it lies within the unit circle and a counter is incremented.
The ratio of the area of the unit circle to the unit square is pi/4. To calculate simply divide the number of hits by the total number of attempts and multiple by 4.
The real question is how many Pi days will pass before the 15C gets all 10 digits?
Screenshot (last 10 minutes of activity):
Dynamic update of my run, refresh often.
Edited: 14 Mar 2007, 2:07 p.m. after one or more responses were posted
▼
Posts: 1,368
Threads: 212
Joined: Dec 2006
Pi meets Monte Carlo!
Neat!
I should set this up on Free42, which is very fast, and see how long it takes....
Les
▼
Posts: 1,619
Threads: 147
Joined: May 2006
If you want speed consider a DSE loop within the main loop. Allow 1000s of iterations before displaying results.
▼
Posts: 1,368
Threads: 212
Joined: Dec 2006
Actually, I just change the PSE to VIEW ST X and can watch the approximations race crazily past like in some sort of wild pi stopwatch!!!
I think you can do likewise on the real Free42 and watch the approximations click by a lot more quickly than if you pause the thing at each iteration--it is much faster, but obviously not nearly as fast as Free42 on handheld or PC.
Les
▼
Posts: 1,368
Threads: 212
Joined: Dec 2006
Since we are talking about probabilistic approximations of Pi, any out there up for an HP calc simulation of Buffon's Needle Problem?
▼
Posts: 325
Threads: 18
Joined: Jul 2006
Quote:
Since we are talking about probabilistic approximations of Pi, any out there up for an HP calc simulation of Buffon's Needle Problem?
A discussion of Buffon's problem, with RPN and RPL programs:
http://kiyoshiakima.tripod.com/funprogs/buffon.pdf
▼
Posts: 1,619
Threads: 147
Joined: May 2006
Posts: 1,368
Threads: 212
Joined: Dec 2006
I have run the original version of Egan's code (with the change of PSE to VIEW ST X) on Free42 on a Palm TX for a little over 2 hours.
The approximant to Pi is 3.14319940195 after 222,054 iterations.
I will run the PC version next. A lot faster I am sure.
Les
Posts: 1,619
Threads: 147
Joined: May 2006
Faster version (30 vs 18 iterations/minute):
1 LBL A
2 0
3 STO 0
4 STO 1
5 LBL 0
6 1
7 10^x
8 STO I
9 LBL 1
10 RAN#
11 RAN#
12 ->P
13 1
14 TEST 9 x >= y
15 STO+ 1
16 0
17 1
18 STO+ 0
19 DSE I
20 GTO 1
21 RCL 1
22 RCL/ 0
23 4
24 *
25 PSE
26 GTO 0
Posts: 3,229
Threads: 42
Joined: Jul 2006
How about this attempt:
001 LBL A
002 CLEAR REG
003 RAD
004 LBL 0
005 1
006 STO+I
007 RCL I
008 STO RAN#
009 RCL RAN#
010 1
011 0
012 *
013 COS
014 1
015 +
016 TEST 0 x<>0?
017 GTO 0
It is probably way faster to converge that the dart board approach.
- Pauli
Posts: 1,755
Threads: 112
Joined: Jan 2005
Hi, Egan:
Egan posted:
"The real question is how many Pi days will pass before the 15C gets all 10 digits?"
Assuming each "try" takes 2 seconds to complete, it will take on the order of 2.31 x 1015 days to get 10 correct digits. That's 6.34 x 1012 years, give or take a few thousand millennia, which is the asked number of 'Pi days' if there's one 'Pi day' a year.
Though HP-15C's battery life verges on the incredible, I guess the batteries would be utterly flat by then. The HP-15C would be flat. Heck, even the Earth would be flat by then !
More seriously, the HP-15C's random number generator has a much shorter period than necessary for so long a computation, so tries would start to badly repeat and some bias would be introduced which could affect results making it ultimately impossible even in theory to get 10 correct digits, no matter how long it would take.
Best regards from V.
Edited: 14 Mar 2007, 8:12 a.m.
▼
Posts: 1,368
Threads: 212
Joined: Dec 2006
In my high speed computations on Free42 I am noticing that very bias in the pseudorandom number generator. The thing can go thru one million or two million loops and will get stuck around 3.143 and won't budge from there....
Les
Posts: 1,619
Threads: 147
Joined: May 2006
Quote:
More seriously, the HP-15C's random number generator has a much shorter period than necessary for so long a computation, so tries would start to badly repeat and some bias would be introduced which could affect results making it ultimately impossible even in theory to get 10 correct digits, no matter how long it would take.
I was concerned about this as well. I should have stated hypothetical. Does any have a paper or URL to how the 15C generates random numbers?
▼
Posts: 776
Threads: 25
Joined: Jun 2007
At the risk of making your program even slower, it seems to me that you could randomize which random number(s) you are using to pick X and Y in order to reduce the effects of the finite length of the random number generator.
Easy way: after some number of loops (ideally, probably the length of the random number generator), insert an extra random call (or two or three or ...) between the one used to get X and then to get Y.
More work: generate a random number, pick a particular digit thereof (say, the fourth), generate that many random numbers before generating the one you will use. Do for both X and Y.
Without thinking too hard about it, this ought to greatly "lengthen" the generating sequence you are using.
Posts: 1,619
Threads: 147
Joined: May 2006
I have updated my initial screenshot to update dynamically. This will remain in effect until I kill it.
Posts: 901
Threads: 113
Joined: Jun 2007
I don't know how old the method which compares the number of "hits" within the circle to the total number of "shots" really is. It was discussed in A. K. Dewdney's column "Computer Recreations" in the April 1985 issue of Scientific American. Dewdney asked readers to send the results of 1000 "shots" to him.
The method appeared again in Michael Ecker's column "Easy Pieces" in the January 1991 issue of Algorithm. At that time graphing calculators had become available so the "shots" could be displayed on the screen as they occured. If the random number algorithm of a given machine yields uniformly distributed numbers then one would expect the screen should approach being completely filled as the number of "shots" is increased. That was true with my Radio Shack Model 100 and my TI-81 but not at all true with my Casio fx-7000G which had a random number generator problem. The random number generator problem waas fixed in the fx-7000GA.
All of this reminds me of John Von Neumann's admonition that "Anyone who considers mathematical methods of producing random numbers is, of course, in a state of sin."
▼
Posts: 1,619
Threads: 147
Joined: May 2006
I first encountered this method in Using MPI. MPI is the standard for parallel programming distributed memory supercomputers (a.k.a superclusters). As you can imagine 100s, 1000s, or 10s of 1000s of high-speed processors generating random numbers in parallel will crank out Pi to 10 digits much faster. Not surprisingly it still can take a relatively long time (a proper deterministic algorithm on a 15C will still best it). If you're ever interested in exploring the other side of the scientific computing spectrum, pick up this book, a cheap switch, a few cheap PCs, and Linux.
The Linux random number generator utilizes entropy to increase its randomness. Entropy sources include keyboard and mouse usage, disk I/O, and system interrupts. I have never tested how random this is, but it should be easy to test by simply generating a series of random bits and then trying to compress it.
Entropy should be possible on some calculators. The 50G should be able to create an entropy pool over time based on keystrokes, battery voltage, I/O, etc... Perhaps the 50G does this today. Probably not, it is unimportant for a handheld calculator to have a robust random number generator. Random numbers in Linux are critical for security. If I want to secure my 50G I'll just lock it in my office or car.
Back to the 15C. Instead of using random numbers we can assume that we have a random number generator with a perfect uniform distribution and at the same time we will assume that all numbers are generated at least once first before reoccurring similar to shuffling a deck of cards.
The smallest fraction that will generate Pi/4 is:
1570796327
----------
2000000000
If we generate 2e9 points with an even distribution from 0,0 to 1,1 then we should get Pi faster by simulating the uniform distribution of the inevitable if we had a true random distribution. Points for x and y will range from 0 to 1 step 1/sqrt(2e9).
At 2 sec/iteration generating the 10 digits of Pi will only take ~ 126.75 years.
▼
Posts: 901
Threads: 113
Joined: Jun 2007
You wrote:
Quote:
The Linux random number generator utilizes entropy to increase its randomness. Entropy sources include keyboard and mouse usage, disk I/O, and system interrupts.
That got me thinking about the random number generator on the fx-7000G. It turned out that the mean value and distribution of 1000 random numbers from a program on that machine would vary when the execution time between subsequent calls of the random number generator was changed. I didn't think of it at the time, but could it have been that Casio was trying to enhance the randomness?
▼
Posts: 1,619
Threads: 147
Joined: May 2006
I know nothing about the fx-7000G. Does is have a clock or way to specify a delay?
▼
Posts: 901
Threads: 113
Joined: Jun 2007
Quote:
I know nothing about the fx-7000G. Does is have a clock or way to specify a delay?
It does not have a clock. I mechanized the delays by loops in the program. Since this is off-topic I suggest that if you want to pursue it further that you go to Viktor Toth's site at www.rskey.org/, go to the Library, go to Texas Instruments, go to TI PPC Notes and then look at page 13 of V10N4 and pages 8 and 9 of V11N1 to see all that I know about it.
|