30 ms·
> 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 usab
by kazinator 4y ago
> 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".
- stkdump 4y agoThis process has an infinitely small (but non-zero) chance of never terminating.
- kazinator 4y agoThe die also has a very small chance of landing on an edge between two faces, which also requires a repeated roll.
- davidgay 4y agoBut that probability rapidly drops below the probability that you will drop dead from some random cause while waiting for the roll's result :)
- phinnaeus 4y agoI think the most likely cause of death in that case is being crushed by your d65536
- a1369209993 4y agoI think that would be much less likely than being crushed by your d65538, given the premise.
- Smaug123 4y agoThis 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.
- mananaysiempre 4y agoThe 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.)
- ffhhj 4y agoIs 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?
- krapp 4y agoNo.
- ffhhj 4y agoWhy? Is it because it haven't been found, or is there a proof of impossibility?
- krapp 4y agoAny 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.
- Dylan16807 4y agoWhich doesn't matter on objects or programs because that chance already exists as a baseline. I'm not building a math here.
- a1369209993 4y agoActually, it doesn't. 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.
- a1369209993 4y ago> ordinal number[1] > 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.
- mananaysiempre 4y agoRejection 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.
- virchau13 4y agoThis sounds interesting - could you elaborate further on how rejection sampling "fails" on LuaJIT?
- mananaysiempre 4y agoI 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.)
- shultays 4y agoIf 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!
- eternityforest 4y agoIf 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.