diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2018-03-05 11:07:48 -0300 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2018-03-05 11:07:48 -0300 |
commit | 66b7b075a65670e8a730c9373d28f971aceb8930 (patch) | |
tree | 952cf018d6353cabf597acc09945c1e14ea6b7a8 /lmathlib.c | |
parent | 62a392ff465b26b39f91a4959895a8330c4eeebd (diff) | |
download | lua-66b7b075a65670e8a730c9373d28f971aceb8930.tar.gz lua-66b7b075a65670e8a730c9373d28f971aceb8930.tar.bz2 lua-66b7b075a65670e8a730c9373d28f971aceb8930.zip |
'math.random' using the xorshift128+ algorithm
Diffstat (limited to 'lmathlib.c')
-rw-r--r-- | lmathlib.c | 231 |
1 files changed, 195 insertions, 36 deletions
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: lmathlib.c,v 1.118 2016/12/20 18:37:00 roberto Exp roberto $ | 2 | ** $Id: lmathlib.c,v 1.119 2016/12/22 13:08:50 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 | */ |
@@ -10,6 +10,7 @@ | |||
10 | #include "lprefix.h" | 10 | #include "lprefix.h" |
11 | 11 | ||
12 | 12 | ||
13 | #include <limits.h> | ||
13 | #include <stdlib.h> | 14 | #include <stdlib.h> |
14 | #include <math.h> | 15 | #include <math.h> |
15 | 16 | ||
@@ -23,19 +24,6 @@ | |||
23 | #define PI (l_mathop(3.141592653589793238462643383279502884)) | 24 | #define PI (l_mathop(3.141592653589793238462643383279502884)) |
24 | 25 | ||
25 | 26 | ||
26 | #if !defined(l_rand) /* { */ | ||
27 | #if defined(LUA_USE_POSIX) | ||
28 | #define l_rand() random() | ||
29 | #define l_srand(x) srandom(x) | ||
30 | #define L_RANDMAX 2147483647 /* (2^31 - 1), following POSIX */ | ||
31 | #else | ||
32 | #define l_rand() rand() | ||
33 | #define l_srand(x) srand(x) | ||
34 | #define L_RANDMAX RAND_MAX | ||
35 | #endif | ||
36 | #endif /* } */ | ||
37 | |||
38 | |||
39 | static int math_abs (lua_State *L) { | 27 | static int math_abs (lua_State *L) { |
40 | if (lua_isinteger(L, 1)) { | 28 | if (lua_isinteger(L, 1)) { |
41 | lua_Integer n = lua_tointeger(L, 1); | 29 | lua_Integer n = lua_tointeger(L, 1); |
@@ -239,22 +227,181 @@ static int math_max (lua_State *L) { | |||
239 | return 1; | 227 | return 1; |
240 | } | 228 | } |
241 | 229 | ||
230 | |||
231 | static int math_type (lua_State *L) { | ||
232 | if (lua_type(L, 1) == LUA_TNUMBER) { | ||
233 | if (lua_isinteger(L, 1)) | ||
234 | lua_pushliteral(L, "integer"); | ||
235 | else | ||
236 | lua_pushliteral(L, "float"); | ||
237 | } | ||
238 | else { | ||
239 | luaL_checkany(L, 1); | ||
240 | lua_pushnil(L); | ||
241 | } | ||
242 | return 1; | ||
243 | } | ||
244 | |||
245 | |||
246 | |||
247 | /* | ||
248 | ** {================================================================== | ||
249 | ** Pseudo-Random Number Generator based on 'xorshift128+'. | ||
250 | ** =================================================================== | ||
251 | */ | ||
252 | |||
253 | |||
254 | #define twotomin53 (1.0 / 9007199254740992.0) /* 2^-53 */ | ||
255 | |||
256 | |||
257 | #if defined(LLONG_MAX) && !defined(LUA_DEBUG) /* { */ | ||
258 | |||
259 | /* | ||
260 | ** Assume long long. | ||
261 | */ | ||
262 | |||
263 | /* a 64-bit value */ | ||
264 | typedef unsigned long long I; | ||
265 | |||
266 | static I xorshift128plus (I *state) { | ||
267 | I x = state[0]; | ||
268 | I y = state[1]; | ||
269 | state[0] = y; | ||
270 | x ^= x << 23; | ||
271 | state[1] = x ^ y ^ (x >> 18) ^ (y >> 5); | ||
272 | return state[1] + y; | ||
273 | } | ||
274 | |||
275 | |||
276 | #define mask53 (~(~0ll << 53)) | ||
277 | |||
278 | /* | ||
279 | ** Convert 53 bits from a random integer into a double in the | ||
280 | ** interval [0,1). | ||
281 | */ | ||
282 | static double I2d (I x) { | ||
283 | return (x & mask53) * twotomin53; | ||
284 | } | ||
285 | |||
286 | /* convert an 'I' to a lua_Integer */ | ||
287 | #define I2Int(x) ((lua_Integer)(x)) | ||
288 | |||
289 | /* convert a lua_Integer to an 'I' */ | ||
290 | #define Int2I(x) ((I)(x)) | ||
291 | |||
292 | #else /* }{ */ | ||
293 | |||
294 | /* | ||
295 | ** No long long; Use two 32-bit integers to represent a 64-bit quantity. | ||
296 | */ | ||
297 | |||
298 | #if LUAI_BITSINT >= 32 | ||
299 | typedef unsigned int lu_int32; | ||
300 | #else | ||
301 | typedef unsigned long lu_int32; | ||
302 | #endif | ||
303 | |||
304 | /* a 64-bit value */ | ||
305 | typedef struct I { | ||
306 | lu_int32 x1, x2; | ||
307 | } I; | ||
308 | |||
309 | |||
310 | /* | ||
311 | ** basic operations on 'I' values | ||
312 | */ | ||
313 | |||
314 | static I pack (int x1, int x2) { | ||
315 | I result; | ||
316 | result.x1 = x1; | ||
317 | result.x2 = x2; | ||
318 | return result; | ||
319 | } | ||
320 | |||
321 | static I Ishl (I i, int n) { | ||
322 | return pack((i.x1 << n) | (i.x2 >> (32 - n)), i.x2 << n); | ||
323 | } | ||
324 | |||
325 | static I Ishr (I i, int n) { | ||
326 | return pack(i.x1 >> n, (i.x2 >> n) | (i.x1 << (32 - n))); | ||
327 | } | ||
328 | |||
329 | static I Ixor (I i1, I i2) { | ||
330 | return pack(i1.x1 ^ i2.x1, i1.x2 ^ i2.x2); | ||
331 | } | ||
332 | |||
333 | static I Iadd (I i1, I i2) { | ||
334 | I result = pack(i1.x1 + i2.x1, i1.x2 + i2.x2); | ||
335 | if (result.x2 < i1.x2) /* carry? */ | ||
336 | result.x1++; | ||
337 | return result; | ||
338 | } | ||
339 | |||
340 | |||
341 | /* | ||
342 | ** implementation of 'xorshift128+' algorithm on 'I' values | ||
343 | */ | ||
344 | static I xorshift128plus (I *state) { | ||
345 | I x = state[0]; | ||
346 | I y = state[1]; | ||
347 | state[0] = y; | ||
348 | x = Ixor(x, Ishl(x, 23)); /* x ^= x << 23; */ | ||
349 | /* s[1] = x ^ y ^ (x >> 18) ^ (y >> 5); */ | ||
350 | state[1] = Ixor(Ixor(Ixor(x, y), Ishr(x, 18)), Ishr(y, 5)); | ||
351 | return Iadd(state[1], y); /* return state[1] + y; */ | ||
352 | } | ||
353 | |||
354 | |||
355 | /* | ||
356 | ** Converts an 'I' into a double, getting its lower half plus 21 | ||
357 | ** (53 - 32) bits from its higher half and joining them into a double. | ||
358 | */ | ||
359 | |||
360 | #define mask32 0xffffffff | ||
361 | #define mask21 (~(~0 << 21)) | ||
362 | |||
363 | #define twoto32 4294967296.0 /* 2^32 */ | ||
364 | |||
365 | static double I2d (I x) { | ||
366 | return ((x.x1 & mask21) * twoto32 + (x.x2 & mask32)) * twotomin53; | ||
367 | } | ||
368 | |||
369 | static lua_Integer I2Int (I x) { | ||
370 | return (((lua_Integer)x.x1 << 31) << 1) | x.x2; | ||
371 | } | ||
372 | |||
373 | static I Int2I (lua_Integer n) { | ||
374 | return pack(n, (n >> 31) >> 1); | ||
375 | } | ||
376 | |||
377 | #endif /* } */ | ||
378 | |||
379 | |||
242 | /* | 380 | /* |
243 | ** This function uses 'double' (instead of 'lua_Number') to ensure that | 381 | ** A state uses two 'I' values. |
244 | ** all bits from 'l_rand' can be represented, and that 'RANDMAX + 1.0' | ||
245 | ** will keep full precision (ensuring that 'r' is always less than 1.0.) | ||
246 | */ | 382 | */ |
383 | typedef struct { | ||
384 | I s[2]; | ||
385 | } RanState; | ||
386 | |||
387 | |||
247 | static int math_random (lua_State *L) { | 388 | static int math_random (lua_State *L) { |
248 | lua_Integer low, up; | 389 | lua_Integer low, up; |
249 | double r = (double)l_rand() * (1.0 / ((double)L_RANDMAX + 1.0)); | 390 | double r; |
391 | RanState *state = (RanState *)lua_touserdata(L, lua_upvalueindex(1)); | ||
392 | I rv = xorshift128plus(state->s); /* next pseudo-random value */ | ||
250 | switch (lua_gettop(L)) { /* check number of arguments */ | 393 | switch (lua_gettop(L)) { /* check number of arguments */ |
251 | case 0: { /* no arguments */ | 394 | case 0: { /* no arguments */ |
252 | lua_pushnumber(L, (lua_Number)r); /* Number between 0 and 1 */ | 395 | lua_pushnumber(L, (lua_Number)I2d(rv)); /* float between 0 and 1 */ |
253 | return 1; | 396 | return 1; |
254 | } | 397 | } |
255 | case 1: { /* only upper limit */ | 398 | case 1: { /* only upper limit */ |
256 | low = 1; | 399 | low = 1; |
257 | up = luaL_checkinteger(L, 1); | 400 | up = luaL_checkinteger(L, 1); |
401 | if (up == 0) { /* single 0 as argument? */ | ||
402 | lua_pushinteger(L, I2Int(rv)); /* full random integer */ | ||
403 | return 1; | ||
404 | } | ||
258 | break; | 405 | break; |
259 | } | 406 | } |
260 | case 2: { /* lower and upper limits */ | 407 | case 2: { /* lower and upper limits */ |
@@ -268,33 +415,44 @@ static int math_random (lua_State *L) { | |||
268 | luaL_argcheck(L, low <= up, 1, "interval is empty"); | 415 | luaL_argcheck(L, low <= up, 1, "interval is empty"); |
269 | luaL_argcheck(L, low >= 0 || up <= LUA_MAXINTEGER + low, 1, | 416 | luaL_argcheck(L, low >= 0 || up <= LUA_MAXINTEGER + low, 1, |
270 | "interval too large"); | 417 | "interval too large"); |
271 | r *= (double)(up - low) + 1.0; | 418 | r = I2d(rv); /* convert random value to a double */ |
419 | r *= (double)(up - low) + 1.0; /* scale it */ | ||
272 | lua_pushinteger(L, (lua_Integer)r + low); | 420 | lua_pushinteger(L, (lua_Integer)r + low); |
273 | return 1; | 421 | return 1; |
274 | } | 422 | } |
275 | 423 | ||
276 | 424 | ||
425 | static void setseed (I *state, lua_Integer n) { | ||
426 | int i; | ||
427 | state[0] = Int2I(n); | ||
428 | state[1] = Int2I(~n); | ||
429 | for (i = 0; i < 16; i++) | ||
430 | xorshift128plus(state); /* discard initial values */ | ||
431 | } | ||
432 | |||
433 | |||
277 | static int math_randomseed (lua_State *L) { | 434 | static int math_randomseed (lua_State *L) { |
278 | l_srand((unsigned int)(lua_Integer)luaL_checknumber(L, 1)); | 435 | RanState *state = (RanState *)lua_touserdata(L, lua_upvalueindex(1)); |
279 | (void)l_rand(); /* discard first value to avoid undesirable correlations */ | 436 | lua_Integer n = luaL_checkinteger(L, 1); |
437 | setseed(state->s, n); | ||
280 | return 0; | 438 | return 0; |
281 | } | 439 | } |
282 | 440 | ||
283 | 441 | ||
284 | static int math_type (lua_State *L) { | 442 | static const luaL_Reg randfuncs[] = { |
285 | if (lua_type(L, 1) == LUA_TNUMBER) { | 443 | {"random", math_random}, |
286 | if (lua_isinteger(L, 1)) | 444 | {"randomseed", math_randomseed}, |
287 | lua_pushliteral(L, "integer"); | 445 | {NULL, NULL} |
288 | else | 446 | }; |
289 | lua_pushliteral(L, "float"); | 447 | |
290 | } | 448 | static void setrandfunc (lua_State *L) { |
291 | else { | 449 | RanState *state = (RanState *)lua_newuserdatauv(L, sizeof(RanState), 0); |
292 | luaL_checkany(L, 1); | 450 | setseed(state->s, 0); |
293 | lua_pushnil(L); | 451 | luaL_setfuncs(L, randfuncs, 1); |
294 | } | ||
295 | return 1; | ||
296 | } | 452 | } |
297 | 453 | ||
454 | /* }================================================================== */ | ||
455 | |||
298 | 456 | ||
299 | /* | 457 | /* |
300 | ** {================================================================== | 458 | ** {================================================================== |
@@ -367,8 +525,6 @@ static const luaL_Reg mathlib[] = { | |||
367 | {"min", math_min}, | 525 | {"min", math_min}, |
368 | {"modf", math_modf}, | 526 | {"modf", math_modf}, |
369 | {"rad", math_rad}, | 527 | {"rad", math_rad}, |
370 | {"random", math_random}, | ||
371 | {"randomseed", math_randomseed}, | ||
372 | {"sin", math_sin}, | 528 | {"sin", math_sin}, |
373 | {"sqrt", math_sqrt}, | 529 | {"sqrt", math_sqrt}, |
374 | {"tan", math_tan}, | 530 | {"tan", math_tan}, |
@@ -384,6 +540,8 @@ static const luaL_Reg mathlib[] = { | |||
384 | {"log10", math_log10}, | 540 | {"log10", math_log10}, |
385 | #endif | 541 | #endif |
386 | /* placeholders */ | 542 | /* placeholders */ |
543 | {"random", NULL}, | ||
544 | {"randomseed", NULL}, | ||
387 | {"pi", NULL}, | 545 | {"pi", NULL}, |
388 | {"huge", NULL}, | 546 | {"huge", NULL}, |
389 | {"maxinteger", NULL}, | 547 | {"maxinteger", NULL}, |
@@ -405,6 +563,7 @@ LUAMOD_API int luaopen_math (lua_State *L) { | |||
405 | lua_setfield(L, -2, "maxinteger"); | 563 | lua_setfield(L, -2, "maxinteger"); |
406 | lua_pushinteger(L, LUA_MININTEGER); | 564 | lua_pushinteger(L, LUA_MININTEGER); |
407 | lua_setfield(L, -2, "mininteger"); | 565 | lua_setfield(L, -2, "mininteger"); |
566 | setrandfunc(L); | ||
408 | return 1; | 567 | return 1; |
409 | } | 568 | } |
410 | 569 | ||