It is an interesting approach, but the question is how it would work
or be made to work for Erlang...
The range algorithm in rand.erl seems to be what Lemire's paper calls
"The Java Approach", I agree.
Lemire's "Avoiding Division" approach avoids integer division and instead
uses multiplication of the random number and the range and bit shifts the
result, assuming multiplication and bit shift are significantly faster
operations than integer division.
The default PRNG:s in the 'rand' module generate 58 bit integers. This
size is carefully selected to avoid creating bignums since they are much
slower to operate on. You can add 3 58 bit integers to get a 59 bit,
and it is still not a bignum. A 60 bit integer is a bignum. All this
assuming a 64 bit VM with the current term tag scheme.
So, multiplying a generated integer of 58 bit with any range larger than 3
would create a bignum, and a subsequent bit shift left of 58 bits would
have to operate on a bignum. I reckon that would be a significant
performance penalty.
To remove the bias, the fastest I can think of right now would be to
mask out the low 58 bits, compare if it is a biased number, and if so
reject and reiterate. Or generate more bits and do a new bignum
multiplication and shift.
For ranges larger than 58 bits you are in bignum land to start with,
so Lemire's approach suggests that we could just generate one extra
58-bit random word, multiply, shift and say the bias is buried.
This might be simpler and faster than the current approach.
An interesting idea.
I think the "Avoiding Division" approach might be efficient when
the range is less than 26 bit because then we could use only 26
bits from the random number and keep the multiplication and shifts
in smallnum integers. This could be interesting to try out.
Those are my first impressions and guesses. They are not the truth.
The truth has to be measured...
Also, if we should come up with a new way of generating integers in
a range, since they would produce new sequences of integers for
the same seed; we have to decide to create new algorithm names
- duplicating all existing. Either that or introduce new
API functions besides rand:uniform/1 and rand:uniform_s/2.
So the performance gain would have to merit such a change...
Cheers
/ Raimo Niskanen
On Tue, Sep 14, 2021 at 10:40:29AM +0200, Thomas Depierre wrote:
> In theory, yes. You would just need to generate more bits of randomness to
> have enough entropy.
>
> There is a catch though. If you begin to need so much entropy that
> generating that is far slower than divisions, then you should look at
> another approach. The Lemire paper offers a reference to other approaches
> more suited to these through less well known and mostly forgotten
> algorithms from the 70s.
> This particular paper is long (60 pages) and is not super applicable to my
> needs, so I have not taken the time to dive in details yet.
>
> In particular, you would need to have generated enough random bits to be
> slower than the big int divisions you need to do. That is probably not
> happening under any realistic integer range we would deal with on the BEAM
> imho.
>
> Thomas Depierre
> Schedule a meeting with me <
https://calendly.com/thomas-depierre/30min>
--
/ Raimo Niskanen, Erlang/OTP, Ericsson AB