Document bignums

* doc/lispref/numbers.texi (Numbers, Integer Basics)
(Predicates on Numbers, Comparison of Numbers)
(Arithmetic Operations, Bitwise Operations): Update for bignums.
* doc/lispref/objects.texi (Integer Type, Type Predicates):
Update for bignums.
* etc/NEWS: Update for bigums.

2 files changed, 59 insertions, 100 deletions

diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi
index 2fed2b642fd..a95c31f4682 100644
--- a/doc/lispref/numbers.texi
+++ b/doc/lispref/numbers.texi
@@ -14,9 +14,9 @@
 fractional parts, such as @minus{}4.5, 0.0, and 2.71828.  They can
 also be expressed in exponential notation: @samp{1.5e2} is the same as
 @samp{150.0}; here, @samp{e2} stands for ten to the second power, and
-that is multiplied by 1.5.  Integer computations are exact, though
-they may overflow.  Floating-point computations often involve rounding
-errors, as the numbers have a fixed amount of precision.
+that is multiplied by 1.5.  Integer computations are exact.
+Floating-point computations often involve rounding errors, as the
+numbers have a fixed amount of precision.
 
 @menu
 * Integer Basics::            Representation and range of integers.
@@ -34,7 +34,15 @@ errors, as the numbers have a fixed amount of precision.
 @node Integer Basics
 @section Integer Basics
 
-  The range of values for an integer depends on the machine.  The
+  Integers in Emacs Lisp can have arbitrary precision.
+
+  Under the hood, though, there are two kinds of integers: smaller
+ones, called @dfn{fixnums}, and larger ones, called @dfn{bignums}
+Some functions in Emacs only accept fixnums.  Also, while fixnums can
+always be compared for equality with @code{eq}, bignums require the
+use of @code{eql}.
+
+  The range of values for a fixnum depends on the machine.  The
 minimum range is @minus{}536,870,912 to 536,870,911 (30 bits; i.e.,
 @ifnottex
 @minus{}2**29
@@ -49,9 +57,7 @@ to
 @tex
 @math{2^{29}-1}),
 @end tex
-but many machines provide a wider range.  Many examples in this
-chapter assume the minimum integer width of 30 bits.
-@cindex overflow
+but many machines provide a wider range.
 
   The Lisp reader reads an integer as a nonempty sequence
 of decimal digits with optional initial sign and optional
@@ -91,14 +97,8 @@ For example:
 #24r1k @result{} 44
 @end example
 
-  If an integer is outside the Emacs range, the Lisp reader ordinarily
-signals an overflow.  However, if a too-large plain integer ends in a
-period, the Lisp reader treats it as a floating-point number instead.
-This lets an Emacs Lisp program specify a large integer that is
-quietly approximated by a floating-point number on machines with
-limited word width.  For example, @samp{536870912.} is a
-floating-point number if Emacs integers are only 30 bits wide and is
-an integer otherwise.
+  An integer is read as a fixnum if it is in the correct range.
+Otherwise, it will be read as a bignum.
 
   To understand how various functions work on integers, especially the
 bitwise operators (@pxref{Bitwise Operations}), it is often helpful to
@@ -141,16 +141,6 @@ In binary, the decimal integer 4 is 100.  Consequently,
 0111...111111 (30 bits total)
 @end example
 
-  Since the arithmetic functions do not check whether integers go
-outside their range, when you add 1 to 536,870,911, the value is the
-negative integer @minus{}536,870,912:
-
-@example
-(+ 1 536870911)
-     @result{} -536870912
-     @result{} 1000...000000 (30 bits total)
-@end example
-
   Many of the functions described in this chapter accept markers for
 arguments in place of numbers.  (@xref{Markers}.)  Since the actual
 arguments to such functions may be either numbers or markers, we often
@@ -160,8 +150,8 @@ value is a marker, its position value is used and its buffer is ignored.
 @cindex largest Lisp integer
 @cindex maximum Lisp integer
 @defvar most-positive-fixnum
-The value of this variable is the largest integer that Emacs Lisp can
-handle.  Typical values are
+The value of this variable is the largest ``small'' integer that Emacs
+Lisp can handle.  Typical values are
 @ifnottex
 2**29 @minus{} 1
 @end ifnottex
@@ -181,8 +171,8 @@ on 64-bit platforms.
 @cindex smallest Lisp integer
 @cindex minimum Lisp integer
 @defvar most-negative-fixnum
-The value of this variable is the smallest integer that Emacs Lisp can
-handle.  It is negative.  Typical values are
+The value of this variable is the smallest small integer that Emacs
+Lisp can handle.  It is negative.  Typical values are
 @ifnottex
 @minus{}2**29
 @end ifnottex
@@ -315,6 +305,20 @@ use otherwise), but the @code{zerop} predicate requires a number as
 its argument.  See also @code{integer-or-marker-p} and
 @code{number-or-marker-p}, in @ref{Predicates on Markers}.
 
+@defun bignump object
+This predicate tests whether its argument is a large integer, and
+returns @code{t} if so, @code{nil} otherwise.  Large integers cannot
+be compared with @code{eq}, only with @code{=} or @code{eql}.  Also,
+large integers are only available if Emacs was compiled with the GMP
+library.
+@end defun
+
+@defun fixnump object
+This predicate tests whether its argument is a small integer, and
+returns @code{t} if so, @code{nil} otherwise.  Small integers can be
+compared with @code{eq}.
+@end defun
+
 @defun floatp object
 This predicate tests whether its argument is floating point
 and returns @code{t} if so, @code{nil} otherwise.
@@ -355,13 +359,13 @@ if so, @code{nil} otherwise.  The argument must be a number.
 
   To test numbers for numerical equality, you should normally use
 @code{=}, not @code{eq}.  There can be many distinct floating-point
-objects with the same numeric value.  If you use @code{eq} to
-compare them, then you test whether two values are the same
-@emph{object}.  By contrast, @code{=} compares only the numeric values
-of the objects.
+and large integer objects with the same numeric value.  If you use
+@code{eq} to compare them, then you test whether two values are the
+same @emph{object}.  By contrast, @code{=} compares only the numeric
+values of the objects.
 
-  In Emacs Lisp, each integer is a unique Lisp object.
-Therefore, @code{eq} is equivalent to @code{=} where integers are
+  In Emacs Lisp, each small integer is a unique Lisp object.
+Therefore, @code{eq} is equivalent to @code{=} where small integers are
 concerned.  It is sometimes convenient to use @code{eq} for comparing
 an unknown value with an integer, because @code{eq} does not report an
 error if the unknown value is not a number---it accepts arguments of
@@ -389,15 +393,6 @@ Here's a function to do this:
          fuzz-factor)))
 @end example
 
-@cindex CL note---integers vrs @code{eq}
-@quotation
-@b{Common Lisp note:} Comparing numbers in Common Lisp always requires
-@code{=} because Common Lisp implements multi-word integers, and two
-distinct integer objects can have the same numeric value.  Emacs Lisp
-can have just one integer object for any given value because it has a
-limited range of integers.
-@end quotation
-
 @defun = number-or-marker &rest number-or-markers
 This function tests whether all its arguments are numerically equal,
 and returns @code{t} if so, @code{nil} otherwise.
@@ -407,7 +402,8 @@ and returns @code{t} if so, @code{nil} otherwise.
 This function acts like @code{eq} except when both arguments are
 numbers.  It compares numbers by type and numeric value, so that
 @code{(eql 1.0 1)} returns @code{nil}, but @code{(eql 1.0 1.0)} and
-@code{(eql 1 1)} both return @code{t}.
+@code{(eql 1 1)} both return @code{t}.  This can be used to compare
+large integers as well as small ones.
 @end defun
 
 @defun /= number-or-marker1 number-or-marker2
@@ -567,10 +563,6 @@ Except for @code{%}, each of these functions accepts both integer and
 floating-point arguments, and returns a floating-point number if any
 argument is floating point.
 
-  Emacs Lisp arithmetic functions do not check for integer overflow.
-Thus @code{(1+ 536870911)} may evaluate to
-@minus{}536870912, depending on your hardware.
-
 @defun 1+ number-or-marker
 This function returns @var{number-or-marker} plus 1.
 For example,
@@ -897,36 +889,6 @@ On the other hand, shifting one place to the right looks like this:
 As the example illustrates, shifting one place to the right divides the
 value of a positive integer by two, rounding downward.
 
-The function @code{lsh}, like all Emacs Lisp arithmetic functions, does
-not check for overflow, so shifting left can discard significant bits
-and change the sign of the number.  For example, left shifting
-536,870,911 produces @minus{}2 in the 30-bit implementation:
-
-@example
-(lsh 536870911 1)          ; @r{left shift}
-     @result{} -2
-@end example
-
-In binary, the argument looks like this:
-
-@example
-@group
-;; @r{Decimal 536,870,911}
-0111...111111 (30 bits total)
-@end group
-@end example
-
-@noindent
-which becomes the following when left shifted:
-
-@example
-@group
-;; @r{Decimal @minus{}2}
-1111...111110 (30 bits total)
-@end group
-@end example
-@end defun
-
 @defun ash integer1 count
 @cindex arithmetic shift
 @code{ash} (@dfn{arithmetic shift}) shifts the bits in @var{integer1}
@@ -951,19 +913,6 @@ looks like this:
 @end group
 @end example
 
-In contrast, shifting the pattern of bits one place to the right with
-@code{lsh} looks like this:
-
-@example
-@group
-(lsh -6 -1) @result{} 536870909
-;; @r{Decimal @minus{}6 becomes decimal 536,870,909.}
-1111...111010 (30 bits total)
-     @result{}
-0111...111101 (30 bits total)
-@end group
-@end example
-
 Here are other examples:
 
 @c !!! Check if lined up in smallbook format!  XDVI shows problem
diff --git a/doc/lispref/objects.texi b/doc/lispref/objects.texi
index b94de80b658..8c92de123c2 100644
--- a/doc/lispref/objects.texi
+++ b/doc/lispref/objects.texi
@@ -166,7 +166,10 @@ latter are unique to Emacs Lisp.
 @node Integer Type
 @subsection Integer Type
 
-  The range of values for an integer depends on the machine.  The
+  Under the hood, there are two kinds of integers---small integers,
+called @dfn{fixnums}, and large integers, called @dfn{bignums}.
+
+  The range of values for a fixnum depends on the machine.  The
 minimum range is @minus{}536,870,912 to 536,870,911 (30 bits; i.e.,
 @ifnottex
 @minus{}2**29
@@ -182,8 +185,14 @@ to
 @math{2^{29}-1})
 @end tex
 but many machines provide a wider range.
-Emacs Lisp arithmetic functions do not check for integer overflow.  Thus
-@code{(1+ 536870911)} is @minus{}536,870,912 if Emacs integers are 30 bits.
+
+  Bignums can have arbitrary precision.  Operations that overflow a
+fixnum will return a bignum instead.
+
+  Fixnums can be compared with @code{eq}, but bignums require
+@code{eql} or @code{=}.  The @code{fixnump} predicate can be used to
+detect such small integers, and @code{bignump} can be used to detect
+large integers.
 
   The read syntax for integers is a sequence of (base ten) digits with an
 optional sign at the beginning and an optional period at the end.  The
@@ -200,11 +209,6 @@ leading @samp{+} or a final @samp{.}.
 @end example
 
 @noindent
-As a special exception, if a sequence of digits specifies an integer
-too large or too small to be a valid integer object, the Lisp reader
-reads it as a floating-point number (@pxref{Floating-Point Type}).
-For instance, if Emacs integers are 30 bits, @code{536870912} is read
-as the floating-point number @code{536870912.0}.
 
   @xref{Numbers}, for more information.
 
@@ -1895,6 +1899,9 @@ with references to further information.
 @item arrayp
 @xref{Array Functions, arrayp}.
 
+@item bignump
+@xref{Predicates on Numbers, floatp}.
+
 @item bool-vector-p
 @xref{Bool-Vectors, bool-vector-p}.
 
@@ -1928,6 +1935,9 @@ with references to further information.
 @item custom-variable-p
 @xref{Variable Definitions, custom-variable-p}.
 
+@item fixnump
+@xref{Predicates on Numbers, floatp}.
+
 @item floatp
 @xref{Predicates on Numbers, floatp}.