diff options
| author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2025-03-27 15:22:40 -0300 |
|---|---|---|
| committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2025-03-27 15:22:40 -0300 |
| commit | 37a1b72706b6e55e60b8d73bcbe269921976825e (patch) | |
| tree | 4584d132e9b9f963faba8ed8199ef470cb5cab47 /lmathlib.c | |
| parent | ef5d171cc89b19ac1fea905b99d819b5f97cba00 (diff) | |
| download | lua-37a1b72706b6e55e60b8d73bcbe269921976825e.tar.gz lua-37a1b72706b6e55e60b8d73bcbe269921976825e.tar.bz2 lua-37a1b72706b6e55e60b8d73bcbe269921976825e.zip | |
Small optimization in 'project' from math.random
When computing the Mersenne number, instead of spreading 1's a fixed
number of times (with shifts of 1, 2, 4, 8, 16, and 32), spread only
until the number becomes a Mersenne number.
Diffstat (limited to 'lmathlib.c')
| -rw-r--r-- | lmathlib.c | 30 |
1 files changed, 9 insertions, 21 deletions
| @@ -533,7 +533,7 @@ typedef struct { | |||
| 533 | ** Project the random integer 'ran' into the interval [0, n]. | 533 | ** Project the random integer 'ran' into the interval [0, n]. |
| 534 | ** Because 'ran' has 2^B possible values, the projection can only be | 534 | ** Because 'ran' has 2^B possible values, the projection can only be |
| 535 | ** uniform when the size of the interval is a power of 2 (exact | 535 | ** uniform when the size of the interval is a power of 2 (exact |
| 536 | ** division). Otherwise, to get a uniform projection into [0, n], we | 536 | ** division). So, to get a uniform projection into [0, n], we |
| 537 | ** first compute 'lim', the smallest Mersenne number not smaller than | 537 | ** first compute 'lim', the smallest Mersenne number not smaller than |
| 538 | ** 'n'. We then project 'ran' into the interval [0, lim]. If the result | 538 | ** 'n'. We then project 'ran' into the interval [0, lim]. If the result |
| 539 | ** is inside [0, n], we are done. Otherwise, we try with another 'ran', | 539 | ** is inside [0, n], we are done. Otherwise, we try with another 'ran', |
| @@ -541,26 +541,14 @@ typedef struct { | |||
| 541 | */ | 541 | */ |
| 542 | static lua_Unsigned project (lua_Unsigned ran, lua_Unsigned n, | 542 | static lua_Unsigned project (lua_Unsigned ran, lua_Unsigned n, |
| 543 | RanState *state) { | 543 | RanState *state) { |
| 544 | if ((n & (n + 1)) == 0) /* is 'n + 1' a power of 2? */ | 544 | lua_Unsigned lim = n; /* to compute the Mersenne number */ |
| 545 | return ran & n; /* no bias */ | 545 | int sh; /* how much to spread bits to the right in 'lim' */ |
| 546 | else { | 546 | /* spread '1' bits in 'lim' until it becomes a Mersenne number */ |
| 547 | lua_Unsigned lim = n; | 547 | for (sh = 1; (lim & (lim + 1)) != 0; sh *= 2) |
| 548 | /* compute the smallest (2^b - 1) not smaller than 'n' */ | 548 | lim |= (lim >> sh); /* spread '1's to the right */ |
| 549 | lim |= (lim >> 1); | 549 | while ((ran &= lim) > n) /* project 'ran' into [0..lim] and test */ |
| 550 | lim |= (lim >> 2); | 550 | ran = I2UInt(nextrand(state->s)); /* not inside [0..n]? try again */ |
| 551 | lim |= (lim >> 4); | 551 | return ran; |
| 552 | lim |= (lim >> 8); | ||
| 553 | lim |= (lim >> 16); | ||
| 554 | #if (LUA_MAXUNSIGNED >> 31) >= 3 | ||
| 555 | lim |= (lim >> 32); /* integer type has more than 32 bits */ | ||
| 556 | #endif | ||
| 557 | lua_assert((lim & (lim + 1)) == 0 /* 'lim + 1' is a power of 2, */ | ||
| 558 | && lim >= n /* not smaller than 'n', */ | ||
| 559 | && (lim >> 1) < n); /* and it is the smallest one */ | ||
| 560 | while ((ran &= lim) > n) /* project 'ran' into [0..lim] */ | ||
| 561 | ran = I2UInt(nextrand(state->s)); /* not inside [0..n]? try again */ | ||
| 562 | return ran; | ||
| 563 | } | ||
| 564 | } | 552 | } |
| 565 | 553 | ||
| 566 | 554 | ||