The Museum of HP Calculators

HP Forum Archive 17

[ Return to Index | Top of Index ]

Pi day - Calculate Pi on your 15C
Message #1 Posted by Egan Ford on 13 Mar 2007, 9:51 p.m.

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

      
Re: Pi day - Calculate Pi on your 15C
Message #2 Posted by Les Wright on 13 Mar 2007, 10:14 p.m.,
in response to message #1 by Egan Ford

Pi meets Monte Carlo!

Neat!

I should set this up on Free42, which is very fast, and see how long it takes....

Les

            
Re: Pi day - Calculate Pi on your 15C
Message #3 Posted by Egan Ford on 13 Mar 2007, 10:35 p.m.,
in response to message #2 by Les Wright

If you want speed consider a DSE loop within the main loop. Allow 1000s of iterations before displaying results.

                  
Re: Pi day - Calculate Pi on your 15C
Message #4 Posted by Les Wright on 14 Mar 2007, 5:10 a.m.,
in response to message #3 by Egan Ford

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

                        
Re: Pi day - Calculate Pi on your 15C
Message #5 Posted by Les Wright on 14 Mar 2007, 5:15 a.m.,
in response to message #4 by Les Wright

Since we are talking about probabilistic approximations of Pi, any out there up for an HP calc simulation of Buffon's Needle Problem?

                              
Re: Pi day - Calculate Pi on your 15C
Message #6 Posted by Kiyoshi Akima on 14 Mar 2007, 12:38 p.m.,
in response to message #5 by Les Wright

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

                                    
Re: Pi day - Calculate Pi on your 15C
Message #7 Posted by Egan Ford on 14 Mar 2007, 12:45 p.m.,
in response to message #6 by Kiyoshi Akima

Great stuff! Thanks.

                        
Re: Pi day - Calculate Pi on your 15C
Message #8 Posted by Les Wright on 14 Mar 2007, 7:26 a.m.,
in response to message #4 by Les Wright

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

      
Re: Pi day - Calculate Pi on your 15C
Message #9 Posted by Egan Ford on 13 Mar 2007, 10:55 p.m.,
in response to message #1 by Egan Ford

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
      
Re: Pi day - Calculate Pi on your 15C
Message #10 Posted by Paul Dale on 13 Mar 2007, 11:30 p.m.,
in response to message #1 by Egan Ford

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

      
Re: Pi day - Calculate Pi on your 15C
Message #11 Posted by Valentin Albillo on 14 Mar 2007, 8:09 a.m.,
in response to message #1 by Egan Ford

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.

            
Re: Pi day - Calculate Pi on your 15C
Message #12 Posted by Les Wright on 14 Mar 2007, 8:24 a.m.,
in response to message #11 by Valentin Albillo

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

            
Re: Pi day - Calculate Pi on your 15C
Message #13 Posted by Egan Ford on 14 Mar 2007, 10:43 a.m.,
in response to message #11 by Valentin Albillo

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?

                  
Re: Pi day - Calculate Pi on your 15C
Message #14 Posted by Dave Shaffer on 14 Mar 2007, 3:58 p.m.,
in response to message #13 by Egan Ford

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.

      
Re: Pi day - Calculate Pi on your 15C
Message #15 Posted by Egan Ford on 14 Mar 2007, 12:32 p.m.,
in response to message #1 by Egan Ford

I have updated my initial screenshot to update dynamically. This will remain in effect until I kill it.

      
Re: Pi day - Calculate Pi on your 15C
Message #16 Posted by Palmer O. Hanson, Jr. on 14 Mar 2007, 9:49 p.m.,
in response to message #1 by Egan Ford

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."

            
Re: Pi day - Calculate Pi on your 15C
Message #17 Posted by Egan Ford on 15 Mar 2007, 5:11 p.m.,
in response to message #16 by Palmer O. Hanson, Jr.

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.

                  
Re: Pi day - Calculate Pi on your 15C
Message #18 Posted by Palmer O. Hanson, Jr.. on 15 Mar 2007, 9:07 p.m.,
in response to message #17 by Egan Ford

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?

                        
Re: Pi day - Calculate Pi on your 15C
Message #19 Posted by Egan Ford on 17 Mar 2007, 2:31 a.m.,
in response to message #18 by Palmer O. Hanson, Jr..

I know nothing about the fx-7000G. Does is have a clock or way to specify a delay?

                              
Re: Pi day - Calculate Pi on your 15C
Message #20 Posted by Palmer O. Hanson, Jr. on 17 Mar 2007, 9:35 p.m.,
in response to message #19 by Egan Ford

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.


[ Return to Index | Top of Index ]

Go back to the main exhibit hall