From: Paul Eggert <eggert@cs.ucla.edu>
To: Andy Moreton <andrewjmoreton@gmail.com>, emacs-devel@gnu.org
Subject: Re: Merging bignum to master
Date: Sun, 19 Aug 2018 01:26:48 -0700 [thread overview]
Message-ID: <2a4ff77b-9d71-1c82-e5cb-ce8276cc2947@cs.ucla.edu> (raw)
In-Reply-To: <86sh3fgpub.fsf@gmail.com>
[-- Attachment #1: Type: text/plain, Size: 344 bytes --]
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.
[-- Attachment #2: 0001-Add-bignum-support-to-expt.patch --]
[-- Type: text/x-patch, Size: 4035 bytes --]
From 47b7a5bd492e92dda928843e28a707b9682cb32f Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
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
next prev parent reply other threads:[~2018-08-19 8:26 UTC|newest]
Thread overview: 58+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-08-11 19:47 Merging bignum to master Tom Tromey
2018-08-11 21:28 ` Basil L. Contovounesios
2018-08-12 16:34 ` Tom Tromey
2018-08-13 12:21 ` Basil L. Contovounesios
2018-08-14 0:21 ` Andy Moreton
2018-08-15 23:41 ` Andy Moreton
2018-08-16 15:38 ` Basil L. Contovounesios
2018-08-19 8:26 ` Paul Eggert [this message]
2018-08-17 14:58 ` Eli Zaretskii
2018-08-12 6:29 ` Ulrich Mueller
2018-08-12 8:09 ` Paul Eggert
2018-08-12 17:21 ` Ulrich Mueller
2018-08-12 18:20 ` Eli Zaretskii
2018-08-12 19:30 ` Ulrich Mueller
2018-08-13 0:15 ` Paul Eggert
2018-08-12 18:05 ` Eli Zaretskii
2018-08-12 23:53 ` Paul Eggert
2018-08-13 0:20 ` Tom Tromey
2018-08-13 7:51 ` Andreas Schwab
2018-08-13 8:06 ` Ulrich Mueller
2018-08-13 9:14 ` Paul Eggert
2018-08-14 23:09 ` Paul Eggert
2018-08-16 2:46 ` Richard Stallman
2018-08-13 23:31 ` Richard Stallman
2018-08-14 1:41 ` Paul Eggert
2018-08-16 2:41 ` Richard Stallman
2018-08-16 19:31 ` Paul Eggert
2018-08-16 22:02 ` Stefan Monnier
2018-08-12 7:37 ` John Wiegley
2018-08-12 18:21 ` Eli Zaretskii
2018-08-12 11:48 ` Pip Cet
2018-08-12 16:02 ` Tom Tromey
2018-08-13 22:58 ` Paul Eggert
2018-08-14 1:12 ` Noam Postavsky
2018-08-14 13:04 ` Pip Cet
2018-08-14 18:01 ` Paul Eggert
2018-08-15 15:20 ` Pip Cet
2018-08-15 16:17 ` Paul Eggert
2018-08-15 23:57 ` Andy Moreton
2018-08-16 22:00 ` Stefan Monnier
2018-08-20 16:28 ` Some vars now limited to fixnum size. (Was: Merging bignum to master) Karl Fogel
2018-08-20 16:54 ` Paul Eggert
2018-08-20 17:27 ` Eli Zaretskii
2018-08-20 17:27 ` Paul Eggert
2018-08-20 18:00 ` Eli Zaretskii
2018-08-20 19:55 ` Pip Cet
2018-08-20 23:15 ` Paul Eggert
2018-08-21 15:01 ` Some vars now limited to fixnum size Tom Tromey
2018-08-21 16:36 ` Andy Moreton
2018-08-21 18:46 ` Paul Eggert
2018-08-22 15:39 ` Tom Tromey
2018-08-21 3:38 ` Some vars now limited to fixnum size. (Was: Merging bignum to master) Richard Stallman
2018-08-21 4:09 ` Paul Eggert
2018-08-22 4:03 ` Richard Stallman
2018-08-22 4:53 ` Paul Eggert
2018-08-20 17:25 ` Eli Zaretskii
2018-08-14 0:51 ` Merging bignum to master Andy Moreton
2018-08-15 15:46 ` Andy Moreton
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=2a4ff77b-9d71-1c82-e5cb-ce8276cc2947@cs.ucla.edu \
--to=eggert@cs.ucla.edu \
--cc=andrewjmoreton@gmail.com \
--cc=emacs-devel@gnu.org \
/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.