> 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 cursed d65536
31–40 of 74 posts
Re: The cursed d65536
#32I'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
#33Earlier quoted context omitted.
Why not just roll 4D16? https://www.amazon.com/Lanema-Polyhedral-Dungeons-Dragons-Si...
"... for Dungeons and Dragons" ah yes, I use a D16 all the time when playing D&D /s
Re: The cursed d65536
#34> 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…
Re: The cursed d65536
#35I'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.
1in diameter, however, gives 0.175mmx0.175mm per face, or about the width of a hair by the width of a hair.
Re: The cursed d65536
#36Re: The cursed d65536
#37Earlier quoted context omitted.
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
#38Earlier quoted context omitted.
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…
This sounds interesting - could you elaborate further on how rejection sampling "fails" on LuaJIT?
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.)Re: The cursed d65536
#39I 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.
Re: The cursed d65536
#40My 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.