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 2004. I learned about this back in the days of 2600 magazine. Fun stuff!
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.
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.
I guess it says you're more into hardware than you're into math, when I saw the title I thought 'this must be some really weird Dungeons and Dragons article'
> 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 values obtained above M. Those values are just "rain that fell elsewhere".
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.
I mean, as far as correctness as concerned, of course it works, but performance-wise in a raytracer I was toying around with it was a dismal failure compared to the (traditionally shunned) analytic approach.
The issue, as far as I understand it, is that LuaJIT only handles traces of two shapes: linear code; or linear loop prologue followed by linear loop body. The conditions of any branches (that could not be determined statically) are evaluated and checked against their tracing-time values, but a failed check (“guard”) throws you out of the compiled trace and back into the interpreter. This includes normal termination of a loop and misspeculated types as well as explicit conditionals.
Of course, handling only these two patterns of control flow is too limiting, so if a guard fails too often the trace compiler can start a new trace from that exit and tie its other end to the original one if it comes back. Aside from handling things like polymorphic functions which get called for more than one combination of types and predictable branches in loops that still get taken occasionally (but too rarely for unrolling), this also turns out to handle nested loops (as explained somewhere in the docs): the inner loop get traced first as a loop, then the outer loop body gets traced as a linear block that ties the end of the inner one back to its beginning, going around from the middle of the outer loop to its end, then from the beginning of its next iteration to the middle.
The catch is that register allocation or optimizations can’t see across trace boundaries, so those side traces get second-class treatment (in particular, only the inner loop gets subjected to loop-invariant code hoisting and strength reduction, as the outer ones are not viewed as loops). Additionally, the part that decides what to trace and how (is it a loop, is it hot, should it be unrolled, etc.) is an opaque pile of heuristics which is generally well tuned, but gets more confused and slower to converge as the nesting level increases.
Turns out having your innermost loop be rejection sampling which usually terminates quickly (under the unrolling threshold) but with a varying number of iterations, in a raytracer that’s already bound to have two or three levels of nested loops, plays merry hell on all of this. Occasionally LuaJIT couldn’t eliminate the GC in the now-“outer” loop and ran 5x slower, occasionally it just fell back to the interpreter and ran 20–100x slower, but generally I think that counts as a failure when the motivation is to avoid libm because it’s slow.
(For similar reasons, the small-vector library used there is almost entirely sad repetitive code along the lines of
c.x = f(a.x, b.x)
if one component then return c end
c.y = f(a.y, b.y)
if two components then return c end
...
because that does not count against the thresholds when you have dozens of these operations per actual iteration.)
The raytracer itself is not in a state I’d want to inflict on anybody. The vector library is just HLSL-style small vectors with subpar error reporting, there’s like half a dozen of those floating around, but if you want it, sure, go wild: http://ix.io/3ZQk (CC0). I’d only ask you to hold off on posting it to LuaRocks under that name because I want to do that myself eventually.
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.)
Is there some method to determine whether a sequence of numbers, being generated from a black-box, reaches a point at which we can confidently say it's a random sequence?
Assuming "random" means that there is no program to generate the sequence that is shorter than the sequence itself, proving the nonexistence of such a program is equivalent to the halting problem. See https://en.wikipedia.org/wiki/Kolmogorov_complexity
If you observe a black box producing a sequence N items, you can’t know whether it will, after that, repeat the same sequence at infinitum (it might just contain a circular tape of N items, for example), or keep producing a single identical item, or keep producing only two different items, etc.
It would require P=NP (widely assumed to be false) and the nonexistence of one-way functions (actually an even stronger assumption). Any one-way function can be used as a PRNG, and it's computationally infeasible to distinguish that from a true random number generator, almost by definition.
Any conceivable sequence could theoretically be generated by randomness. A perfect random number generator could generate a list of social security numbers or an infinite sequence of zeros. Likewise any sequence that appears random may just have a pattern which hasn't emerged from what has observed.
If you're working with real numbers, then your step counter is a natural number, you repeat for[2] infinitely many steps, and the probability of failure is exactly zero.
If, on the hand, you're working with surreal numbers - which you would have to be for "infinitely small (but non-zero)" to make sense - then your step counter is a ordinal number[1], not a natural, and you repeat for[2] non-well-foundedly many steps (one for each ordinal), after which the probability of failure is again exactly zero. (Otherwise it would be the reciprocal of some surreal number, that is less than some ordinal, and for any ordinal, you can show that you tried a well-founded number of times that is nonetheless strictly greater than it.[0])
The more existent problem is that you can't put any useful upper bound on how many rerolls you'll need, which is terrible for constant-time algorithms, and particularly for cryptography.
0: And you actually only need two to the power of the number of tries to be greater, since the failure probability of one sample is at most 1/2, so the probability after K tries is at most 1/2^K.
1: ie, a positive whole surreal number, rather than a positive whole real number
2: Technically, you repeat for up to but not including that many, since you're guaranteed to terminate by then.
> 1: ie, a positive whole surreal number, rather than a positive whole real number
Actually, ordinals have some additional contraints besides just "positive" and "whole" (eg ω−1 is not a ordinal), that just reduce to "positive whole" in the case of reals, although that doesn't change the actual point any.
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.
If we accept needing the user to run an "algorithm" like that, we could have a D256(Or whatever the next highest fair dice is) and actually have a practical-ish system.
Although hex D16s would probably be better.
D20s with 0-F plus two extras could be pretty awesome in a cyberpunk tabletop game. The other two could be "IOError" that makes the matrix glitch in a bad way, and superposition, that makes it glitch in a way you can use.
If you are OK with roll again then you can just have a cylinder-ish shaped dice where numbers are on the sides (so it is N-edge polygon instead of a circle) and top and bottom is marked as "roll again"
even better, you can round the top and bottom. Either by semi spheres or pointy like a pencil tip. Then chances of "roll again" hitting would be really low!
From the broken first attempt: Each face has 3 vertices, shared between 6 faces, so the total number of vertices is 65536, and they become faces of my die.
This should have tipped you off. If you have six triangular faces around every vertex, you have a flat Euclidean plane, not a sphere with positive curvature.
Pedantry: it doesn’t have to be flat - for example a triangulated parabola could also have that configuration. You only get a topological result from just knowing edge and vertex counts. Now if the triangles are identical equilateral then you’re in business.
What if the triangles are all congruent but not equilateral? Can that even happen? That’s a fun one, so I won’t spoil it.
Not a sphere, we know that can’t happen due to the topological constraint you brought up. Instead picture a float plane tiled by equilateral triangles. Now mark each vertex as either low, middle, or high such that every triangle has one of each. Push the low ones below the plane and the high vertices above the plane by some amount x. Now it’s a bumpy plane full of triangles, each one is isosceles and all identical.
I think that’s the only way to do this, but maybe there are more. Could we get a hyperbolic plane this way? Normally you squeeze extra triangles around each vertex to do that so I doubt it but maybe.
That's why "don't do math after midnight". But I don't get what's wrong with repeated throws of tetrahedron - 2 bits of result at a time - or even icosahedron, with re-throws if one of 4 "wrong" sides is up - 4 bits at a "good" throw...
You can also make repeated throws of an octahedron for 3 bits per throw. 16 is not a multiple of 3, but there's no difficulty with just discarding the 17th and 18th bits. So you'd need to roll 6d8 instead of 8d4.
Look at the humble d10 for inspiration. The trick is to avoid making a spherical-looking die. A fair d65536 could look like a pair of cones glued together, with 32768 sides per cone. Alternatively, one can make a fair 65536-sided cylinder with rounded ends.
I'd like a physics analysis of how flat/hard a surface you need to roll a D65536, how long it would take to settle, and how good a microscope you'd need to read the top face.
Is there, like, 99designs for physics questions? I'd happily pay $99 for the answer, then post it here like I worked it out myself.
a 1ft diameter d65536 could be broken into surfaces with area 4.45 square millimeters, or a little over 2x2mm. With good eyes and enough squinting, a microscope might not be needed. maybe fill it with liquid with a tiny air bubble to find the top face
1in diameter, however, gives 0.175mmx0.175mm per face, or about the width of a hair by the width of a hair.
Use a 7-segment font and two paints with the same density, with one paint the same as the background color. For each digit, paint in all 7 segments. For each number, draw all 5 digits.
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.
You can buy hexadecimal dice ie D16 with the sides labelled 0 through F, I have some, I use them to generate random numbers when it is important to me that I personally have confidence these are random numbers.
With hex dice you can generate 16 bits with four rolls, four bits each time.
Obviously you're more likely to already have a D6 somewhere, but then you're even more likely to own a coin, and 16 coin tosses is also an effective way to generate a 16-bit number.
> Obviously you're more likely to already have a D6 somewhere, but then you're even more likely to own a coin
I'm not sure this is still true. At least not here in Sweden. Everyone I know owns multiple board games which come with at least one D6 and in recent years I've had discussions with friends and family about us paying everything electronically nowadays. There has even been talk about the risk to our society of no one having cash anymore.
In fact, some weeks ago I needed a coin to show my kids when they asked about this physical money they'd heard of and I couldn't find one.
Yep, or use 16 dice that have only 0 and 1 on them. The order would be important, so you'd want to color them or otherwise indicate which was high order and which was low.
Or do 16 throws of such a d(2) die, i.e. 16 coin flips, in succession.
If you really want to do it in one throw, you don't really need to color them all differently, though. Just read them in a specified way, i.e. always from left to right and top to bottom. (You don't even have to always read them the same way as long as how you read them is completely independent from what their faces show.)
I'd be a little worried that I might be tempted to unconsciously order the values in some way which would bias the results. But you could build a box with four separate cells and a clear plexiglass top, shake them all up, and always read left-to-right or right-to-left! Sounds like a fun weekend project!
I believe that there are fewer than factorial(65536) particles in our universe[0], so I reject using a die with that many faces to equalize the probabilities. As other comments point out, a mere 65536 faces is on the verge of practicality.
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)
There's an assumption here that a polytope with equal area faces will be fair. I'd like to see a proof.
My mathematical intuition is that the probability of stopping on a face depends on the extent that nearby faces slow a rotation, which depends on the angle of attack across each face. Without symmetry, this will vary by face.
The article explicitly says that equal areas are not required for fairness; and gives this explanation for wanting equal areas: "Dice that are fair by symmetry (and hence under any reasonable throwing dynamics) always have to have an even number of sides and belong to certain symmetry groups (Diaconis & Keller 1989)."
A better approach would be to calculate the amount of needed nodes that would junction the vertices, and then push them apart (simulated annealing). Though it won't be a regular geometry.
it would be easier to avoid edges altogether and regularly space flat circular areas leaving curved space between them. you can have any arbitrary number of faces if you give up on the faces touching.
[1] http://www.techfreakz.org/2600faq.html#redbox
[2] https://hackaday.com/2004/09/05/radioshack-phone-dialer-red-...