From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Pip Cet Newsgroups: gmane.emacs.devel Subject: Re: master d582356: * src/fns.c (Frandom): Handle bignum `limit`s Date: Fri, 5 Mar 2021 19:42:09 +0000 Message-ID: References: <20210305170955.27732.27579@vcs0.savannah.gnu.org> <20210305170957.AF99920E1B@vcs0.savannah.gnu.org> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="25042"; mail-complaints-to="usenet@ciao.gmane.io" To: emacs-devel@gnu.org, Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Fri Mar 05 20:43:39 2021 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1lIGML-0006Nq-Rk for ged-emacs-devel@m.gmane-mx.org; Fri, 05 Mar 2021 20:43:37 +0100 Original-Received: from localhost ([::1]:50722 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1lIGMK-0007lE-ST for ged-emacs-devel@m.gmane-mx.org; Fri, 05 Mar 2021 14:43:36 -0500 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:42500) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1lIGLd-0007A1-5w for emacs-devel@gnu.org; Fri, 05 Mar 2021 14:42:53 -0500 Original-Received: from mail-ot1-x335.google.com ([2607:f8b0:4864:20::335]:43525) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1lIGLa-00025y-0g for emacs-devel@gnu.org; Fri, 05 Mar 2021 14:42:52 -0500 Original-Received: by mail-ot1-x335.google.com with SMTP id v12so2911259ott.10 for ; Fri, 05 Mar 2021 11:42:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=S17VDG67AfhYFA7DD0nutoOwccwpms3b/zy43Jfiq7M=; b=g5ZRqcO9bbdwReXIyTiR2XgWZsawuld9XbtELdQueo97EIISg5vZvyino7V6YKLIn8 TQZksiETByQ4XktDus1tMy4xNZIL12TGTx18DYKNd3Jgjpgkh3YhVUMRiPEYytxUG7Hd gx+pWaAZffhs7WOLOxU69vlA8i1/CuB5B23T0kEIysyvBOuw9p6rtb73sd1GDWuWxUYu vUl/R1sHUE5U2deX9oxl50rF91BVOPBzj95umTNgbercwSZYj2p7XH4Kd6wjxoIn/lRO TukO40HOpbRPCkTzwEJUXBW8GoBLA3iJrEo5Lko+vgLZrT1ScPc9KVdxAZeqxDuWcI8I U3vg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=S17VDG67AfhYFA7DD0nutoOwccwpms3b/zy43Jfiq7M=; b=pEqRAiC39qzd9dLDwY6U/KD5ZHrVxVj+O9YTdmZMvVL1urIkoHAOwu7Ha2zj6K+11c j2xGcmWfV9lGAGDqIsiBD9FxdMsYrnhlT8Ws/RA94kLdm7knMXHcOQ3u+tuCA4ilj7sh U9E692mKB99t0lm4UUITbb3KUeHp0HksXPJsIhl1REaHpYDqC+hvsuJ3DZ2x6UaStICR oKM9orvvy+MPhvIquqA+/ITC6HpA2dFDYA3Gd99/Z9HaJJVf8Nk/oxH86OmGR89GsKtR hgYXJloDVQze+JB7S1Y72qrMcuuWMPxH5Z7SBL1R4U6WoqVgZ1XkzQeZzFNG2pZkvh+H exkA== X-Gm-Message-State: AOAM531Mf59chwzZOVLcT+i3GSJYfWuq3XYk62Q9EtTrHchuvqcNjJUp 9fJWs8/MWTM7J5yE3u1ltA0yrAO66bX6bGXS8qng30iJJuI= X-Google-Smtp-Source: ABdhPJxL5CuJI7iVqGCeMcFWX7YTZIdq67VeohpVOLiO756M7cHMwErU9kYaMy4/bJJi8tf2uUA/8PkdqdoXS3ihn08= X-Received: by 2002:a05:6830:1e51:: with SMTP id e17mr9284255otj.292.1614973366335; Fri, 05 Mar 2021 11:42:46 -0800 (PST) In-Reply-To: <20210305170957.AF99920E1B@vcs0.savannah.gnu.org> Received-SPF: pass client-ip=2607:f8b0:4864:20::335; envelope-from=pipcet@gmail.com; helo=mail-ot1-x335.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:266037 Archived-At: On Fri, Mar 5, 2021 at 5:28 PM Stefan Monnier wrote: > branch: master > commit d582356a7f704f8a209a3ef31d6ea970520c6224 > Author: Stefan Monnier > Commit: Stefan Monnier > > * 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