speed of rand vs randi

Question

Jonathan 2011-11-11

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/21013-speed-of-rand-vs-randi

I sometimes use "if rand < 0.5" or "if randi(2) == 1" to arbitrarily select one branch or another with equal probability. I ran the following code to see the speed difference between these. Does anyone know why fetching a random double is so much less expensive than fetching a random integer?

Thanks in advance, Jonathan

tic
randi(2,1000000,1) == 1;
toc
tic
rand(1000000,1) < 0.5;
toc
Elapsed time is 0.037818 seconds.
Elapsed time is 0.018022 seconds.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Jan 2011-11-11

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/21013-speed-of-rand-vs-randi#answer_27714

在 MATLAB Online 中打开

The algorithms to create random numbers reply 32bit integers usually. A standard method to create a random DOUBLE combines two of them:

a = <INT32_rand>;
b = <INT32_rand>;
r = ((a >> 5) * 67108864.0 + (b >> 6)) / 9007199254740992.0;

Getting an integer <= n with a guaranteed equal distribution is more expensive. You cannot just use MOD or an integer division, because this would result in a bias. You have to draw random numbers until you get one, which is smaller than the largest multiple of n, which is smaller than 2^32-1. Then the modulo-operation is safe. This methods needs branching, which slows down the processor massively.

3 个评论
显示 1更早的评论隐藏 1更早的评论

Jan 2011-11-11

The license conditions of Matlab forbid a reverse engineering.

Matlab uses standard libraries for the creation of random numbers, e.g. mt19937ar, therefore it is documented, that 32-bit integers are created. Some comparisons of the results would reveal the parameters used for the conversion to doubles.

For the conversion to integers there is another efficient method from Magnus Jonsson:

used |= n >> 1;

used |= used >> 2;

used |= used >> 4;

used |= used >> 8;

used |= used >> 16;

// Draw numbers until one is found in [0,n]:

while ((i = RAND_UINT32() & used) > n) ;

The runtime behaviour is equivalent to the method explained above. The Matlab documentation links to this page for details about the Mersenne twister:

http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

Jonathan 2011-11-17