Re: master d582356: * src/fns.c (Frandom): Handle bignum `limit`s

[Pip Cet <pipcet@gmail.com>]

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