From: Pip Cet <pipcet@gmail.com>
To: emacs-devel@gnu.org, Stefan Monnier <monnier@iro.umontreal.ca>
Subject: Re: master d582356: * src/fns.c (Frandom): Handle bignum `limit`s
Date: Fri, 5 Mar 2021 19:42:09 +0000 [thread overview]
Message-ID: <CAOqdjBfocJseE-Ht-9f-ga+R-5LduFqBqgDbTA5UJPMeS6i0vA@mail.gmail.com> (raw)
In-Reply-To: <20210305170957.AF99920E1B@vcs0.savannah.gnu.org>
On Fri, Mar 5, 2021 at 5:28 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:
> 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
Should we add "with every value equally likely" here, or is that
perfectly obvious?
> 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);
> +}
Can't we use CALLN?
> +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
No longer INTMASK.
> + 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;
Whenever I see that algorithm, I think it can't possibly be correct,
but it is :-)
> + }
> +}
> +
> 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.
That docstring always tricks me into thinking "oh, don't worry about
passing something invalid, you'll get an error", when in fact, you get
a fixnum. (random -1)? Random fixnum. (random 1.0)? Random fixnum.
(random 'many)? Random fixnum.
> @@ -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);
It's inconsistent for this function to handle the negative bignum case
correctly.
But I'm really writing to ask whether it might be a good idea to add
float support while we're there. I'll leave uniformly-distributed big
ratios as an exercise for the reader ;-)
And,all of this could happen in Lisp, couldn't it? Should it?
Pip
next parent reply other threads:[~2021-03-05 19:42 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <20210305170955.27732.27579@vcs0.savannah.gnu.org>
[not found] ` <20210305170957.AF99920E1B@vcs0.savannah.gnu.org>
2021-03-05 19:42 ` Pip Cet [this message]
2021-03-05 19:56 ` master d582356: * src/fns.c (Frandom): Handle bignum `limit`s Stefan Monnier
2021-03-05 20:13 ` Pip Cet
2021-03-05 20:34 ` Stefan Monnier
2021-03-06 7:42 ` Pip Cet
2021-03-06 8:44 ` Eli Zaretskii
2021-03-06 9:44 ` Pip Cet
2021-03-06 10:56 ` Eli Zaretskii
2021-03-06 13:22 ` Pip Cet
2021-03-06 14:45 ` Eli Zaretskii
2021-03-07 13:27 ` Pip Cet
2021-03-07 14:04 ` Eli Zaretskii
2021-03-07 14:21 ` Pip Cet
2021-03-07 15:22 ` Eli Zaretskii
2021-03-07 17:23 ` Pip Cet
2021-03-07 17:47 ` Eli Zaretskii
2021-03-07 18:37 ` Stefan Monnier
2021-03-07 19:54 ` Andrea Corallo via Emacs development discussions.
2021-03-07 19:55 ` Pip Cet
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAOqdjBfocJseE-Ht-9f-ga+R-5LduFqBqgDbTA5UJPMeS6i0vA@mail.gmail.com \
--to=pipcet@gmail.com \
--cc=emacs-devel@gnu.org \
--cc=monnier@iro.umontreal.ca \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.