Mini challenge - coin toss



#2

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.


#3

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.

#4

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.


#5

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.


#6

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

#7

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

#8

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.


#9

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


#10

Palmer: Didn't you study engineering in university?

Jeff Kearns


#11

Quote:
Palmer: Didn't you study engineering in university?

Yes. University of Minnesota graduating in 1950.
#12

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


#13

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

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

#14

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


#15

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.

#16

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.


#17

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


#18

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.


#19

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.

#20

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

#21

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.


#22

Does the hp97 code simulate random coin tosses?


#23

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


#24

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.


#25

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


#26

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


#27

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

#28

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! ;)


#29

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

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

Regards,
Howard


#30

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.


#31

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.


#32

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


#33

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.

#34

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.

#35

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.

Possibly Related Threads...
Thread Author Replies Views Last Post
  HPCC Mini Conference 2013 hugh steers 6 440 09-13-2013, 04:27 PM
Last Post: BruceH
  Picture from the Mini-HHC (LA) Geir Isene 11 660 07-07-2013, 01:06 PM
Last Post: Jim Horn
  My birthday, so a little commemorative mini-challenge ! Valentin Albillo 43 1,989 03-07-2013, 03:44 AM
Last Post: Walter B
  WP 34S mini-challenge (B) Gerson W. Barbosa 17 836 12-27-2012, 04:39 PM
Last Post: Marcus von Cube, Germany
  Mini-challenge: HHC2012 RPL programming contest with larger input David Hayden 14 821 10-05-2012, 10:36 PM
Last Post: David Hayden
  HP41 / SY41CL Mini-B USB Power Connector (Module) Matt Kernal 5 1,086 07-08-2012, 06:23 PM
Last Post: Diego Diaz
  HP-15C (& LE!) 11-11-11 Mini-Challenge Valentin Albillo 28 1,259 11-14-2011, 08:12 AM
Last Post: Valentin Albillo
  Mini challenge. CEIL / FLOOR in RPN M. Joury 47 2,165 10-31-2011, 10:11 AM
Last Post: M. Joury
  A simple wp34s mini-challenge Gerson W. Barbosa 29 1,384 06-29-2011, 06:02 PM
Last Post: Guenter Schink
  HP-15C mini-challenge (Project Euler - problem #1) Gerson W. Barbosa 14 726 05-08-2011, 11:08 AM
Last Post: Marcus von Cube, Germany

Forum Jump: