▼
Posts: 121
Threads: 21
Joined: Jun 2008
You want to play a game that requires a coin toss, but you have no coins to toss. Fortunately, you have your trusty HP67 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.
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
Here is a starting point for the HP67:
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 pseudorandom number.
I think you can shorten the program if you use a lessthanobvious steps to generate the random numbers.
Namir
Edited: 22 Mar 2009, 9:48 a.m.
Posts: 2,247
Threads: 200
Joined: Jun 2005
Here is a shorter version for the HP67:
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 HP41C version (which is 1 step shorter than the HP67 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.
▼
Posts: 120
Threads: 9
Joined: Aug 2005
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.
▼
Posts: 3,229
Threads: 42
Joined: Jul 2006
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
Posts: 2,247
Threads: 200
Joined: Jun 2005
What would your code look like for an HP67?
Posts: 18
Threads: 0
Joined: Sep 2007
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 midair and making off with it.
▼
Posts: 901
Threads: 113
Joined: Jun 2007
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
▼
Posts: 222
Threads: 21
Joined: Oct 2006
Palmer: Didn't you study engineering in university?
Jeff Kearns
▼
Posts: 901
Threads: 113
Joined: Jun 2007
Quote:
Palmer: Didn't you study engineering in university?
Yes. University of Minnesota graduating in 1950.
Posts: 27
Threads: 1
Joined: Aug 2007
My solution uses a TI84 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
▼
Posts: 3,283
Threads: 104
Joined: Jul 2005
A voyager will allow a longer series of tosses than any TI.
Edited: 24 Mar 2009, 3:40 a.m.
Posts: 1,193
Threads: 43
Joined: Jul 2005
While it is possible to use the linear congruential method to create pseudorandom sequences of the form
x(i) = FRAC ((x(i1) * 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 nonrandom 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
▼
Posts: 282
Threads: 46
Joined: Jul 2005
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 rereading 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.
Posts: 1,665
Threads: 142
Joined: Jan 2009
Did this on my HP50g using the builtin clock to generate the random number instead of the RAND function. It also works on my HP48SX.
<< 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.
▼
Posts: 24
Threads: 4
Joined: Oct 2007
<< 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 Saturnbased models because the clock tick is 1/8192. I don't know how the TICKS and TIME commands are emulated on ARMbased 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.
▼
Posts: 1,665
Threads: 142
Joined: Jan 2009
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.
▼
Posts: 24
Threads: 4
Joined: Oct 2007
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.
Posts: 1,193
Threads: 43
Joined: Jul 2005
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...
Posts: 121
Threads: 21
Joined: Jun 2008
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.
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
Does the hp97 code simulate random coin tosses?
▼
Posts: 1,830
Threads: 113
Joined: Aug 2005
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
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
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.
▼
Posts: 1,830
Threads: 113
Joined: Aug 2005
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
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
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
▼
Posts: 1,830
Threads: 113
Joined: Aug 2005
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
Posts: 121
Threads: 21
Joined: Jun 2008
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! ;)
▼
Posts: 1,830
Threads: 113
Joined: Aug 2005
Quote:
Hey, hey! I resemble that remark! ;)
Hee hee. But I stopped short of actually calling it cheating :)
Regards, Howard
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
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.
▼
Posts: 4,587
Threads: 105
Joined: Jul 2005
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.
▼
Posts: 2,247
Threads: 200
Joined: Jun 2005
Had Mike described how the solution he is looking for works, we'd be more unified in our answers.
▼
Posts: 1,830
Threads: 113
Joined: Aug 2005
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.
Posts: 121
Threads: 21
Joined: Jun 2008
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 tongueincheek, I think the technique might be a good way to randomize a seed value in some way on machines that don't have builtin 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.
Posts: 66
Threads: 2
Joined: Aug 2007
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.
