[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
master d582356: * src/fns.c (Frandom): Handle bignum `limit`s
From: |
Stefan Monnier |
Subject: |
master d582356: * src/fns.c (Frandom): Handle bignum `limit`s |
Date: |
Fri, 5 Mar 2021 12:09:57 -0500 (EST) |
branch: master
commit d582356a7f704f8a209a3ef31d6ea970520c6224
Author: Stefan Monnier <monnier@iro.umontreal.ca>
Commit: Stefan Monnier <monnier@iro.umontreal.ca>
* src/fns.c (Frandom): Handle bignum `limit`s
(ccall2, get_random_bignum): New functions.
---
doc/lispref/numbers.texi | 2 +-
src/fns.c | 53 +++++++++++++++++++++++++++++++++++++++++++++++-
2 files changed, 53 insertions(+), 2 deletions(-)
diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi
index 63e3e0b..4c5f7212 100644
--- a/doc/lispref/numbers.texi
+++ b/doc/lispref/numbers.texi
@@ -1250,7 +1250,7 @@ other strings to choose various seed values.
This function returns a pseudo-random integer. Repeated calls return a
series of pseudo-random integers.
-If @var{limit} is a positive fixnum, the value is chosen to be
+If @var{limit} is a positive integer, the value is chosen to be
nonnegative and less than @var{limit}. Otherwise, the value might be
any fixnum, i.e., any integer from @code{most-negative-fixnum} through
@code{most-positive-fixnum} (@pxref{Integer Basics}).
diff --git a/src/fns.c b/src/fns.c
index 7914bd4..b193ad6 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -54,10 +54,55 @@ DEFUN ("identity", Fidentity, Sidentity, 1, 1, 0,
return argument;
}
+static Lisp_Object
+ccall2 (Lisp_Object (f) (ptrdiff_t nargs, Lisp_Object *args),
+ Lisp_Object arg1, Lisp_Object arg2)
+{
+ Lisp_Object args[2] = {arg1, arg2};
+ return f (2, args);
+}
+
+static Lisp_Object
+get_random_bignum (Lisp_Object limit)
+{
+ /* This is a naive transcription into bignums of the fixnum algorithm.
+ I'd be quite surprised if that's anywhere near the best algorithm
+ for it. */
+ while (true)
+ {
+ Lisp_Object val = make_fixnum (0);
+ Lisp_Object lim = limit;
+ int bits = 0;
+ int bitsperiteration = FIXNUM_BITS - 1;
+ do
+ {
+ /* Shift by one so it is a valid positive fixnum. */
+ EMACS_INT rand = get_random () >> 1;
+ Lisp_Object lrand = make_fixnum (rand);
+ bits += bitsperiteration;
+ val = ccall2 (Flogior,
+ Fash (val, make_fixnum (bitsperiteration)),
+ lrand);
+ lim = Fash (lim, make_fixnum (- bitsperiteration));
+ }
+ while (!EQ (lim, make_fixnum (0)));
+ /* Return the remainder, except reject the rare case where
+ get_random returns a number so close to INTMASK that the
+ remainder isn't random. */
+ Lisp_Object remainder = Frem (val, limit);
+ if (!NILP (ccall2 (Fleq,
+ ccall2 (Fminus, val, remainder),
+ ccall2 (Fminus,
+ Fash (make_fixnum (1), make_fixnum (bits)),
+ limit))))
+ return remainder;
+ }
+}
+
DEFUN ("random", Frandom, Srandom, 0, 1, 0,
doc: /* Return a pseudo-random integer.
By default, return a fixnum; all fixnums are equally likely.
-With positive fixnum LIMIT, return random integer in interval [0,LIMIT).
+With positive integer LIMIT, return random integer in interval [0,LIMIT).
With argument t, set the random number seed from the system's entropy
pool if available, otherwise from less-random volatile data such as the time.
With a string argument, set the seed based on the string's contents.
@@ -71,6 +116,12 @@ See Info node `(elisp)Random Numbers' for more details. */)
init_random ();
else if (STRINGP (limit))
seed_random (SSDATA (limit), SBYTES (limit));
+ if (BIGNUMP (limit))
+ {
+ if (0 > mpz_sgn (*xbignum_val (limit)))
+ xsignal2 (Qwrong_type_argument, Qnatnump, limit);
+ return get_random_bignum (limit);
+ }
val = get_random ();
if (FIXNUMP (limit) && 0 < XFIXNUM (limit))
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- master d582356: * src/fns.c (Frandom): Handle bignum `limit`s,
Stefan Monnier <=