Live data from Hacker News

The cursed d65536

aleph.se

21–30 of 74 posts

Re: The cursed d65536

#21
post #2

I know it's not the point of TFA, but you can just roll a d8 6 times, generating 3 bits each time, for a total of 18 bits, and then discard two of them.

The article suggests flipping coins in the last sentence, which gets you exactly as many bits as you want.

Re: The cursed d65536

#22

> This is of course hilariously cursed. It will look almost perfect, but very rarely give numbers outside the expected range. If the D65538 is fair, it is usable: you just discard the two unwanted values when they show up and roll again. Those faces could be labelled as "roll again". If you have a uniform source of random numbers from 1 to N, you can get a uniform distribution from 1 to M < N simply by discarding val…

This process has an infinitely small (but non-zero) chance of never terminating.

Re: The cursed d65536

#23
post #20

Probably says something about me that my immediate reaction to the number 65536 wasn’t 2^16, but rather the frequency of the timer crystal you had to swap into a Radio Shack tone dialer to make a “red box”[1] that would let you make free phone calls on US pay phones by simulating the analog coin code sound of a quarter being deposited. Fun fact that the “red box” was the first hackaday article[2] posted way back in 2…

I just coded it in basic and the recorded it to a mini-casette lecture-recorder. Unfortunately, by that point the tones just triggered an operator call.

Re: The cursed d65536

#24
post #22

> This is of course hilariously cursed. It will look almost perfect, but very rarely give numbers outside the expected range. If the D65538 is fair, it is usable: you just discard the two unwanted values when they show up and roll again. Those faces could be labelled as "roll again". If you have a uniform source of random numbers from 1 to N, you can get a uniform distribution from 1 to M < N simply by discarding val…

This process has an infinitely small (but non-zero) chance of never terminating.

The die also has a very small chance of landing on an edge between two faces, which also requires a repeated roll.

Re: The cursed d65536

#25
post #22

> This is of course hilariously cursed. It will look almost perfect, but very rarely give numbers outside the expected range. If the D65538 is fair, it is usable: you just discard the two unwanted values when they show up and roll again. Those faces could be labelled as "roll again". If you have a uniform source of random numbers from 1 to N, you can get a uniform distribution from 1 to M < N simply by discarding val…

This process has an infinitely small (but non-zero) chance of never terminating.

But that probability rapidly drops below the probability that you will drop dead from some random cause while waiting for the roll's result :)

Re: The cursed d65536

#26
I'm surprised that nobody has mentioned the d120 which AFAICT is the largest fair dice that you can just go out and buy. Sadly it's a smidge under 7 bits, but you can "reasonably" roll up 32 bits of entropy with a mere 6 rolls (and still have 9 bits left over)

https://www.wired.com/2016/05/mathematical-challenge-of-desi...

Re: The cursed d65536

#27
post #22

> This is of course hilariously cursed. It will look almost perfect, but very rarely give numbers outside the expected range. If the D65538 is fair, it is usable: you just discard the two unwanted values when they show up and roll again. Those faces could be labelled as "roll again". If you have a uniform source of random numbers from 1 to N, you can get a uniform distribution from 1 to M < N simply by discarding val…

This process has an infinitely small (but non-zero) chance of never terminating.

This is a rather sloppy way of saying "this process may fail to terminate, though the set of nonterminating outcomes has probability 0". No real number is infinitely small but nonzero.

Re: The cursed d65536

#28

> This is of course hilariously cursed. It will look almost perfect, but very rarely give numbers outside the expected range. If the D65538 is fair, it is usable: you just discard the two unwanted values when they show up and roll again. Those faces could be labelled as "roll again". If you have a uniform source of random numbers from 1 to N, you can get a uniform distribution from 1 to M < N simply by discarding val…

Rejection sampling, that is. Unexpectedly, but obviously in retrospect, the common (ancient) wisdom of using that in the continuous case instead of figuring out tricky combinations of special functions to get the result from a bounded number of uniform samples... fails miserably on LuaJIT. Of course atan2() is not the fastest thing in the world, but on a compiler that only really understands loops with linear bodies calling it even via FFI beats adding an unpredictable nested loop.

Re: The cursed d65536

#29
post #22

> This is of course hilariously cursed. It will look almost perfect, but very rarely give numbers outside the expected range. If the D65538 is fair, it is usable: you just discard the two unwanted values when they show up and roll again. Those faces could be labelled as "roll again". If you have a uniform source of random numbers from 1 to N, you can get a uniform distribution from 1 to M < N simply by discarding val…

This process has an infinitely small (but non-zero) chance of never terminating.

The process has exactly zero chance of never terminating in the usual probability space of infinite strings with iid characters, even though the set of strings (of RNG results) on which it does not terminate is nonempty (uncountably infinite, even, provided N ≥ M + 2); the term of art is that it terminates almost surely. An alternative definition is that you can throw out these strings from the space and no well-posed question of probability (as opposed to set) theory will get a different answer. They’re gremlins, essentially, except for the part where an (uncountably) infinite union of gremlin (null) sets may not yield a gremlin set.

(The usual definition of that space via “cylinder sets” may seem contrived, but it’s usually introduced first because it’s “elementary” in that it does not require developing the machinery of limits of [not in] probability spaces. Those can be made to work, though, and then you can say that the space of infinite strings is the limit of the spaces of length-n strings for n → ∞ and obtain the same thing. In fact, the cylinder-set definition is essentially the limit definition with the notion of limit inlined.)

Re: The cursed d65536

#30
post #20

Probably says something about me that my immediate reaction to the number 65536 wasn’t 2^16, but rather the frequency of the timer crystal you had to swap into a Radio Shack tone dialer to make a “red box”[1] that would let you make free phone calls on US pay phones by simulating the analog coin code sound of a quarter being deposited. Fun fact that the “red box” was the first hackaday article[2] posted way back in 2…

The DTMF chips that generated regular Touch Tones™ were capable of generating all kinds of fun sounds simply by extending the key matrix.

You could build a red box, pink box, blue box, and others by modifying a standard tone dialer. The easiest thing to do was to add a fourth column of keys, which supposedly gave you the ability to use the ABCD digits required for military networks. I never tried that, though.

For those of you who missed out on that era, a tone dialer was a little palm-sized box that had a small Touch Tone keypad on one side, and a speaker on the other. If you had a rotary phone, after dialing, you could hold it up to the mouthpiece and use many of the fancy features that came with the invention of Touch Tone, like using FŌN cards, or listening to your messages on your answering machine.

Post reply on HN