aboutsummaryrefslogtreecommitdiff
path: root/lmathlib.c
diff options
context:
space:
mode:
authorRoberto Ierusalimschy <roberto@inf.puc-rio.br>2018-03-05 11:07:48 -0300
committerRoberto Ierusalimschy <roberto@inf.puc-rio.br>2018-03-05 11:07:48 -0300
commit66b7b075a65670e8a730c9373d28f971aceb8930 (patch)
tree952cf018d6353cabf597acc09945c1e14ea6b7a8 /lmathlib.c
parent62a392ff465b26b39f91a4959895a8330c4eeebd (diff)
downloadlua-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.c231
1 files changed, 195 insertions, 36 deletions
diff --git a/lmathlib.c b/lmathlib.c
index e0240c9b..708a19c0 100644
--- a/lmathlib.c
+++ b/lmathlib.c
@@ -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
39static int math_abs (lua_State *L) { 27static 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
231static 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 */
264typedef unsigned long long I;
265
266static 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*/
282static 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
299typedef unsigned int lu_int32;
300#else
301typedef unsigned long lu_int32;
302#endif
303
304/* a 64-bit value */
305typedef struct I {
306 lu_int32 x1, x2;
307} I;
308
309
310/*
311** basic operations on 'I' values
312*/
313
314static I pack (int x1, int x2) {
315 I result;
316 result.x1 = x1;
317 result.x2 = x2;
318 return result;
319}
320
321static I Ishl (I i, int n) {
322 return pack((i.x1 << n) | (i.x2 >> (32 - n)), i.x2 << n);
323}
324
325static I Ishr (I i, int n) {
326 return pack(i.x1 >> n, (i.x2 >> n) | (i.x1 << (32 - n)));
327}
328
329static I Ixor (I i1, I i2) {
330 return pack(i1.x1 ^ i2.x1, i1.x2 ^ i2.x2);
331}
332
333static 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*/
344static 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
365static double I2d (I x) {
366 return ((x.x1 & mask21) * twoto32 + (x.x2 & mask32)) * twotomin53;
367}
368
369static lua_Integer I2Int (I x) {
370 return (((lua_Integer)x.x1 << 31) << 1) | x.x2;
371}
372
373static 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*/
383typedef struct {
384 I s[2];
385} RanState;
386
387
247static int math_random (lua_State *L) { 388static 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
425static 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
277static int math_randomseed (lua_State *L) { 434static 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
284static int math_type (lua_State *L) { 442static 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 } 448static 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