The Museum of HP Calculators

HP Forum Archive 19

[ Return to Index | Top of Index ]

Mini challenge - coin toss
Message #1 Posted by MikeO on 21 Mar 2009, 7:54 p.m.

You want to play a game that requires a coin toss, but you have no coins to toss. Fortunately, you have your trusty HP-67 or (fill in your favorite classic HP programmable calculator.)

Create the shortest program you can that will provide a randomized coin toss result.

-Mike

Edited: 21 Mar 2009, 8:07 p.m.

      
Re: Mini challenge - coin toss
Message #2 Posted by Namir on 22 Mar 2009, 9:35 a.m.,
in response to message #1 by MikeO

Here is a starting point for the HP-67:

LBL A
PI
+
3
Y^X
FRAC
STO A
2
*
INT
R/S
RCL A
GTO A

To operate: 

Set the display mode to DSP 0 and then perform the following steps:

1. Enter a seed value and press [A].
2. The program displays 1 for head and 0 for tail.
3. Press R/S to see the next head or tail value.

The program uses register A to maintain the current pseudo-random number.

I think you can shorten the program if you use a less-than-obvious steps to generate the random numbers.

Namir

Edited: 22 Mar 2009, 9:48 a.m.

      
Re: Mini challenge - coin toss
Message #3 Posted by Namir on 22 Mar 2009, 9:52 a.m.,
in response to message #1 by MikeO

Here is a shorter version for the HP-67:

LBL A
1/X
FRAC
STO A
2
*
INT
R/S
RCL A
GTO A

Using 1/X to generate a random number for a coin toss "might" be an acceptable trick. Initial seed should be 0.1 < seed < 0.9 AND 1/seed <> integer. Avoid "nice" fractions that lead to reciprocals that are integers.

Here is an HP-41C version (which is 1 step shorter than the HP-67 version shown above) that does not use any memory registers, except the stack:

LBL COIN
1/X
FRC
STO Y
ST+ X
INT
STOP
X<>Y
GTO COIN

To start the program, set FIX 0, enter a seed value (0.1 < seed < 0.9 AND 1/seed <> integer), and execute the command XEQ COIN. You get the first coin toss. Press the [R/S] key to view subsequent coin tosses.

Namir

Edited: 22 Mar 2009, 11:04 a.m.

            
Re: Mini challenge - coin toss
Message #4 Posted by Chris Dean on 22 Mar 2009, 2:58 p.m.,
in response to message #3 by Namir

Here is my solution for the 15c

g RAN#
.
5
+
g INT

0 represents Heads or Tails 1 the other. This of course assumes
the coin does not land on its side, it is evenly balanced and therefore a toss of the coin may be represented by the Uniform distribution.

There is no need for a label just press R/S.

Edited: 22 Mar 2009, 3:01 p.m.

                  
Re: Mini challenge - coin toss
Message #5 Posted by Paul Dale on 22 Mar 2009, 5:13 p.m.,
in response to message #4 by Chris Dean

And a step shorter is:

    g RAN#
    2
    *
    INT

And on a 41 with games module: 

    XEQ RNDM
    ST+ X
    INT

or even: 

    2
    XEQ RNDMW

- Pauli

                  
Re: Mini challenge - coin toss
Message #6 Posted by Namir on 22 Mar 2009, 8:49 p.m.,
in response to message #4 by Chris Dean

What would your code look like for an HP-67?

                  
Re: Mini challenge - coin toss
Message #7 Posted by Gordon Strickland on 23 Mar 2009, 7:16 p.m.,
in response to message #4 by Chris Dean

Message #4 notes that one must exclude from the analysis the possibility that the coin lands and stays balanced on its edge. It is perhaps equally important to exclude the possibility of a passing magpie snatching the coin in mid-air and making off with it.

                        
Re: Mini challenge - coin toss
Message #8 Posted by Palmer O. Hanson, Jr. on 23 Mar 2009, 9:03 p.m.,
in response to message #7 by Gordon Strickland

Quote:
Message #4 notes that one must exclude from the analysis the possibility that the coin lands and stays balanced on its edge.
Here's an old coin flip story from my college days. An engineer and his date were trying to decide whether to go dancing or to a movie. His date said "Heads we go to a movie; tails we go dancing." The engineer asked "What if the coin stands on its edge?" His date replied "Then, we'll take a hotel room for the night." The engineer flipped the coin, it rolled into a crack in the sidewalk and came to rest standing on its edge. His date suggested "Shouldn't we make it two out of three?"

Palmer

                              
Re: Mini challenge - coin toss
Message #9 Posted by Jeff Kearns on 23 Mar 2009, 9:18 p.m.,
in response to message #8 by Palmer O. Hanson, Jr.

Palmer: Didn't you study engineering in university?

Jeff Kearns

                                    
Re: Mini challenge - coin toss
Message #10 Posted by Palmer O. Hanson, Jr. on 23 Mar 2009, 10:17 p.m.,
in response to message #9 by Jeff Kearns

Quote:
Palmer: Didn't you study engineering in university?
Yes. University of Minnesota graduating in 1950.
      
Re: Mini challenge - coin toss
Message #11 Posted by Chuck Sommer on 22 Mar 2009, 3:05 p.m.,
in response to message #1 by MikeO

My solution uses a TI-84 Plus silver edition. Take the calculator and toss it in the air to land on the floor with a randomizing rotational motion about it's long axis. Face up is heads, face down is tails. I would never suggest using one of our precious HPs for this task.

Chuck

            
Re: Mini challenge - coin toss
Message #12 Posted by Marcus von Cube, Germany on 22 Mar 2009, 4:07 p.m.,
in response to message #11 by Chuck Sommer

A voyager will allow a longer series of tosses than any TI.

Edited: 24 Mar 2009, 3:40 a.m.

      
Re: Mini challenge - coin toss
Message #13 Posted by Andrés C. Rodríguez (Argentina) on 22 Mar 2009, 5:31 p.m.,
in response to message #1 by MikeO

While it is possible to use the linear congruential method to create pseudorandom sequences of the form

x(i) = FRAC ((x(i-1) * a + b)

as some of the answers to this challenge suggested, not every value for "a" and "b" gives acceptable random behavior.

The matter is throughly discussed in Knuth's "Art of Computer Programming", Vol 2. There, you can find a nice example of a complex and apparently good random generator which, after a few cycles, begins to oscillate within a few answers that repeat themselves in an obviously non-random manner.

Knuth dixit: "Never use a random method to generate random numbers"

One of the better tests for randomness is the "Spectral test", also discussed in the same book.

HP took care, when creating pseudorandom generators, in the HP 25 Applications Manual, and in the HP 41 Standard Pac, to publish programs that pass the Spectral test. I have long memorized them, and used them from time to time. While they are not the shortest, they are short (and fast) enough for usual purposes.

For the HP 41:

RCL 00
9821
*
.211327
+
FRAC
STO oo

For the coin toss, simply add:

2
*
INT

(An answer of 0 is "heads", an answer of 1 is "tails")

Of course, the pseudorandom "seed" can be any number between 0 and 1, stored in Register 00

            
Re: Mini challenge - alternate PRNGs
Message #14 Posted by Mike T. on 26 Mar 2009, 7:44 p.m.,
in response to message #13 by Andrés C. Rodríguez (Argentina)

I long ago memorised the following short(ish) pseudo random number generator routine for use on my HP33C.

I think this uses a seed value (.5284163) copied from a similar routine somewhere in the HP97 manual - I can't check that anymore and it might not even be the first number in the sequence generated by the HP97 pseudo random number routine, as I used it at the time because I found it the easiest to remember.

01 - 	     73	.
02 -         5	5
03 -         2       2
04 -         8       8
05 -         4       4
06 -         1       1
07 -         6       6
08 -         3       3
09 -  14 74       PAUSE
10 -         9       9
11 -         9       9
12 -         7       7
13 -       61        x
14 -  15 33       g FRAC
15 -  13 09       GTO 09

On re-reading the HP33C manual a couple of years ago I found a similar routine on page 66 with the same multiplier, but using a different seed value (.2315478).

Obviously by the time I stopped borrowing my father's HP97 and actually owned my first HP calculator I'd already given up reading the manuals or I might have decided to memorise a different seed value!

I do remember that the seed value was an important factor in determining the number of random numbers that the routine above would generate before beginning to repeat itself. (I guess that one day I'll have to try to find out if the seed given in the HP33C manual is actually any 'better' than the one I used).

Interestingly the more complicated routine given above for the later HP41C that allows the user to use any number between zero and one as a seed, also appears on page 67 of the HP34C Applications Guide.

Mike T.

      
Re: Mini challenge - coin toss
Message #15 Posted by Michael de Estrada on 22 Mar 2009, 7:07 p.m.,
in response to message #1 by MikeO

Did this on my HP-50g using the built-in clock to generate the random number instead of the RAND function. It also works on my HP-48SX.

<< TIME 10000 * FP 2 * IP >>

where TIME yields the current clock time, FP and IP take the fractional and integer parts of the number.

Michael

Edited: 22 Mar 2009, 7:43 p.m.

            
Re: Mini challenge - coin toss
Message #16 Posted by Khanh-Dang Nguyen Thu-Lam on 23 Mar 2009, 4:16 a.m.,
in response to message #15 by Michael de Estrada

<< TICKS 1 R->B AND >>

This one is shorter but gives an integer. Append B->R if you really need a real.

I guess it also provides more randomness than your version, at least on Saturn-based models because the clock tick is 1/8192. I don't know how the TICKS and TIME commands are emulated on ARM-based calcs.

The program above assume nothing about the wordsize (see the STWS and RCWS commands). If you assume the wordsize is 1 bit (e.g. run the << 1 STWS >> before), you can hardly write something shorter than:

<< TICKS >>

Again, append B->R if you really need a real.

                  
Re: Mini challenge - coin toss
Message #17 Posted by Michael de Estrada on 23 Mar 2009, 2:51 p.m.,
in response to message #16 by Khanh-Dang Nguyen Thu-Lam

I agree that your version is shorter, and it is also more elegant IMO. However, I don't think there is any difference in the "randomness" of the results from the two different approaches. If you are thinking that randomness somehow relates to precision, then there will be no difference between your method and mine. Your method requires the calculator to have slightly less than 4 significant digits for decimal fractions of a second. The internal precision is 12 decimal digits of which 6 are consumed for whole hours, minutes and seconds, leaving 6 digits for fractional seconds. Therefore, when a clock tick is converted to HMS format, there is no loss of accuracy.

As to what constitutes "randomness", perhaps one of the statistical mathematicians among us can propose a test.

Michael

Edited: 23 Mar 2009, 2:51 p.m.

                        
Re: Mini challenge - coin toss
Message #18 Posted by Khanh-Dang Nguyen Thu-Lam on 23 Mar 2009, 5:29 p.m.,
in response to message #17 by Michael de Estrada

I just meant if you run your program in a loop, for example:

<< 1 100 START YOURPROGRAM NEXT >>

then, the sequence will be even more predictable than with my method.

Edited: 23 Mar 2009, 5:36 p.m.

      
Re: Mini challenge - coin toss
Message #19 Posted by Andrés C. Rodríguez (Argentina) on 22 Mar 2009, 8:04 p.m.,
in response to message #1 by MikeO

Youi can throw your calculator into the air, and see if it hits the floor with the keyboard facing up or down... :-)

Eventually, if this is too hard to consider, just throw the batteries into the air...

      
Re: Mini challenge - coin toss
Message #20 Posted by MikeO on 23 Mar 2009, 12:39 a.m.,
in response to message #1 by MikeO

Some creative answers so far.

Namir provides both HP67 and HP41 versions. Andrés provides both an algorithm and a practical alterative when batteries are low, or missing - simply toss the calculator. Hilarious. Michael de Estrada provides a quick RPL version.

Here's my contribution (RPN) for HP97 - 2 lines: 

001 X<->Y     -41
002 GTO(i)  22 45
To run: store -1 in register I, then 0 Enter 1. Then press R/S to flip and R/S to view it. Repeat as often as needed.

Edited: 23 Mar 2009, 1:05 a.m.

            
Re: Mini challenge - coin toss
Message #21 Posted by Namir on 23 Mar 2009, 2:59 a.m.,
in response to message #20 by MikeO

Does the hp97 code simulate random coin tosses?

                  
Re: Mini challenge - coin toss
Message #22 Posted by Howard Owen on 23 Mar 2009, 4:29 a.m.,
in response to message #21 by Namir

The randomness derives from the precise time you press R/S the second time. The coin toss will be as random as the choice of time interval between presses of r/s is. If you make that choice based on some physically random event like radioactive decay, this program will pass the spectral test with flying colors :)

Regards,
Howard

                        
Re: Mini challenge - coin toss
Message #23 Posted by Namir on 23 Mar 2009, 6:30 a.m.,
in response to message #22 by Howard Owen

Ok, I see. The R/S simply interrupts the program execution showing either 0 or 1.

Interesting solution, making the user as part of the program!

Edited: 23 Mar 2009, 8:02 a.m.

                              
Re: Mini challenge - coin toss
Message #24 Posted by Howard Owen on 23 Mar 2009, 12:32 p.m.,
in response to message #23 by Namir

I'd be tempted to say that this approach is cheating, except the author is the one that posed the challenge in the first place!

Regards,
Howard

                                    
Re: Mini challenge - coin toss
Message #25 Posted by Namir on 23 Mar 2009, 12:51 p.m.,
in response to message #24 by Howard Owen

I agree. Mike should have been a bit more specific about how to write the solution. Using machines with random number generators saves many steps. Also I coded my solution to run as a proper program.

Namir

                                          
Re: Mini challenge - coin toss
Message #26 Posted by Howard Owen on 23 Mar 2009, 1:48 p.m.,
in response to message #25 by Namir

I dunno, Namir.

Quote:
Create the shortest program you can that will provide a randomized coin toss result.

The 2 line program does fit the given criteria. Of course, like I implied, that's what you would expect from the poser of the challenge. :)

It appears to me that a solution of this kind is not possible on the 41C in two steps. The best you could do would be three lines:

LBL 01
X<>Y
GTO 01

Where we use a short form GTO for speed. But this program needs one less setup step - the preloading of the i register.

On the 35S, a similar program is: 

R001 LBL R
R002 X<>Y
R003 GTO R002

Still 3 lines, but you could say the initial label isn't actually used, and that this is really a 2 line program. Except you probably couldn't since the label is mandatory. Let's say this is a 2.5 line program. :)

Regards,
Howard

                                    
Re: Mini challenge - coin toss
Message #27 Posted by MikeO on 23 Mar 2009, 8:20 p.m.,
in response to message #24 by Howard Owen

Quote:
I'd be tempted to say that this approach is cheating, except the author is the one that posed the challenge in the first place!

Regards,
Howard

Hey, hey! I resemble that remark! ;)

                                          
Re: Mini challenge - coin toss
Message #28 Posted by Howard Owen on 24 Mar 2009, 3:44 a.m.,
in response to message #27 by MikeO

Quote:
Hey, hey! I resemble that remark! ;)

Hee hee. But I stopped short of actually calling it cheating :)

Regards,
Howard

                                                
Re: Mini challenge - coin toss
Message #29 Posted by Namir on 24 Mar 2009, 9:58 a.m.,
in response to message #28 by Howard Owen

I think in future challenges, the author of the challenge should specify how the solution works (whether to write a program or a set of keystrokes)--what to input and what and HOW you get the output.

Namir

Edited: 24 Mar 2009, 10:00 a.m.

                                                      
Re: Mini challenge - coin toss
Message #30 Posted by Walter B on 24 Mar 2009, 2:12 p.m.,
in response to message #29 by Namir

Come on, isn't it part of the fun to see the different approaches -- or using another word: to see the Ansatz ;)

I won't regulate too much. But that's strictly my personal opinion.

                                                            
Re: Mini challenge - coin toss
Message #31 Posted by Namir on 24 Mar 2009, 3:20 p.m.,
in response to message #30 by Walter B

Had Mike described how the solution he is looking for works, we'd be more unified in our answers.

                                                                  
Re: Mini challenge - coin toss
Message #32 Posted by Howard Owen on 24 Mar 2009, 3:59 p.m.,
in response to message #31 by Namir

What's the point of being unified? A lot of the fun is seeing lots of different approaches and interpretations. I'm normally an observer on these challenges, but I love to read them because I usually learn something about the math and the calculators. Mike's solution made me think about the difference between random and pseudo random processes.

Obviously, we rely on pseudo random processes in computation because a reliable source of dynamic disorder isn't usually available. You can't have a geiger counter and radioactive source built in to every mobile and stationary computing device. And we also may need randomness at a rate far greater than nature can conveniently provide, such as in Physics simulations on a supercomputing cluster.

So Mike's solution won't work in those cases. But it could be useful in the case where all you need is a literal toss of a coin. It could even produce a better random series than any pseudo random algorithm, again depending on the method you use to choose the interval between key presses.

On the other hand, I found that I kept getting the same answer with my key presses because I had an unconscious rhythm going. On my HP41, the numbers were oscillating slowly enough that this rhythm would result in a long series of 1s or 0s before it drifted out of phase far enough to flip over to the other state. If I tried to consciously vary the frequency of my key presses, I got better results. But that made me think about how I was choosing my intervals. Was it truly random? Since it was based on a cognitive process, I'll bet not.

So that's an awful lot of thought generated by all the solutions presented here and especially by the attendant discussions. And that means all the solutions and all the discussion. None of the attempts to solve the more conventional (and useful) case of pseudo random number generation are invalidated by a clever solution addressing a different level of the problem.

Regards,
Howard

Edit: Another benefit to a pseudo random process is that it is repeatable. Physically random process by definition do not repeat indefinitely. (You could record and play back such a sequence, however.)

Edited: 24 Mar 2009, 4:04 p.m.

                              
Re: Mini challenge - coin toss
Message #33 Posted by MikeO on 23 Mar 2009, 8:33 p.m.,
in response to message #23 by Namir

Quote:
Interesting solution, making the user as part of the program!

The solution occurred to me as a direct analogue of flipping a coin - with the program simulating the spinning coin, and hitting R/S simulating the toss and catching of the coin.

Although a bit tongue-in-cheek, I think the technique might be a good way to randomize a seed value in some way on machines that don't have built-in random number routines.

I noticed you had a couple different formulas for pseudo random number generators. These are interesting.

Thanks Namir!

Edited: 23 Mar 2009, 9:18 p.m.

      
Re: Mini challenge - coin toss
Message #34 Posted by htom trites jr on 23 Mar 2009, 3:54 p.m.,
in response to message #1 by MikeO

Random from a computer is beyond hard. You can get beyond some of the simple woes using a version of the Von Neumann Coin procedure. 

Begin
Repeat
 R1 <-- random(head,tail);
 R2 <-- random(head,tail);
Until R1 <> R2;
Return R1 
End
This strips out simple constant biases towards head or tail (actual coins are usually slightly biased to head.) The procedure is not perfect, however.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall