Mini challenge - coin toss - Printable Version +- HP Forums (https://archived.hpcalc.org/museumforum) +-- Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum-1.html) +--- Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum-2.html) +--- Thread: Mini challenge - coin toss (/thread-148792.html) Mini challenge - coin toss - MikeO - 03-21-2009 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 - Namir - 03-22-2009 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 - Namir - 03-22-2009 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 - Chris Dean - 03-22-2009 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 - Chuck Sommer - 03-22-2009 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 - Marcus von Cube, Germany - 03-22-2009 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 - Paul Dale - 03-22-2009 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 - Andrés C. Rodríguez (Argentina) - 03-22-2009 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 - coin toss - Michael de Estrada - 03-22-2009 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 - Andrés C. Rodríguez (Argentina) - 03-22-2009 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 - Namir - 03-22-2009 What would your code look like for an HP-67? Re: Mini challenge - coin toss - MikeO - 03-23-2009 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 - Namir - 03-23-2009 Does the hp97 code simulate random coin tosses? Re: Mini challenge - coin toss - Khanh-Dang Nguyen Thu-Lam - 03-23-2009 << 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 - Howard Owen - 03-23-2009 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 - Namir - 03-23-2009 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 - Howard Owen - 03-23-2009 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 - Namir - 03-23-2009 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 - Howard Owen - 03-23-2009 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 - Michael de Estrada - 03-23-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. Re: Mini challenge - coin toss - htom trites jr - 03-23-2009 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. Re: Mini challenge - coin toss - Khanh-Dang Nguyen Thu-Lam - 03-23-2009 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 - Gordon Strickland - 03-23-2009 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 - MikeO - 03-23-2009 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 - MikeO - 03-23-2009 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 - Palmer O. Hanson, Jr. - 03-23-2009 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 - Jeff Kearns - 03-23-2009 Palmer: Didn't you study engineering in university? Jeff Kearns Re: Mini challenge - coin toss - Palmer O. Hanson, Jr. - 03-23-2009 Quote: Palmer: Didn't you study engineering in university? Yes. University of Minnesota graduating in 1950. Re: Mini challenge - coin toss - Howard Owen - 03-24-2009 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 - Namir - 03-24-2009 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 - Walter B - 03-24-2009 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 - Namir - 03-24-2009 Had Mike described how the solution he is looking for works, we'd be more unified in our answers. Re: Mini challenge - coin toss - Howard Owen - 03-24-2009 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 - alternate PRNGs - Mike T. - 03-26-2009 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.