aboutsummaryrefslogtreecommitdiff
path: root/lmathlib.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2018-03-22 16:54:49 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2018-03-22 16:54:49 -0300
commitc5e3b2f81402773466f2afc8e87839509f65facc (patch)
tree2adaf431b9d1fc41c49fdd6d70541f3883c9e231 /lmathlib.c
parent64867624630b4effacb3d3fb54708ecda19f0221 (diff)
downloadlua-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.c39
1 files changed, 15 insertions, 24 deletions
diff --git a/lmathlib.c b/lmathlib.c
index aa9ef51a..55b44f8b 100644
--- a/lmathlib.c
+++ b/lmathlib.c
@@ -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
439static lua_Unsigned project (lua_Unsigned ran, lua_Unsigned n, 432static 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