From unknown Sun Jun 15 08:54:28 2025 X-Loop: help-debbugs@gnu.org Subject: bug#38753: 27.0.60; cl--random-state uncontrolled growth due to bignums Resent-From: Christopher Wellons Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Thu, 26 Dec 2019 17:13:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 38753 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: To: 38753@debbugs.gnu.org X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Received: via spool by submit@debbugs.gnu.org id=B.157738033423537 (code B ref -1); Thu, 26 Dec 2019 17:13:02 +0000 Received: (at submit) by debbugs.gnu.org; 26 Dec 2019 17:12:14 +0000 Received: from localhost ([127.0.0.1]:56152 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ikWgH-00067Y-Tr for submit@debbugs.gnu.org; Thu, 26 Dec 2019 12:12:14 -0500 Received: from lists.gnu.org ([209.51.188.17]:48124) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ikWgF-00067Q-Fi for submit@debbugs.gnu.org; Thu, 26 Dec 2019 12:12:12 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:48143) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ikWgE-0001n0-E8 for bug-gnu-emacs@gnu.org; Thu, 26 Dec 2019 12:12:11 -0500 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ikWgD-0000Ax-EE for bug-gnu-emacs@gnu.org; Thu, 26 Dec 2019 12:12:10 -0500 Received: from mail.nullprogram.com ([192.241.191.137]:52338) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1ikWgD-0000Aj-BK for bug-gnu-emacs@gnu.org; Thu, 26 Dec 2019 12:12:09 -0500 Received: from nullprogram.com (localhost [127.0.0.1]) by mail.nullprogram.com (Postfix) with ESMTPS id 4973FC5332 for ; Thu, 26 Dec 2019 12:12:08 -0500 (EST) Date: Thu, 26 Dec 2019 12:12:07 -0500 From: Christopher Wellons Message-ID: <20191226171207.cepft7cjmmbuow6o@nullprogram.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline User-Agent: NeoMutt/20170113 (1.7.2) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 192.241.191.137 X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) The cl-random generator was not written for bignums, so it misbehaves in Emacs 27. After generating a few million numbers from any particular state, it will only signal "Arithmetic overflow error". The generator relies on fixnums wrapping via two's complement. In Emacs 27, fixnums turn into bignums rather than wrap, so the state grows until reaching the bignum limit, then breaks. The cl-random function is a lagged Fibonacci generator. The output is the difference of two integers at special "taps" in the state vector, and one tap is replaced with the output. The output is properly truncated using logand, but state update is not, and it soon fills with growing bignums. The fix is trivial: Move the logand truncation so that it applies to both the output and the state update. The truncated bits are never used so the output of the generator remains unchanged. diff --git a/lisp/emacs-lisp/cl-extra.el b/lisp/emacs-lisp/cl-extra.el index 7e9d8fe870..2e0b37c14d 100644 --- a/lisp/emacs-lisp/cl-extra.el +++ b/lisp/emacs-lisp/cl-extra.el @@ -469,7 +469,7 @@ cl-random (while (< (setq i (1+ i)) 200) (cl-random 2 state)))) (let* ((i (cl-callf (lambda (x) (% (1+ x) 55)) (cl--random-state-i state))) (j (cl-callf (lambda (x) (% (1+ x) 55)) (cl--random-state-j state))) - (n (logand 8388607 (aset vec i (- (aref vec i) (aref vec j)))))) + (n (aset vec i (logand 8388607 (- (aref vec i) (aref vec j)))))) (if (integerp lim) (if (<= lim 512) (% n lim) (if (> lim 8388607) (setq n (+ (ash n 9) (cl-random 512 state)))) From unknown Sun Jun 15 08:54:28 2025 MIME-Version: 1.0 X-Mailer: MIME-tools 5.505 (Entity 5.505) X-Loop: help-debbugs@gnu.org From: help-debbugs@gnu.org (GNU bug Tracking System) To: Christopher Wellons Subject: bug#38753: closed (bug#38753: 27.0.60; cl--random-state uncontrolled growth due to bignums) Message-ID: References: <1A4F12F2-5DE3-4F42-8956-BD2DD27C4D47@acm.org> <20191226171207.cepft7cjmmbuow6o@nullprogram.com> X-Gnu-PR-Message: they-closed 38753 X-Gnu-PR-Package: emacs Reply-To: 38753@debbugs.gnu.org Date: Sun, 29 Dec 2019 13:00:02 +0000 Content-Type: multipart/mixed; boundary="----------=_1577624402-11429-1" This is a multi-part message in MIME format... ------------=_1577624402-11429-1 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Your bug report #38753: 27.0.60; cl--random-state uncontrolled growth due to bignums which was filed against the emacs package, has been closed. The explanation is attached below, along with your original report. If you require more details, please reply to 38753@debbugs.gnu.org. --=20 38753: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=3D38753 GNU Bug Tracking System Contact help-debbugs@gnu.org with problems ------------=_1577624402-11429-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at 38753-done) by debbugs.gnu.org; 29 Dec 2019 12:59:43 +0000 Received: from localhost ([127.0.0.1]:59345 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ilYAY-0002xU-Te for submit@debbugs.gnu.org; Sun, 29 Dec 2019 07:59:43 -0500 Received: from mail1458c50.megamailservers.eu ([91.136.14.58]:41742 helo=mail267c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ilYAX-0002xH-6X for 38753-done@debbugs.gnu.org; Sun, 29 Dec 2019 07:59:42 -0500 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1577624374; bh=0u9st1LZCcmRDzAF2VutKmk1dlQUbeddCmDGHab8IIk=; h=From:Subject:Date:To:From; b=iRnLOm00dJm+ng6+KcLlmx3mk4+SFyOkvtHCV3UwS5a0POPdZlwQxcqgw5f2eXoWJ sLOQ+cZAPtIBSnIRjZ6WJzD5V4eztJHw7DjBUETimNQgjgbcWmviiaxmvsqhtQKV5e JwK/m2G3ztKd5wAWiP/c+5wXqbfUJbWYFWKBUOvM= Feedback-ID: mattiase@acm.or Received: from [192.168.0.4] (c188-150-171-71.bredband.comhem.se [188.150.171.71]) (authenticated bits=0) by mail267c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id xBTCxWoG019668 for <38753-done@debbugs.gnu.org>; Sun, 29 Dec 2019 12:59:33 +0000 From: =?utf-8?Q?Mattias_Engdeg=C3=A5rd?= Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\)) Subject: bug#38753: 27.0.60; cl--random-state uncontrolled growth due to bignums Message-Id: <1A4F12F2-5DE3-4F42-8956-BD2DD27C4D47@acm.org> Date: Sun, 29 Dec 2019 13:59:31 +0100 To: 38753-done@debbugs.gnu.org X-Mailer: Apple Mail (2.3445.104.11) X-CTCH-RefID: str=0001.0A0B0210.5E08A336.0002, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-CSC: 0 X-CHA: v=2.3 cv=OY7m8SbY c=1 sm=1 tr=0 a=SF+I6pRkHZhrawxbOkkvaA==:117 a=SF+I6pRkHZhrawxbOkkvaA==:17 a=kj9zAlcOel0A:10 a=Zf8PuZVA_9kA:10 a=M51BFTxLslgA:10 a=95ZTNanrhPxpY_uQ8mcA:9 a=CjuIK1q_8ugA:10 X-Spam-Score: 1.0 (+) X-Debbugs-Envelope-To: 38753-done X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.0 (/) Thank you! The proposed fix indeed looks correct; applied to emacs-27. ------------=_1577624402-11429-1 Content-Type: message/rfc822 Content-Disposition: inline Content-Transfer-Encoding: 7bit Received: (at submit) by debbugs.gnu.org; 26 Dec 2019 17:12:14 +0000 Received: from localhost ([127.0.0.1]:56152 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ikWgH-00067Y-Tr for submit@debbugs.gnu.org; Thu, 26 Dec 2019 12:12:14 -0500 Received: from lists.gnu.org ([209.51.188.17]:48124) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ikWgF-00067Q-Fi for submit@debbugs.gnu.org; Thu, 26 Dec 2019 12:12:12 -0500 Received: from eggs.gnu.org ([2001:470:142:3::10]:48143) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1ikWgE-0001n0-E8 for bug-gnu-emacs@gnu.org; Thu, 26 Dec 2019 12:12:11 -0500 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on eggs.gnu.org X-Spam-Level: X-Spam-Status: No, score=0.8 required=5.0 tests=BAYES_50 autolearn=disabled version=3.3.2 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1ikWgD-0000Ax-EE for bug-gnu-emacs@gnu.org; Thu, 26 Dec 2019 12:12:10 -0500 Received: from mail.nullprogram.com ([192.241.191.137]:52338) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1ikWgD-0000Aj-BK for bug-gnu-emacs@gnu.org; Thu, 26 Dec 2019 12:12:09 -0500 Received: from nullprogram.com (localhost [127.0.0.1]) by mail.nullprogram.com (Postfix) with ESMTPS id 4973FC5332 for ; Thu, 26 Dec 2019 12:12:08 -0500 (EST) Date: Thu, 26 Dec 2019 12:12:07 -0500 From: Christopher Wellons To: bug-gnu-emacs@gnu.org Subject: 27.0.60; cl--random-state uncontrolled growth due to bignums Message-ID: <20191226171207.cepft7cjmmbuow6o@nullprogram.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline User-Agent: NeoMutt/20170113 (1.7.2) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 192.241.191.137 X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) The cl-random generator was not written for bignums, so it misbehaves in Emacs 27. After generating a few million numbers from any particular state, it will only signal "Arithmetic overflow error". The generator relies on fixnums wrapping via two's complement. In Emacs 27, fixnums turn into bignums rather than wrap, so the state grows until reaching the bignum limit, then breaks. The cl-random function is a lagged Fibonacci generator. The output is the difference of two integers at special "taps" in the state vector, and one tap is replaced with the output. The output is properly truncated using logand, but state update is not, and it soon fills with growing bignums. The fix is trivial: Move the logand truncation so that it applies to both the output and the state update. The truncated bits are never used so the output of the generator remains unchanged. diff --git a/lisp/emacs-lisp/cl-extra.el b/lisp/emacs-lisp/cl-extra.el index 7e9d8fe870..2e0b37c14d 100644 --- a/lisp/emacs-lisp/cl-extra.el +++ b/lisp/emacs-lisp/cl-extra.el @@ -469,7 +469,7 @@ cl-random (while (< (setq i (1+ i)) 200) (cl-random 2 state)))) (let* ((i (cl-callf (lambda (x) (% (1+ x) 55)) (cl--random-state-i state))) (j (cl-callf (lambda (x) (% (1+ x) 55)) (cl--random-state-j state))) - (n (logand 8388607 (aset vec i (- (aref vec i) (aref vec j)))))) + (n (aset vec i (logand 8388607 (- (aref vec i) (aref vec j)))))) (if (integerp lim) (if (<= lim 512) (% n lim) (if (> lim 8388607) (setq n (+ (ash n 9) (cl-random 512 state)))) ------------=_1577624402-11429-1-- From unknown Sun Jun 15 08:54:28 2025 X-Loop: help-debbugs@gnu.org Subject: bug#38753: 27.0.60; cl--random-state uncontrolled growth due to bignums Resent-From: Pip Cet Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 29 Dec 2019 13:33:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 38753 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: To: Christopher Wellons Cc: 38753@debbugs.gnu.org Received: via spool by 38753-submit@debbugs.gnu.org id=B38753.157762633414745 (code B ref 38753); Sun, 29 Dec 2019 13:33:02 +0000 Received: (at 38753) by debbugs.gnu.org; 29 Dec 2019 13:32:14 +0000 Received: from localhost ([127.0.0.1]:59359 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ilYg1-0003pk-Nr for submit@debbugs.gnu.org; Sun, 29 Dec 2019 08:32:13 -0500 Received: from mail-ot1-f52.google.com ([209.85.210.52]:34253) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ilYfz-0003pT-Oi for 38753@debbugs.gnu.org; Sun, 29 Dec 2019 08:32:12 -0500 Received: by mail-ot1-f52.google.com with SMTP id a15so42845886otf.1 for <38753@debbugs.gnu.org>; Sun, 29 Dec 2019 05:32:11 -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 :cc; bh=Qy6tDlZMg/W4YNqm7Cn2+L7X5Xotl6MG7hZ+z9QmJUw=; b=r6JSoQzP+ZSpC95n0UJiqG+EKJKQaxUKEcmTeZxPhIeqNKcwr67oRKfsuTpLmCJM89 1MM5JQBqlnWgttKfpsIbcymow2+ddTHTwlVdCJOfJojHqmEGvXrEtZc8eTrxkvbPrwIl xmq9teZ0Ek2Uk3YfWHjpfp87YW+IaI19oX4AyQS/peO7ETuBJ8X9oYu7j8dxHOsGhdl0 rFSGAVwAbYDeitIOraLH9osCPnFUqm0XU28qEYBeY8mSVMUB19mZnKT7bcrhb+czzSaN pT9p3de8n//nfoTWdLDUu1j69PkiNi2sq6602ijov0aEhoGWGgiSyPm/nDs7kJyZWhGI vYKA== 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:cc; bh=Qy6tDlZMg/W4YNqm7Cn2+L7X5Xotl6MG7hZ+z9QmJUw=; b=eWRplshCxC6+uhjmI29CAJav3SL6E83z8LlsGeIof9Qvv2krukGWpdn/ecnIzGNqRU 7+nf4WAxAU1d17cwjzZcu30u730RaQHzPQ0FdS9H10IwgUH0T2CDG9tj8KrAFDGzyx5p N+4uXfJ0zAl1PtCl8RJpSMODhfLRPhGMJPvLbNpYBg7kLbz2wfitwW6u41kg60iMqQ/R 5MLaVl/+hcKIopF6QPCd3AcFLy611ePyM0CaW5CLbqEL59x0shwEkYkL3LdF/Chtg/Kb Hwy6Ea6mcm5dql33hDh9FYurTNdzQjCCKyBGFlS+j2PglqU90PDmoPKKzfIMgCV84xTe Iazw== X-Gm-Message-State: APjAAAXVHOtCQ5gw12WL7DBSeqvKZkmKP5UA9THmj3yBvYR+HrXeW3Ox 2vJPtNNMC9SiGNA5P1goNIl93MLTEgypK5I8v6E= X-Google-Smtp-Source: APXvYqyfVOj9ZLpKqRl9ucVGI+l0WOW8TVE1iGFtgvKx5NJ2T3R6+CnGU0BG4ZgEfy7w/HkaCjtAe1ZI0ERXRz1a3OQ= X-Received: by 2002:a05:6830:1bd5:: with SMTP id v21mr72607474ota.154.1577626326161; Sun, 29 Dec 2019 05:32:06 -0800 (PST) MIME-Version: 1.0 References: <20191226171207.cepft7cjmmbuow6o@nullprogram.com> In-Reply-To: <20191226171207.cepft7cjmmbuow6o@nullprogram.com> From: Pip Cet Date: Sun, 29 Dec 2019 13:31:30 +0000 Message-ID: Content-Type: text/plain; charset="UTF-8" X-Spam-Score: -0.0 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) On Thu, Dec 26, 2019 at 5:13 PM Christopher Wellons wrote: > The cl-random generator was not written for bignums, so it misbehaves in > Emacs 27. Good catch. I might be wrong, but it looks to me like cl-random and Frandom are currently both limited to small integers (< 31 bits and fixnum range, respectively) and we don't have a random number generator that will do the right thing for (random 100000000000000000000000000000000000000000000) Any idea how easy it would be to fix either of them, or both? From unknown Sun Jun 15 08:54:28 2025 X-Loop: help-debbugs@gnu.org Subject: bug#38753: 27.0.60; cl--random-state uncontrolled growth due to bignums Resent-From: Philipp Stephani Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 29 Dec 2019 13:49:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 38753 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: To: Pip Cet Cc: Christopher Wellons , 38753@debbugs.gnu.org Received: via spool by 38753-submit@debbugs.gnu.org id=B38753.157762732416393 (code B ref 38753); Sun, 29 Dec 2019 13:49:01 +0000 Received: (at 38753) by debbugs.gnu.org; 29 Dec 2019 13:48:44 +0000 Received: from localhost ([127.0.0.1]:59363 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ilYw0-0004GK-5k for submit@debbugs.gnu.org; Sun, 29 Dec 2019 08:48:44 -0500 Received: from mail-ot1-f47.google.com ([209.85.210.47]:40122) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ilYvx-0004G5-Qu for 38753@debbugs.gnu.org; Sun, 29 Dec 2019 08:48:42 -0500 Received: by mail-ot1-f47.google.com with SMTP id w21so35126489otj.7 for <38753@debbugs.gnu.org>; Sun, 29 Dec 2019 05:48:41 -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 :cc; bh=TBVfdIV5YbQ4BOb9EKck8Z7Ao/wqxPr3QHNe1jf0+jY=; b=rxyatYgD9UM774Ue2u+WjvIEaDq5YeY4vyCj/tqTNiJIaBLwysfMVIsqaYJqbzFvN1 cTOn44BBcTJxti+wTEDPS8QKKFb4lWdVN0r65kLHZLY90uDGD4dOnzQHOzQuyl6m4Uy3 L0qw509LAl6g0B+5ppDiXNCm+ks+JJwECEdEMDwTcNFU4wAe+DdK5GLYcWLtnPXoq2hJ yxXLHViJRhiRwR3ENcyk6lP8QM24nq85S2o1IvCoOVyk6dYOFFRBd2Qxl01H4wpprhkW YczvJsBeurGU6VXR0f9J0xorGxR1xmU7vbuppvOEA7y+JG+ZLEYmGDDFneG8UL/moUir hz5A== 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:cc; bh=TBVfdIV5YbQ4BOb9EKck8Z7Ao/wqxPr3QHNe1jf0+jY=; b=eV9QgdeICXHVvhQVd3Y8KNVQHtfybW1TubCMOUsK6FS6ZPRnk3iyfyqqFdYfzUEscU /IYHYR2RDQ45hUrSKmfi5uhp5S+zy4DB+1cwbp8e9/oIDdJ3YdX68jBDf0fwYNVejUEo NDWXbJ7ZS3LgaaKjrtry07F7FuBIZnTJT4yIL24fuqwQ+DB/OFg9J5in4yL/fIYYtBAN wF86+a2pYUfMEMWTx1VDpKXEy/S25HUabnXGazc7CrjHHzxnDheQ4VcOJL963fyUG9ep 3U6N+gWxhmPtAGJI1prr8Uef+gPd8oastinKnMRDTb5Vlr45zcPjyuDkV3Ef3fHYSHYL 6iIQ== X-Gm-Message-State: APjAAAWk+POFqnNNhbsHRfsSCJ1kKU7KJl+HzTdlDlZ8+FTBzYDgqMH4 Uq2vTm1lJkxoOG6VxegGWGba99+fZFN941UN3j8= X-Google-Smtp-Source: APXvYqw+kKNdA6Mz+veCw1P7C1me1MAlz1YwMbGsqOCCq4OkwcCl6KxZ0gl1hM2UrdcfI9tC0i0L3a4RS4HIIMAJFGc= X-Received: by 2002:a05:6830:ce:: with SMTP id x14mr56022291oto.105.1577627316094; Sun, 29 Dec 2019 05:48:36 -0800 (PST) MIME-Version: 1.0 References: <20191226171207.cepft7cjmmbuow6o@nullprogram.com> In-Reply-To: From: Philipp Stephani Date: Sun, 29 Dec 2019 14:48:25 +0100 Message-ID: Content-Type: text/plain; charset="UTF-8" X-Spam-Score: 0.2 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.8 (/) Am So., 29. Dez. 2019 um 14:33 Uhr schrieb Pip Cet : > > On Thu, Dec 26, 2019 at 5:13 PM Christopher Wellons > wrote: > > The cl-random generator was not written for bignums, so it misbehaves in > > Emacs 27. > > Good catch. > > I might be wrong, but it looks to me like cl-random and Frandom are > currently both limited to small integers (< 31 bits and fixnum range, > respectively) and we don't have a random number generator that will do > the right thing for > (random 100000000000000000000000000000000000000000000) > > Any idea how easy it would be to fix either of them, or both? I haven't tried it out, but mpz_urandomm should be what we need. We'd need to find a replacement for mini-gmp though. From unknown Sun Jun 15 08:54:28 2025 X-Loop: help-debbugs@gnu.org Subject: bug#38753: 27.0.60; cl--random-state uncontrolled growth due to bignums References: <20191226171207.cepft7cjmmbuow6o@nullprogram.com> In-Reply-To: <20191226171207.cepft7cjmmbuow6o@nullprogram.com> Resent-From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 29 Dec 2019 14:10:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 38753 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: To: Pip Cet , Christopher Wellons , Philipp Cc: 38753@debbugs.gnu.org Received: via spool by 38753-submit@debbugs.gnu.org id=B38753.157762857818421 (code B ref 38753); Sun, 29 Dec 2019 14:10:01 +0000 Received: (at 38753) by debbugs.gnu.org; 29 Dec 2019 14:09:38 +0000 Received: from localhost ([127.0.0.1]:59383 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ilZGD-0004n3-QS for submit@debbugs.gnu.org; Sun, 29 Dec 2019 09:09:38 -0500 Received: from mail152c50.megamailservers.eu ([91.136.10.162]:56572 helo=mail50c50.megamailservers.eu) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ilZGB-0004mt-4p for 38753@debbugs.gnu.org; Sun, 29 Dec 2019 09:09:36 -0500 X-Authenticated-User: mattiase@bredband.net DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=megamailservers.eu; s=maildub; t=1577628573; bh=1PDl6uerg0CzGH1BJ6utXivgdIEJbq+RuOWET+Jhxes=; h=From:Subject:Date:Cc:To:From; b=mE7HZUprhW0L8iBfL0WpXp1cgLRBBA8gE855FCCUeKlAccic6lX+P9MGROnR/q2Ga aHsV7tazvOekihxrs75o+lrfITSe/mJUISU7EzN6G+jpDHh8GpSGZIY7Ourj/FsiAn KNY2huR6RH3UBklNpp9737DVrYMVB8MKaFLYbLHw= Feedback-ID: mattiase@acm.or Received: from [192.168.0.4] (c188-150-171-71.bredband.comhem.se [188.150.171.71]) (authenticated bits=0) by mail50c50.megamailservers.eu (8.14.9/8.13.1) with ESMTP id xBTE9U0K031941; Sun, 29 Dec 2019 14:09:32 +0000 From: Mattias =?UTF-8?Q?Engdeg=C3=A5rd?= Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\)) Message-Id: Date: Sun, 29 Dec 2019 15:09:30 +0100 X-Mailer: Apple Mail (2.3445.104.11) X-CTCH-RefID: str=0001.0A0B0201.5E08B39D.0011, ss=1, re=0.000, recu=0.000, reip=0.000, cl=1, cld=1, fgs=0 X-CTCH-VOD: Unknown X-CTCH-Spam: Unknown X-CTCH-Score: 0.000 X-CTCH-Rules: X-CTCH-Flags: 0 X-CTCH-ScoreCust: 0.000 X-CSC: 0 X-CHA: v=2.3 cv=N4FX6F1B c=1 sm=1 tr=0 a=SF+I6pRkHZhrawxbOkkvaA==:117 a=SF+I6pRkHZhrawxbOkkvaA==:17 a=kj9zAlcOel0A:10 a=M51BFTxLslgA:10 a=3Fc2rDN5DA6fEtmSEZEA:9 a=CjuIK1q_8ugA:10 X-Spam-Score: 0.3 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -0.7 (/) > I might be wrong, but it looks to me like cl-random and Frandom are = currently both limited to small integers (< 31 bits and fixnum range, = respectively) and we don't have a random number generator that will do = the right thing for > (random 100000000000000000000000000000000000000000000)=20 Thank you for noticing this! It definitely merits a separate bug (or = two). From unknown Sun Jun 15 08:54:28 2025 X-Loop: help-debbugs@gnu.org Subject: bug#38753: 27.0.60; cl--random-state uncontrolled growth due to bignums Resent-From: Christopher Wellons Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 29 Dec 2019 14:28:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 38753 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: To: Pip Cet Cc: 38753@debbugs.gnu.org Received: via spool by 38753-submit@debbugs.gnu.org id=B38753.157762964320081 (code B ref 38753); Sun, 29 Dec 2019 14:28:02 +0000 Received: (at 38753) by debbugs.gnu.org; 29 Dec 2019 14:27:23 +0000 Received: from localhost ([127.0.0.1]:59405 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ilZXP-0005Do-5i for submit@debbugs.gnu.org; Sun, 29 Dec 2019 09:27:23 -0500 Received: from mail.nullprogram.com ([192.241.191.137]:58318) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ilZXM-0005Df-9T for 38753@debbugs.gnu.org; Sun, 29 Dec 2019 09:27:21 -0500 Received: from nullprogram.com (localhost [127.0.0.1]) by mail.nullprogram.com (Postfix) with ESMTPS id 8FF35C534C; Sun, 29 Dec 2019 09:27:19 -0500 (EST) Date: Sun, 29 Dec 2019 09:27:18 -0500 From: Christopher Wellons Message-ID: <20191229142718.q2vvumr6e7pbobdu@nullprogram.com> References: <20191226171207.cepft7cjmmbuow6o@nullprogram.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: User-Agent: NeoMutt/20170113 (1.7.2) X-Spam-Score: 0.0 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) > Any idea how easy it would be to fix either of them, or both? The reason I found that bug is because I was experimenting with addressing exactly that problem: https://github.com/skeeto/lcg128 It's got the right features, including support for arbitrary limits (per your example), but I'm not satisfied with the performance. For arbitrary limits it uses the same rejection algorithm as Python — generate (logb lim) bits and reject if out of range — and cl-random could be updated to use the same technique. The LCG around 6x slower than cl-random in the common case (generating small numbers). Bignums aren't ideal for this since every operation requires an allocation, and the LCG throws away half of the work (the upper half of the multiplication result). The lagged Fibonacci generator really does hit a sweet spot for Emacs Lisp, where, before bignums, even 32-bit integers weren't a reliable option. So it fits within Emacs' worst fixnum limitations and requires few bytecode instructions to generate a number. The random built-in ought to simply be pcg32 across all platforms: http://www.pcg-random.org/download.html Currently it's whatever crummy host-provided PRNG it happens to find at compile time. It's certainly possible to implement pcg32 using Emacs 27 bignums, but it would be even slower than my LCG, especially on 32-bit platforms. In C it's very, very fast. If the pcg32 state, just one 64-bit integer, was an optional parameter, then cl-random could build on it. However, the state would nearly always be a bignum, even on 64-bit platforms, and that would really slow it down. I haven't yet thought of any obviously good options for this. From unknown Sun Jun 15 08:54:28 2025 X-Loop: help-debbugs@gnu.org Subject: bug#38753: 27.0.60; cl--random-state uncontrolled growth due to bignums Resent-From: Pip Cet Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 29 Dec 2019 17:35:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 38753 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: To: Christopher Wellons Cc: 38753@debbugs.gnu.org Received: via spool by 38753-submit@debbugs.gnu.org id=B38753.157764088213856 (code B ref 38753); Sun, 29 Dec 2019 17:35:01 +0000 Received: (at 38753) by debbugs.gnu.org; 29 Dec 2019 17:34:42 +0000 Received: from localhost ([127.0.0.1]:60185 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ilcSg-0003bP-8p for submit@debbugs.gnu.org; Sun, 29 Dec 2019 12:34:42 -0500 Received: from mail-ot1-f41.google.com ([209.85.210.41]:41881) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ilcSe-0003bC-I6 for 38753@debbugs.gnu.org; Sun, 29 Dec 2019 12:34:40 -0500 Received: by mail-ot1-f41.google.com with SMTP id r27so43326307otc.8 for <38753@debbugs.gnu.org>; Sun, 29 Dec 2019 09:34:40 -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 :cc; bh=swGDN/tZD1rVA2P+pd34OPnaEgrKhd94TjWKfq1SRHI=; b=UvTC3Fpt+lJ5X1N8Uk1/FsvnzHg3FRsFn7fiNoF0KpnSVgYSOnlOfesM6TtSs+JU20 c6jswfZArogVokQYxQwxv3kUrngU4A+rUKXy/lfdDPikwQIH3CY71cOuHZqZfBv7H4XP eQY8KjFDRTWOGxYxSzyT1sRyRZqphbe1HbBtOVCW1TdhWcfh37KOE12EDpjf4/u7DATL C8swCaxSgscptt8av1CPJtBijTP6gfNgyRyk9nPlcGBsH/1HSY/tYsh/X0RbxQPYgtG/ QHlCCci8H/CPKC4Le7UJcpZUwZUlwkBqpPZEaqlPrVfo8KXzpjXllCeSje+Fd0vGtZNu RfdA== 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:cc; bh=swGDN/tZD1rVA2P+pd34OPnaEgrKhd94TjWKfq1SRHI=; b=nW7gfi1bPyTICb0M5XmuzmBs53RhopBf/EtHxbbttn26KBIakBEN/MwtWrfWv9yg9A jvAVX7rfLXA2Y8Eu+qLWmqJhJSANboVu17DzC4IhMJC+es156npCQSKL0cObx5TFFxEL f7ZKUh5lGHw3ieyxLyD9+dfqBaK61OfZixU9l4TU9ylSQEFFLUhG//oO9DjlE/qWgayY dFujQ2IO3Vx58xSitmk3ivqLD3UHZmi1+dY3lsyula07/alsMvPG5+/FJqWMgFJ2IOxL ld+R8/PQjiFi1jn6R0i2kDJ1cJv1qknsE/JSIoof5onRGb225qvqsTUJsxdOM/7zMFCP +Tlg== X-Gm-Message-State: APjAAAU84ZArhSuVOrCJ9dsZYRrApWUFQ89vrJFhzz6S5QTQbVyseQ+H ph/1KF7TM61hJixsfamLjrr43HSc1QmM3UHJf6HebA== X-Google-Smtp-Source: APXvYqw+7hAKaRXe+0Tao+KTA7XvUP3rR/a56ZdEW5Xl6c7Xq9immbJPqS01ZmG77ktxvvO61zfGesVBiMErMU8ngXk= X-Received: by 2002:a9d:68cb:: with SMTP id i11mr65415837oto.210.1577640875052; Sun, 29 Dec 2019 09:34:35 -0800 (PST) MIME-Version: 1.0 References: <20191226171207.cepft7cjmmbuow6o@nullprogram.com> <20191229142718.q2vvumr6e7pbobdu@nullprogram.com> In-Reply-To: <20191229142718.q2vvumr6e7pbobdu@nullprogram.com> From: Pip Cet Date: Sun, 29 Dec 2019 17:33:59 +0000 Message-ID: Content-Type: text/plain; charset="UTF-8" X-Spam-Score: -0.0 (/) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) On Sun, Dec 29, 2019 at 2:27 PM Christopher Wellons wrote: > > Any idea how easy it would be to fix either of them, or both? > The reason I found that bug is because I was experimenting with > addressing exactly that problem: > > https://github.com/skeeto/lcg128 > > It's got the right features, including support for arbitrary limits (per > your example), but I'm not satisfied with the performance. That looks excellent. Maybe we should be using a cryptographic RNG by default, though? I really don't know the tradeoffs, though. At first glance, there are two questions I have about lcg128: - should random floats have more than 53 significant bits if they're < 0.5? I think the answer is yes, even though that will make the implementation harder. - should (lcg128-range 2^n) call the generator twice, on average? I think it's an important special case in which we only want to call the generator once. From unknown Sun Jun 15 08:54:28 2025 X-Loop: help-debbugs@gnu.org Subject: bug#38753: 27.0.60; cl--random-state uncontrolled growth due to bignums Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 29 Dec 2019 18:13:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 38753 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: To: Pip Cet Cc: wellons@nullprogram.com, 38753@debbugs.gnu.org Received: via spool by 38753-submit@debbugs.gnu.org id=B38753.157764312624715 (code B ref 38753); Sun, 29 Dec 2019 18:13:02 +0000 Received: (at 38753) by debbugs.gnu.org; 29 Dec 2019 18:12:06 +0000 Received: from localhost ([127.0.0.1]:60207 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ild2s-0006QZ-95 for submit@debbugs.gnu.org; Sun, 29 Dec 2019 13:12:06 -0500 Received: from eggs.gnu.org ([209.51.188.92]:33976) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1ild2q-0006Pg-Cm for 38753@debbugs.gnu.org; Sun, 29 Dec 2019 13:12:04 -0500 Received: from fencepost.gnu.org ([2001:470:142:3::e]:51458) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1ild2l-0007C1-6Y; Sun, 29 Dec 2019 13:11:59 -0500 Received: from [176.228.60.248] (port=2427 helo=home-c4e4a596f7) by fencepost.gnu.org with esmtpsa (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.82) (envelope-from ) id 1ild2k-00005X-E2; Sun, 29 Dec 2019 13:11:59 -0500 Date: Sun, 29 Dec 2019 20:12:02 +0200 Message-Id: <83y2uvm26l.fsf@gnu.org> From: Eli Zaretskii In-reply-to: (message from Pip Cet on Sun, 29 Dec 2019 17:33:59 +0000) References: <20191226171207.cepft7cjmmbuow6o@nullprogram.com> <20191229142718.q2vvumr6e7pbobdu@nullprogram.com> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Spam-Score: -2.3 (--) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) > From: Pip Cet > Date: Sun, 29 Dec 2019 17:33:59 +0000 > Cc: 38753@debbugs.gnu.org > > That looks excellent. Maybe we should be using a cryptographic RNG by > default, though? Are you aware that we already init the random seed using system entropy and/or cryptographic RNG? See init_random.