diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2018-03-22 16:54:49 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2018-03-22 16:54:49 -0300 |
commit | c5e3b2f81402773466f2afc8e87839509f65facc (patch) | |
tree | 2adaf431b9d1fc41c49fdd6d70541f3883c9e231 /lmathlib.c | |
parent | 64867624630b4effacb3d3fb54708ecda19f0221 (diff) | |
download | lua-c5e3b2f81402773466f2afc8e87839509f65facc.tar.gz lua-c5e3b2f81402773466f2afc8e87839509f65facc.tar.bz2 lua-c5e3b2f81402773466f2afc8e87839509f65facc.zip |
in random/'project', remove the special case for "small" intervals;
it is slower than the general case.
Diffstat (limited to 'lmathlib.c')
-rw-r--r-- | lmathlib.c | 39 |
1 files changed, 15 insertions, 24 deletions
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: lmathlib.c,v 1.125 2018/03/12 12:39:03 roberto Exp roberto $ | 2 | ** $Id: lmathlib.c,v 1.126 2018/03/16 14:18:18 roberto Exp roberto $ |
3 | ** Standard mathematical library | 3 | ** Standard mathematical library |
4 | ** See Copyright Notice in lua.h | 4 | ** See Copyright Notice in lua.h |
5 | */ | 5 | */ |
@@ -422,27 +422,18 @@ typedef struct { | |||
422 | 422 | ||
423 | /* | 423 | /* |
424 | ** Project the random integer 'ran' into the interval [0, n]. | 424 | ** Project the random integer 'ran' into the interval [0, n]. |
425 | ** Because 'ran' has 2^B possible values, the projection can only | 425 | ** Because 'ran' has 2^B possible values, the projection can only be |
426 | ** be uniform when the size of the interval [0, n] is a power of 2 | 426 | ** uniform when the size of the interval [0, n] is a power of 2 (exact |
427 | ** (exact division). With the fairest possible projection (e.g., | 427 | ** division). To get a uniform projection into [0,lim], we first |
428 | ** '(ran % (n + 1))'), the maximum bias is 1 in 2^B/n. | 428 | ** compute 'lim', the smallest (2^b - 1) not smaller than 'n'. If the |
429 | ** For a "small" 'n', this bias is acceptable. (Here, we accept | 429 | ** random number is inside [0, n], we are done. Otherwise, we try with |
430 | ** a maximum bias of 0.0001%.) For a larger 'n', we first | 430 | ** another 'ran' until we have a result inside the interval. |
431 | ** compute 'lim', the smallest (2^b - 1) not smaller than 'n', | ||
432 | ** to get a uniform projection into [0,lim]. If the result is | ||
433 | ** inside [0, n], we are done. Otherwise, we try we another | ||
434 | ** 'ran' until we have a result inside the interval. | ||
435 | */ | 431 | */ |
436 | |||
437 | #define MAXBIAS 1000000 | ||
438 | |||
439 | static lua_Unsigned project (lua_Unsigned ran, lua_Unsigned n, | 432 | static lua_Unsigned project (lua_Unsigned ran, lua_Unsigned n, |
440 | RanState *state) { | 433 | RanState *state) { |
441 | if (n < LUA_MAXUNSIGNED / MAXBIAS) | 434 | lua_Unsigned lim = n; |
442 | return ran % (n + 1); | 435 | if ((lim & (lim + 1)) > 0) { /* 'lim + 1' is not a power of 2? */ |
443 | else { | ||
444 | /* compute the smallest (2^b - 1) not smaller than 'n' */ | 436 | /* compute the smallest (2^b - 1) not smaller than 'n' */ |
445 | lua_Unsigned lim = n; | ||
446 | lim |= (lim >> 1); | 437 | lim |= (lim >> 1); |
447 | lim |= (lim >> 2); | 438 | lim |= (lim >> 2); |
448 | lim |= (lim >> 4); | 439 | lim |= (lim >> 4); |
@@ -451,13 +442,13 @@ static lua_Unsigned project (lua_Unsigned ran, lua_Unsigned n, | |||
451 | #if (LUA_MAXINTEGER >> 30 >> 2) > 0 | 442 | #if (LUA_MAXINTEGER >> 30 >> 2) > 0 |
452 | lim |= (lim >> 32); /* integer type has more than 32 bits */ | 443 | lim |= (lim >> 32); /* integer type has more than 32 bits */ |
453 | #endif | 444 | #endif |
454 | lua_assert((lim & (lim + 1)) == 0 /* 'lim + 1' is a power of 2 */ | ||
455 | && lim >= n /* not smaller than 'n' */ | ||
456 | && (lim >> 1) < n); /* it is the smallest one */ | ||
457 | while ((ran & lim) > n) | ||
458 | ran = I2UInt(xorshift128plus(state->s)); | ||
459 | return ran & lim; | ||
460 | } | 445 | } |
446 | lua_assert((lim & (lim + 1)) == 0 /* 'lim + 1' is a power of 2 */ | ||
447 | && lim >= n /* not smaller than 'n' */ | ||
448 | && (lim == 0 || (lim >> 1) < n)); /* it is the smallest one */ | ||
449 | while ((ran & lim) > n) | ||
450 | ran = I2UInt(xorshift128plus(state->s)); | ||
451 | return ran & lim; | ||
461 | } | 452 | } |
462 | 453 | ||
463 | 454 | ||