From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Paul Eggert Newsgroups: gmane.emacs.devel Subject: Re: Merging bignum to master Date: Sun, 19 Aug 2018 01:26:48 -0700 Organization: UCLA Computer Science Department Message-ID: <2a4ff77b-9d71-1c82-e5cb-ce8276cc2947@cs.ucla.edu> References: <877ekwu1mn.fsf@tromey.com> <87o9e8oaot.fsf@tcd.ie> <87a7prk0h6.fsf@tromey.com> <86r2j13ihs.fsf@gmail.com> <86sh3fgpub.fsf@gmail.com> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="------------107AA3A649905E6FB2CAEB94" X-Trace: blaine.gmane.org 1534667134 29570 195.159.176.226 (19 Aug 2018 08:25:34 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 19 Aug 2018 08:25:34 +0000 (UTC) User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 To: Andy Moreton , emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Sun Aug 19 10:25:30 2018 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1frJ1d-0007Xo-G2 for ged-emacs-devel@m.gmane.org; Sun, 19 Aug 2018 10:25:29 +0200 Original-Received: from localhost ([::1]:42000 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1frJ3j-0002kz-Lr for ged-emacs-devel@m.gmane.org; Sun, 19 Aug 2018 04:27:39 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:50609) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1frJ33-0002il-70 for emacs-devel@gnu.org; Sun, 19 Aug 2018 04:26:58 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1frJ30-00087M-3S for emacs-devel@gnu.org; Sun, 19 Aug 2018 04:26:57 -0400 Original-Received: from zimbra.cs.ucla.edu ([131.179.128.68]:58620) by eggs.gnu.org with esmtps (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:32) (Exim 4.71) (envelope-from ) id 1frJ2z-00086I-Qw for emacs-devel@gnu.org; Sun, 19 Aug 2018 04:26:54 -0400 Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id 443B916081D; Sun, 19 Aug 2018 01:26:51 -0700 (PDT) Original-Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10032) with ESMTP id uqRbzMKm3IzT; Sun, 19 Aug 2018 01:26:49 -0700 (PDT) Original-Received: from localhost (localhost [127.0.0.1]) by zimbra.cs.ucla.edu (Postfix) with ESMTP id C6761160825; Sun, 19 Aug 2018 01:26:49 -0700 (PDT) X-Virus-Scanned: amavisd-new at zimbra.cs.ucla.edu Original-Received: from zimbra.cs.ucla.edu ([127.0.0.1]) by localhost (zimbra.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10026) with ESMTP id 0ymYbewDy6UW; Sun, 19 Aug 2018 01:26:49 -0700 (PDT) Original-Received: from [192.168.1.9] (unknown [47.154.30.119]) by zimbra.cs.ucla.edu (Postfix) with ESMTPSA id 7C6C616081D; Sun, 19 Aug 2018 01:26:49 -0700 (PDT) In-Reply-To: <86sh3fgpub.fsf@gmail.com> Content-Language: en-US X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 131.179.128.68 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 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.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:228674 Archived-At: This is a multi-part message in MIME format. --------------107AA3A649905E6FB2CAEB94 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Andy Moreton wrote: > Tom and Basil, please try the following patch for expt. > I have given it some light sanity testing on Windows 64bit. Thanks, I wrote up some test cases for that and found by inspection a few problems having to do with XFIXNUM returning a value greater than ULONG_MAX, that sort of thing, and installed the attached. --------------107AA3A649905E6FB2CAEB94 Content-Type: text/x-patch; name="0001-Add-bignum-support-to-expt.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0001-Add-bignum-support-to-expt.patch" >From 47b7a5bd492e92dda928843e28a707b9682cb32f Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sun, 19 Aug 2018 01:22:08 -0700 Subject: [PATCH] Add bignum support to expt Problem and initial solution reported by Andy Moreton in: https://lists.gnu.org/r/emacs-devel/2018-08/msg00503.html * doc/lispref/numbers.texi (Math Functions): expt integer overflow no longer causes truncation; it now signals an error since bignum overflow is a big deal. * src/floatfns.c (Fexpt): Support bignum arguments. * test/src/floatfns-tests.el (bignum-expt): New test. --- doc/lispref/numbers.texi | 2 +- src/floatfns.c | 47 ++++++++++++++++++++++---------------- test/src/floatfns-tests.el | 9 ++++++++ 3 files changed, 37 insertions(+), 21 deletions(-) diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi index 74a313e2e1..209e9f139a 100644 --- a/doc/lispref/numbers.texi +++ b/doc/lispref/numbers.texi @@ -1185,7 +1185,7 @@ Math Functions @defun expt x y This function returns @var{x} raised to power @var{y}. If both arguments are integers and @var{y} is nonnegative, the result is an -integer; in this case, overflow causes truncation, so watch out. +integer; in this case, overflow signals an error, so watch out. If @var{x} is a finite negative number and @var{y} is a finite non-integer, @code{expt} returns a NaN. @end defun diff --git a/src/floatfns.c b/src/floatfns.c index 713d42694f..54d068c29e 100644 --- a/src/floatfns.c +++ b/src/floatfns.c @@ -204,29 +204,36 @@ DEFUN ("expt", Fexpt, Sexpt, 2, 2, 0, doc: /* Return the exponential ARG1 ** ARG2. */) (Lisp_Object arg1, Lisp_Object arg2) { - CHECK_FIXNUM_OR_FLOAT (arg1); - CHECK_FIXNUM_OR_FLOAT (arg2); - if (FIXNUMP (arg1) /* common lisp spec */ - && FIXNUMP (arg2) /* don't promote, if both are ints, and */ - && XFIXNUM (arg2) >= 0) /* we are sure the result is not fractional */ - { /* this can be improved by pre-calculating */ - EMACS_INT y; /* some binary powers of x then accumulating */ - EMACS_UINT acc, x; /* Unsigned so that overflow is well defined. */ - Lisp_Object val; - - x = XFIXNUM (arg1); - y = XFIXNUM (arg2); - acc = (y & 1 ? x : 1); - - while ((y >>= 1) != 0) + CHECK_NUMBER (arg1); + CHECK_NUMBER (arg2); + + /* Common Lisp spec: don't promote if both are integers, and if the + result is not fractional. */ + if (INTEGERP (arg1) && NATNUMP (arg2)) + { + unsigned long exp; + if (RANGED_FIXNUMP (0, arg2, ULONG_MAX)) + exp = XFIXNUM (arg2); + else if (MOST_POSITIVE_FIXNUM < ULONG_MAX && BIGNUMP (arg2) + && mpz_fits_ulong_p (XBIGNUM (arg2)->value)) + exp = mpz_get_ui (XBIGNUM (arg2)->value); + else + xsignal3 (Qrange_error, build_string ("expt"), arg1, arg2); + + mpz_t val; + mpz_init (val); + if (FIXNUMP (arg1)) { - x *= x; - if (y & 1) - acc *= x; + mpz_set_intmax (val, XFIXNUM (arg1)); + mpz_pow_ui (val, val, exp); } - XSETINT (val, acc); - return val; + else + mpz_pow_ui (val, XBIGNUM (arg1)->value, exp); + Lisp_Object res = make_number (val); + mpz_clear (val); + return res; } + return make_float (pow (XFLOATINT (arg1), XFLOATINT (arg2))); } diff --git a/test/src/floatfns-tests.el b/test/src/floatfns-tests.el index 43a2e27829..e4caaa1e49 100644 --- a/test/src/floatfns-tests.el +++ b/test/src/floatfns-tests.el @@ -42,6 +42,15 @@ (should (= most-positive-fixnum (- (abs most-negative-fixnum) 1)))) +(ert-deftest bignum-expt () + (dolist (n (list most-positive-fixnum (1+ most-positive-fixnum) + most-negative-fixnum (1- most-negative-fixnum) + -2 -1 0 1 2)) + (should (= (expt n 0) 1)) + (should (= (expt n 1) n)) + (should (= (expt n 2) (* n n))) + (should (= (expt n 3) (* n n n))))) + (ert-deftest bignum-logb () (should (= (+ (logb most-positive-fixnum) 1) (logb (+ most-positive-fixnum 1))))) -- 2.17.1 --------------107AA3A649905E6FB2CAEB94--