Generating random numbers

[3iff]

Not a puzzle as such but a problem that should give some of you a few seconds thought.

I sometimes need to generate random numbers (up to 10 maximum) but don't have suitable dice to hand...but I do have a simple calculator.

How can I generate good quality random numbers? I do have a method which I'll reveal after I see some of your suggestions.

[Antrax]

Assuming you don't have shift + . to generate a random number like in my calculator, you can punch the calculator and then do cos, sin or something of the sort, it should be fairly random in the [-1, 1] range and then you just add 1 and multiply by 5.
Theoretically you could choose some seed you like and run Mersenne Twister on your calculator, but that seems a bit extraneous
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[3iff]

Sorry, it's a simple calculator...I have + - / * percent and square root...and it ain't programmable.

I do have a computer to hand and could program a random number generator but using a hand calculator and a simple procedure it's much easier doing things that way.

Impressive answer though.

[Duke Gnome]

Just use 4. Everybody knows 4 is the most random number.

[Jack_Ian]

How about a telephone book?
Open a page at random and use the right-most digits of the numbers listed. The left side of the telephone numbers is not random, but after the first 3 digits, it's as random as any computer can dream up for you.

[Courk]

Can you take the number keys off a calculator? Place in a face-side down pile and mix them up.

[ralphmerridew]

Hit a series of digits until the screen is full, then hit square root, and take the rightmost digit. That should be close enough to random.

[Chuck]

Toss the calculator like a coin enough times to generate a sufficiently long binary number.

[bonanova]

This was a real problem with the original IBM PCs back in the '80s.
Games of chance would repeat -- computers being the logical beasts they're supposed to be.

To preclude this, the clever folks who wrote the game apps would simply ask the user to fix the problem.
At first invocation, the RNG that would roll the dice in a craps game, say, got a new seed by flashing the ingenious message on the screen:

Please enter a random number.

Little did folk know back then that the right number to enter was 4.

Of course, the computer had a clock. And a simple way to seed the RNG would have been to use the last few digits [milliseconds back then] of the current time!

Anyway, I always wondered [a] which numbers were the random ones, and [b] why they didn't simply say [for the craps game]:

Please enter two random numbers between 1 and 6.
_________________
_{Vidi, vici, veni.}

[Nsof]

[marcusI]

Let your cat/dog/bird/baby/wife/ etc. walk on the keypad.

[Antrax]

I guess if you do <punch keyboard> / <punch keyboard> and choose the third digit from the right + 1 it should be uniform, but I don't know how to prove it.
Instead, you can pick your favourite a, b such that both aren't divisible by 2, 5, or 10 (say, 3 and 7 or something of the sort) and do a * <punch keyboard> + b, and take the rightmost digit + 1, this should be uniform on [1, 10].
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[PuzzleScot]

I'm sure there are lots of answers..

1) Draw a target on the wall with 10 areas. Throw calculator at the wall, and see where it hits...

2) Prise the 10 digit buttons off the calculator, put them in your pocket, then pull one out...

3) Pour sugary tea on your calculator. As it dries, the keys will stop working one at a time. The last digit to stop working is your random number!

4) Place calculator face down on the floor and stamp on it. First digit showing on display is the one you want.

5) Repeatedly smash calculator with a hammer. Count all the pieces and shards, and take the modulo 10 remainder

6) Drive a nail through the centre of the calculator into your desk. Mark 10 even areas on your desk, in pen, around the nail. Simply spin to get a random number every time.

7) Flip the calculator like a coin 100 times. The number of face-ups modulo 10 will be random. (ish)
_________________
http://www.ukpuzzles.org/

[Lepton*]

I remember programming some BASIC stuff where I needed to seed the random number generator. If we're talking about a non-physical calculator, the real issue is seeding. Antrax has suggested a number of methods that will give a good distribution as long as decent seeds are provided.

Mashing the calculator probably won't give you a good seed, because our hands have definite shapes. Try mashing your keyboard a few times and see what letters you get. If we apply Antrax's ideas in series, we can get arbitrarily close to an even distribution.

Here's an idea that hasn't been suggested yet. Create a simple Markov Chain. You will need to remember the previous random digit. Then do a certain series of operations that will give you another digit. The simplest example would be to take the previous random digit, multiply by 7, and take the units place digit (this will give you an even distribution of odd digits). More complicated algorithms are what drive the "shuffle" in your iPod.

[Zag]

Lepton, You need to read Knuth's (definitive) paper on random numbers. He talks about using such a method (where each number is the seed for the next, with a complex formula each step). The problem was that he found he very clever and complex algorithm would quickly devolve into one of several numbers that each generated themselves.

Even with a simpler process like you describe, you have the problem that you never get the same number several times in a row, followed by different numbers. Since this will happen rolling a die, it should happen with your pseudo-random numbers, as well. The usual technique when using such an algorithm is to be generating numbers across a range that is at least a thousand times larger than the range of numbers you want to use. Then you have to do a ton of testing to see that the numbers generated are actually random-like.

[Dented Ford]

Look up last week's lottery results. If they aren't random enough, then you should sue the lottery company.

[Courk]

One day I noticed that the current drawing and the one before were identical. I think it was only the pick 3 or pick 4, but still...

[Zag]

[marcusI]

This won't work for a simple calculator, but Lepton's post about BASIC reminded me.
Back in the BASIC days I used a method that seemed to work well for the seed number. They accepted any number from 1 to 32,000. I set up a loop counting rapidly from 1 to 178 (sqrt(31,684)) then used two user inputs to stop the loop twice. The inputs were needed anyway. Multiplying these user generated numbers together gave me the seed.

[Lepton]

[Zag]

Not my day-to-day, I'm afraid. But I did work for a video game company once, many moons ago, and one of the things I wrote was the random number generator. Now I work on boring stuff.

Knuth's paper is actually pretty funny. He describes the number generation process that he made up, thinking that a really "random" process would generate really random numbers. It was something like: Starting with a 10-digit number, grab the third digit as a counter. Square the number and keep the middle 10 digits <counter> times. Then some other transformations along similar lines.

It sounded great, until he pointed out the 10 digit numbers which, after all the machinations, would transform to themselves, and that he found very few numbers that didn't result in one of those within a dozen transformations.

The one I created was one of the ones that Knuth ends up suggesting. (This was for an 8-bit cpu, and I had very limited RAM and even less ROM to work in. I had a bank of 27 bytes, which were seeded from the timer readings when the player was clicking through the startup screens. I had two indices, one that moved through the bank 2 at a time, the other at 5 at a time. When asked for a random number, I would add the numbers under the two indices and put it in the position of the first index; move both indices, then return the number. The whole thing is 29 bytes of RAM, maybe 100 bytes of ROM, very fast, and wonderfully random.

[Antrax]

Sounds a lot like an LFSR, if I understood correctly. Sounds cool
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[3iff]

Well, I certainly got a large collection of increasingly bizarre answers...

Anyway, what I do, wishing to maintain the integrity and usefulness of my calculator, is to randomly punch in 8 digits (all the calculator will process), then hit 'divide' and punch in another random number between 4 and 8 digits...

I then read the answer starting from the first decimal place and this gives me a series of random number (should I need more than one) with 0 representing 10 of course.

I believe this to be totally random unless one of you match geniuses can offer proof otherwise.

[Antrax]

By "totally random" do you mean uniform? because your method will never produce 10 as the first number.
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Zag]

I believe he meant the first place after the decimal. i.e. tenths.

It's pretty random, but a lot depends on how you "randomly" press digits. For instance, if I randomly press digits, I get 987546546 a lot, and close variations.

Also, if your divisor is ever a digit longer than your dividend, you'll find yourself getting 10 quite a bit too often.

[3iff]

Example...

random number is 49621758
divisor is 47596

result is 1042.5615, giving me random numbers of 5, 6, 1 and 5 again which I'd ignore.

My random numbers are conciously carefully entered...an ambiguous term...but I strive to hit a number of different digit keys without regard to which numbers they are, sometimes even deliberately hitting the same number twice in a row. I'm also careful to make the divisor a shorter number.

Should I need more randoms, then I do it again...and my method at least allows me to reuse the calculator again later.

[Lepton*]

[3iff]

I'd ignore it because I don't need it...

My 'application' is to choose usually 2 items from a list of usually 6 items. So I really only need 2 numbers from 1-6 and they must be different.

So if the random result was 345.91814 then my randoms would be 1 and 4, ignoring 9 and 8 as they are out of range and ignoring the duplicate 1.

Perhaps I should have mentioned that?

Obviously for a different purpose, I would accept all generated random numbers that fit my criteria.

[MatthewV]

I usually will type in a long number and then divide it by another long number and take the digit after the first non-zero digit. This way I don't have to worry about typing in a shorter number the second time.

[Zahariel]

All of these schemes based essentially on "choose a particular digit of x / y" are slightly biased toward lower numbers, because x / y is convex in the y direction (in the first quadrant), and linear in the x direction. It turns out, even if you're using good uniform random numbers to begin with (which, if you're getting them by pressing buttons on a calculator, you aren't), it's really tough to keep them uniform after you do something to them! Schemes based on division, exponentiation, or powers greater than 1 (any function for which f'' is positive) will tend to give low digits more than high digits; square roots and logarithms are just the opposite and give high digits more than they should. This is actually one of the ways the IRS spots made-up tax returns; practically all of the functions involved in a tax return are exponential so they ought to have more 1s than 9s.

This bias is relatively slight, though, so it probably won't matter unless you're doing cryptography though. And if you are, you need a real mechanical source of randomness anyway; nothing you do yourself is going to cut it. Zag's right; this sort of thing is harder than it looks. Knuth finished the paper (and the appropriate chapter of TAoCP) with the quote "The generation of random numbers is too important to be left to chance."

[ShadowSword]

Let's say your simple calculator has a nice memory. Punch in n! (n>=5). Subtract from that number the same number but removing all the zeros from the number. Add 4. Now remember the last digit (let 0 take the place of 10). Call it A.
Now repeat the exact same process but start with (n+1)! Now instead of calling the last digit A, we will call it B. If A<B then your random number is A+1, otherwise it is A. To be constant, take mod 10 of the number.

So let n=11
39916800-399168+4= 39517636, A=6
n+1=12
479001600-47916+4=47895388, B=8
B>A, therefore your random number is 7

The number certainly sounds random enough but i wouldn't bet on it. There are a lot of algorithms which seem to yield a random number that you could do. If you don't prove that the chances of each number coming up is the same then frankly you don't know if it is truely random.
_________________
"Heads you're good, tails you fail" says my fortune cookie

[Antrax]

I'm almost sure I can prove that method is not uniform. How did you come up with it?
_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!

[Pigboy]

[L'lanmal]

[Lepton]

Because everyone knows that 0 is not a random number.

[ralphmerridew]

If you have a weakly random method, you can unbias it:

Generate 10 weakly random numbers. See which is the largest. Choose its index as your random digit.

[3iff]