Why isn't Random API next(upperBound: T) implemented using "Apple's Method"?

(Jens Persson) #1

I'm just curious if there are any particular reasons why the Random API's next(upperBound: T) is implemented the way it is (with two %) rather than using the AFAICS more efficient "Apple's Method" (with a bitmask and no %) as described eg here.

1 Like
(Pyry Jahkola) #2

Is upperBound required to be a power of two here? Because otherwise this implementation seems not-quite-right… :thinking:

(Steve Canon) #3

It's a little bit subtle to implement efficiently for generic integers that may be arbitrarily large, but mostly I/we simply haven't gotten around to it yet, and the current implementation is "good enough"--there have been higher-priority optimization tasks to attend to.

(Steve Canon) #4

No, it's simple rejection sampling, so easy to prove that it's always correct.

1 Like
(Pyry Jahkola) #5

Right, what got me is the fact that it rejects the initial range which occurs one time more than every other value before the final modulo. :+1:

1 Like