.c	Saturday  Dec 10,1983  22:45  NM+6D.7H.41M.28S.  -*- Bolio -*-

.chapter "Numbers"
.setq number-chapter-number chapter-number
.setq number-section-page section-page

.section "Types, Contagion, Coercion, and Confusion"

.subsection "The Types"

lan{Nil} provides several different representations for numbers.
It provides integers, of essentially unlimited precision,
and floating-point.  There is also the 3ratio* data type, for
representing non-integer rational numbers.  The 3complex* data
type has been added, but may not yet be trustworthy for anything other
than simple arithmetic operations, and has not yet been specialized to
a point where any significant "crunch" might be performed on it.

lan{Nil} integers are currently of two kinds.  There are
term_i{fixnum}s and term_i{bignum}s.  term{Fixnum}s have 30 bits
of precision, including the sign, and are represented without consing
(i.e., no memory consumption).  Integers which require more than 30
bits to represent are implemented as term{bignum}s.
term{Bignum}s are an extended data-type, and can grow to any size,
limited only by whatever system parameter happens to be limiting the
growth of your lan{nil}, and your patience.

There are four primitive floating-point formats supported in
lan{nil}, as described in (number-types-section-page).  These are
.table 3 250 250 0 0 0
.item short-float
This is implemented as a single-float (lan{vax} 7f_float*
format) with some of the fraction bits truncated, so that it can fit
into a lan{nil} pointer without any memory consumption.  All
operations on this type essentially convert it to a single-float to
perform the operation, and then pack it back (truncating some of the
fraction bits) when it is returned.  5 of the fraction bits get
truncated, leaving 19, or about 5 decimal digits of precision.
Because the exponent is the same as for 3single-float*, it has
close to the same range, however.
.item single-float
This corresponds to the lan{vax} 7f_float* format;  this
provides 24 bits of precision (about 7 decimal digits), and a range of
about 2.9e-39 to 1.7e+38.
.item double-float
This utilizes the lan{vax} 7d_float* format, which has 56 bits
of precision (about 16 decimal digits).  The exponent format is
identical to that of 3single-float*, so the range is essentially
the same.
.item long-float
This utilizes the lan{vax} 7h_float* format.  This has a
whopping 113 bits of precision (33 decimal digits), and binary
exponent range from -16383 to +16383.  This is a range of about
8.4e-4933 to 5.9e+4931.  Because the machine instructions which operate on
this format of float are not supported by all lan{vax} hardware,
lan{nil} makes use of a lan{vms}-supplied condition handler to
cause emulation of the missing instructions.  As a compromise, it also
tries to avoid such instructions when it can (for instance, just for
data movement).
.end_table

.subsection "Contagion and Coercion"

Most of the lan{nil} arithmetic functions are 2generic*.  That
is, they accept numbers of any type (subject to the semantics of the
function, of course), and automatically "coerce" as necessary when
there are mixed types.  Coercion is mainly a function of the
floating-point types.  For instance, division of integers might yield
a ratio:
.lisp
(/ 2 3)  =>  2/3
.end_lisp
However, rational numbers are always "normalized", and automatically
"convert" back to integers:
.lisp
(+ 1/3 2/3)  =>  1
.end_lisp
When a floating-point number meets an integer or a floating-point
number of a "shorter" type, the latter is converted automatically to
the format of the former before the operation proceeds:
.lisp
(* 2 2.0s0)  =>  4.0s0
(* 2 2.0d0 2.0s0)  =>  8.0d0
.end_lisp
Such contagious conversion is never performed in the other direction;
floating point numbers are never converted to integers just because
the result might be integral, for example, or to a shorter format of
float.

Complex numbers in lan{nil} are restricted to having components
which are either both rational, or both floats of the same format.  A
complex number with rational components will automatically be
converted back to a rational (non-complex) number if the result of a
computation gives a zero imaginary part.  This never occurs if the
components are floats:
.lisp
(* #c(0 1) #c(0 1))  =>  -1
(* #c(0.0 1.0) #c(0.0 1.0))  =>  #c(-1.0 0.0)
.end_lisp

.subsection "Confusion"

As was described in (number-types-section-page), the format of a
floating-point number may be selected by use of a particular character
as the exponent specifier.  Thus, 32.0s0* is 3short-float*,
32.0f0* is 3single-float*, 32.0d0* is 3double-float*,
and 32.0l0* is 3long-float*.  lan{Common lisp} specifies
that the default format is 3single-float*.  This is the format
which is used when a floating-point number is read in, and either no
exponent character is used, or one of 3e* is used (e.g.,
32.59e10*).  This is also the format specified as being returned
by exponential, transcendental, or irrational functions when given
rational inputs.  lan{Nil} has historically had a default (in fact,
it used to be the 2only*) format of 3double-float*.  Because
3single-float* (and short and long) are all quite new to
lan{nil}, the default format is still 3double-float*.  That is,
currently
.lisp
(typep 2.59 'double-float)  =>  t
(typep (log 3/4) 'double-float)  =>  t
.end_lisp
However, 2this will be changed*.  The lan{nil} reader/printer
combination has been twiddled somewhat so that, while the default
format chosen by 3read* is 3double-float*, the printer will
always print the exponent character which will force the format.

.defvar *read-default-float-format*
This variable (which is defined by lan{common lisp}) names the type
of float which 3read* should create when it encounters one which
does not specify the format.  It should have as its value
3short-float*, 3single-float*, 3double-float*, or
3long-float*.  The lan{common lisp} default for this is
3single-float*.

As a special interim hack, lan{nil} allows this variable to have
3nil* as its value.  This is taken to mean (to the reader) to
produce 3double-float* by default, but (to the printer) to not use
an "unspecified" format on output.  That is, with
3*read-default-float-format** being 3nil*, the printer will
never produce "1.0", but rather "1.0d0".
.end_defvar

It is strongly recommended that explicit use of coercion (using the
3float* function, (float-fun)) be made wherever the type of the
result might matter, when using functions which must convert into
floating-point before proceeding.  This includes things like 3log*
3sin*, and 3sqrt*.  Note also that certain operations on
complex numbers with rational components, such as 3abs*,
implicitly use these other functions;  for instance, 
.lisp
(abs #c(3 4))  =>  5.0d0
.end_lisp

.section "Predicates on Numbers"

Note also the type predicates fun{numberp}, fun{bignump},
fun{integerp}, fun{fixnump}, fun{floatp}, fun{ratiop},
fun{rationalp}, and fun{complexp}.

.defun zerop number
Returns 3t* if 2number* is integer, floating-point, or complex
zero, 3nil* otherwise.
.end_defun

.defun plusp non-complex-number
.defun1 minusp non-complex-number
Return 3t* if 2non-complex-number* is of the appropriate sign,
3nil* otherwise.
.end_defun

.defun oddp integer
.defun1 evenp integer
Return 3t* if 2integer* is odd (even), 3nil* otherwise.

In lan{nil} (but 2not* lan{common lisp}), 3oddp* and
3evenp* have been extended to gaussian integers.  3evenp* is
defined as divisibility by 31+2i**, and 3oddp* as being
not 3evenp*.  This definition has the property that exactly half
of the gaussian integers are odd and half are even.  While there is a
remote possibility that this definition will be changed, I consider it
very unlikely.
.end_defun


.section "Comparisons on Numbers"

.defun = number &rest more-numbers
.defun1 /= number &rest more-numbers
.defun1 < number &rest more-numbers
.defun1 > number &rest more-numbers
.defun1 <= number &rest more-numbers
.defun1 >= number &rest more-numbers
These functions each take one or more arguments.
If the sequence of arguments satisfies a certain condition:
.lisp
=       1all the same*
/=      1all different*
<       1monotonically increasing*
>       1monotonically decreasing*
<=      1monotonically nondecreasing*
>=      1monotonically nonincreasing*
.end_lisp
then the predicate is true, and otherwise is false.

Complex numbers are only acceptable as arguments to 3=* and
3/=*;  the others require their arguments to be non-complex.

These functions also have fixnum-only and double-float-only versions.
.end_defun

.defun greaterp num1 num2 &rest more-numbers
.defun1 lessp num1 num2 &rest more-numbers
These are implemented as synonyms of 3<* and 3>*, and exist
for lan{maclisp} compatibility.
.end_defun

.defun max number &rest more-numbers
.defun1 min number &rest more-numbers
Generic max/min.  Works on any non-complex numbers.  Note also the
existence of fun{max&} and fun{min&} ((max&-fun)), which only
work on fixnums, and fun{max$} and fun{min$} ((max$-fun)), which
only work on double-floats.
.end_defun


.section "Arithmetic Operations"

.defun + &rest numbers
.defun1 plus &rest numbers
Returns the sum of all of the numbers, performing type coercion as
appropriate.  If there are no numbers, 30* is returned.  The name
3plus* is retained for lan{maclisp} compatibility.  Note also
the fixnum-only 3+&*, and double-float-only 3+$*.
.end_defun

.defun 1+ 
.defun1 add1 number
.lisp
(plus 2number* 1)
.end_lisp
The name 3add1* is retained primarily for lan{maclisp}
compatibility.
.end_defun

.defun - number &rest numbers
With one argument, 3-* returns the negative of that argument.
With more than one argument, it subtracts all of the others from the
first.  Type coercion is performed as necessary.  Note also the
fixnum-only 3-&*, and double-float-only 3-$* functions.
.end_defun

.defun difference number &rest numbers
When given more than one argument, fun{difference} subtracts from
the first argument all the others, and returns the result.  When given
one argument, fun{difference} returns it.  This is noteworthy
because it is compatible with the lan{maclisp}
fun{difference} function, and it is iincompatible* with 3-*
above.
.end_defun

.defun 1- number
.defun1 sub1 number
.lisp
(- 2number* 1)
.end_lisp
The name 3sub1* is retained for lan{maclisp} compatibility.
.end_defun

.defun minus number
This is the same as 3(- 2number*)*;  the name is retained for
lan{maclisp} compatibility.
.end_defun

.defun * &rest numbers
.defun1 times &rest numbers
Returns the product of all of the numbers, coercing as appropriate.
The identity for this operation is 31*.  The name 3times* is
retained for lan{maclisp} compatibility.
.end_defun

.defun / number &rest numbers
This is the generic rationalizing division function.  With one
argument, 3/* reciprocates the argument;  with more than one, it
divides the first by all the others, and returns the result.  3/*
will return a ratio if the mathematical quotient of two integers is
not an exact integer;  truncating integer division is performed by the
lan{maclisp} compatible 3quotient* function, and various sorts
of truncation and rounding (not limited to floating-point inputs) are
provided by the 3floor*, 3ceiling*, 3truncate*, and
3round* functions ((integer-conversion-section-page)).
.end_defun

.defun quotient number &rest more-numbers
This is the lan{maclisp}-compatible 3quotient* function.
When given more than one argument, fun{quotient} divides the first
by all the others, and returns the result.  With one argument,
returns that argument.

If 3quotient* is given integer arguments, it performs truncating
division (see 3truncate*, (truncate-fun)).  However, if any of
the arguments are ratios, it will instead do rational division, like
3/*.
.end_defun

.defun conjugate number
Returns the complex conjugate of 2number*, which is 2number*
itself if 2number* is not complex.
.end_defun

.defun gcd &rest integers
Returns the greatest common divisor of the integers.  With no
arguments, 3gcd* returns 30*.

In lan{nil}, 3gcd* works on all gaussian integers.  The result
will always lie within the first quadrant, or along the positive real
axis.
.end_defun


.defun lcm integer &rest more-integers
Returns the least common multiple of the integers.

Like 3gcd*, 3lcm* in lan{nil} works on all gaussian integers.
.end_defun


.section "Irrational and Transcendental Functions"

Remember that the functions in this section which must perform their
operations in floating-point, will convert rational numbers to
3double-float* currently, but to 3single-float* in the future.

.defconstant pi
The value of this constant is 2pi*, in the longest floating-point
format available;  in lan{nil}, this is a long-float.  To use a
shorter format of 2pi*, for instance double-float, one should use
something like one of the forms
.lisp
(+ (float pi 0.0d0) 2n*)
(+ (coerce pi 'double-float) 2n*)
.end_lisp
to avoid having the value of 3pi* cause coercion to
3long-float* in your computations.  Uses of both 3coerce* and
3float* like the above will be optimized by the compiler into the
appropriate value.

If other similar constants are added to lan{nil}, they also will be
in long-float format, and should be treated similarly.
.end_defconstant

.subsection "Exponential and Logarithmic Functions"

.defun exp number
Returns 2e* raised to the power 2number*, where 2e* is the
base of the natural logarithms.  If 2number* is a float, the
answer is computed and returned in the same format;  if it is
rational, it is first converted to 3double-float*.
.end_defun

.defun expt base-number power-number
Returns 2base-number* raised to the power 2power-number*.  If
2base-number* is an rational number and the
2power-number* is an integer, the calculation will be exact and
the result will be a rational number.  Otherwise, the calculation
devolves into floating-point, and will use a logarithmic computation
if 2power-number* is not an integer.
.end_defun

.defun log number &optional base
Returns the logarithm of 2number* in the base 2base*, which
defaults to 2e*, the base of the natural logarithms.  The rules of
contagious coercion apply here;  2number* and 2base* are
converted to the largest format of the two, unless both are rational,
in which case they are converted to 3double-float*.

It is an error if 2number* is zero, unless 2base* is zero, in
which case the log is taken to be zero.
.end_defun

.defun sqrt number
Returns the principal square root of 2number*.  If 2number* is
rational, it is converted to a 3double-float* first;  3sqrt*
in lan{nil} never produces a rational number even if 2number*
might have a rational square root, even though this is not disallowed
by lan{common lisp}.

If 2number* is a negative non-complex number, a complex number is
returned.
.end_defun

.defun isqrt integer
Integer square-root:  the argument must be a non-negative integer, and
the result is the greatest integer less than or equal to the exact
positive square root of the argument.
.end_defun

.subsection "Trigonometric and Related Functions"

.defun abs number
Returns the absolute value of the argument, which may be any type of
number.

When applied to the complex plane, 3abs* returns the distance of
the point from the origin, which is
.lisp
(sqrt (+ (expt 2realpart* 2) (expt 2imagpart* 2))).
.end_lisp
Thus, for complex numbers, the result will always be floating-point
because there is a 3sqrt* hidden away in the computation.
Applications which require only 2comparing* distances from the
origin may use the above form without the 3sqrt* operation;  this
is done, for instance, by the internal code for 3gcd* of complex
integers.
.end_defun

.defun signum number
By definition,
.lisp
(signum 2x*) <=> (if (zerop 2x*) 2x* (/ 2x* (abs 2x*)))
.end_lisp
fun{signum} of an rational number will return
3-1*, 30*, or 31* according to whether the number is
negative, zero, or positive.  For a floating-point number, the result
will be a floating-point number of the same format with one of the
mentioned three values.

fun{signum} of a complex number is a complex number of the
same phase but with unit magnitude.  As a result, it will always be a
complex number with floating-point components (see the discussion
under 3abs*, above).
.end_defun


.defun sin radians
.defun1 cos radians
.defun1 tan radians
Standard trig functions.  The number 2radians* will be converted
to a 3double-float* if it is rational.  These accept complex
arguments.
.end_defun

.defun asin number
.defun1 acos number
fun{asin} returns the arcsine of the argument, and fun{acos} the
arccosine.  The result is in radians.  2number* will be converted
to a 3double-float* first if it is rational;  it may also be
complex.

Note that 3(asin -5)*, for instance, results in a complex answer.
.end_defun

.defun atan y &optional x
Fairly standard arctangent.

With one argument (which may be complex), the arctangent is returned;
for a non-complex argument, the result is between 7-/2* and 7/2*
(exclusive).  More generally, the following definition is used:
.lisp
atan(z) = -2i**log((1+2i**z)*sqrt(1/(1+z^2)))
.end_lisp

With two arguments, neither may be complex.  The arctangent of
32y*/2x** is returned, and the signs of 2y* and
2x* are used to derive quadrant information.  Also, 2x* may be
zero as long as 2y* is not zero.  The result will be between 7-*
(exclusive) and 7* (inclusive).
.end_defun


.defun sinh number
.defun1 cosh number
.defun1 tanh number
Hyperbolic sine, cosine, and tangent.  2number* may be complex.
.end_defun

.defun asinh number
.defun1 acosh number
.defun1 atanh number
Etc.
.end_defun


.section "Type Conversions and Component Extractions on Numbers"

.defun float number &optional other
If 2other* is not supplied, then if 2number* is a float of any
type, it is returned;  otherwise, it is converted to a float of the
default format, which is currently 3double-float*, but will be
3single-float* in the future.

If 2other* is supplied, then it must be a floating-point number.
2number* is converted to a float of the same type.  Thus,
.lisp
(float 2frob* 0.0f0)
.end_lisp
causes explicit conversion of 2frob* to a single-float.  Note that
this will convert to a shorter format also.

The lan{nil} compiler contrives to recognize the cases where
3float* is given a constant 2other* argument, and call special
efficient routines for converting to the given type.
.end_defun

.defun rational number
This converts 2number* to a rational
number.  If it is already rational, it is returned.  Otherwise, a
rational number is computed corresponding to the 2precise*
representation of the number.  For instance,
.lisp
(rational (float 7/11 0.0s0))  =>  333637/524288
.end_lisp
It is always the case that for a floating-point number 2f*,
.lisp
(= (float (rational 2f*) 2f*) 2f*)  =>  t
.end_lisp
.end_defun

.defun rationalize number
If 2number* is rational, it is
returned.  Otherwise, the floating-point representation is taken to be
an 2approximation* of a rational number, and that rational number
is returned.  For instance,
.lisp
(rationalize (float 7/11 0.0s0))  =>  7/11
.end_lisp
3rationalize* is not the most efficient coercion routine around...
.end_defun

.defun complex realpart &optional (imagpart 0)
This constructs a complex number with real part of 2realpart*, and
imaginary part of 2imagpart*.  If 2realpart* is rational and
2imagpart* is either (integer) 0 or not supplied, then the result
is just 2realpart*, because complex numbers with rational
components and a zero imaginary part automatically turn back into
rational (non-complex) numbers.  If either argument is floating-point,
then both components will be converted to the longest floating point
format of the two.  For instance,
.lisp
(complex 5 3)		=>  #c(5 3)
(complex 1/5 3.0d0)	=>  #c(0.2d0 3.0d0)
(complex 2.5l0 0.7s0)	=>  #c(2.5l0 0.7l0)
(complex 2)		=>  2
(complex 2.0)		=>  #c(2.0 0.0)
.end_lisp
.end_defun

.defun truncate number &optional divisor
.defun1 floor number &optional divisor
.defun1 ceiling number &optional divisor
.defun1 round number &optional divisor
These functions serve two similar purposes.  They may be used to
convert from a floating-point number to an integer in various useful
ways, and they can also perform division/remainder operations
similarly.

If only one argument is given, it is converted to an integer by the
appropriate method:  by truncation for 3truncate*, by rounding
towards negative infinity for 3floor*, by rounding towards
positive infinity for 3ceiling*, or by rounding towards the
nearest integer for 3round*.  (The lan{nil} and lan{common
lisp} 3round* will round an exact half by rounding towards the
even integer;  in this it may differ from rounding in other
languages.)  Two values are returned:  the first is the result of the
conversion, and the second is the remainder for the operation.  If
2number* is an integer, then the first value is that integer and
the second is 30*.  If it is a ratio, then the second will also be
a ratio, and if it is a float, then the second will be a float of the
same format.  For example,
.lisp
(truncate 2.5)		=>  {2, 0.5}
(truncate 5/2)		=>  {2, 1/2}
(truncate -2.5)		=>  {-2, -0.5}
(truncate -5/2)		=>  {-2, -1/2}
(ceiling 2.5)		=>  {3, -0.5}
(ceiling 5/2)		=>  {3, -1/2}
(ceiling -2.5)		=>  {-2, -0.5}
(ceiling -5/2)		=>  {-2, -1/2}
(floor 2.5)		=>  {2, 0.5}
(floor 5/2)		=>  {2, 1/2}
(floor -2.5)		=>  {-3, 0.5}
(floor -5/2)		=>  {-3, 1/2}
(round 2.5)		=>  {2, 0.5}
(round -2.5)		=>  {-2, -0.5}
(round 2.6)		=>  {3, -0.4}
(round -2.6)		=>  {-3, 0.4}
(round 3.5)		=>  {4, -0.5}
(round -3.5)		=>  {-4, 0.5}
.end_lisp

If the 2divisor* argument is given, the first value is the result
of integer conversion of the result of dividing 2number* by
2divisor*, after the appropriate type of rounding or truncation is
performed.  The second value is the remainder for that division after
the rounding/truncation.  That is, if the values are 2q* and
2r*, then
.lisp
(= 2number* (+ (* 2q* 2divisor*) 2r*))  =>  t
.end_lisp
For instance,
.lisp
(truncate 5 2)		=>  {2, 1}
(truncate -5 2)		=>  {-2, -1}
(truncate 5 -2)		=>  {-2, 1}
(truncate -5 -2)	=>  {2, -1}
(floor 5 2)		=>  {2, 1}
(floor -5 2)		=>  {-3, 1}
(floor 5 -2)		=>  {-3, -1}
(floor -5 -2)		=>  {2, -1}
.end_lisp

What this means is, if 2truncate* is given two integer arguments,
then the two values are the quotient and remainder, as obtained by
those functions.  If 2floor* is given two integer arguments, then
the second value is the standard 3mod* ((mod-fun)).
.end_defun

.defun rem number divisor
When 3rem* is given integer arguments, it is identical to
the lan{maclisp} 3remainder* function.  More generally, however,
it performs the 3truncate* operation on its two arguments, and
returns the second value from that as its value.
.end_defun

.defun remainder number divisor
This is identical to 3rem*.  The name is retained for
lan{maclisp} compatibility:  if 2number* and 2divisor* are
both integers (which is all the lan{maclisp} 3remainder*
function accepts), then the operation is the same.

One slight discrepency exists with the lan{maclisp} 3remainder*
function:  in lan{maclisp}, 3remainder* will accept a
2divisor* argument of 30* and return 2number*.  This is
incompatible with the definition of 3rem* (and also with fixnum
open-compilation of 3remainder* in lan{maclisp}!) because of the
implicit division involved--in lan{nil}, a divisor of 30*
results in a division-by-zero error.
.end_defun

.defun mod number divisor
When 2number* and 2divisor* are both integers, then 3mod*
is the standard "modulus" function.  More generally, 3mod*
performs the 3floor* operation on its two arguments, and returns
the second value from that as its value.

Note that by virtue of its definition in terms of 3floor* which is
a kind of division, a 2divisor* of zero results in a
division-by-zero error.
.end_defun

.defun ffloor number &optional divisor
.defun1 ftruncate number &optional divisor
.defun1 fceiling number &optional divisor
.defun1 fround number &optional divisor
These functions behave just like 3floor*, 3truncate*,
3ceiling*, and 3round*, except that the first value returned
is converted to a float if it is not.  While this is fairly useless
for rational arguments, it can result in some efficiency gain for
arguments of type 3float*.  Note that if both arguments are
rational, only the first value will be a double-float, not the second.
.end_defun

.section "Logical Operations on Numbers"
.setq logical-operations-on-numbers-section-page section-page

The logical operations in this section treat integers as if they were
represented in two's-complement notation.  (In lan{nil}, both
fixnums and bignums in fact are represented that way.)

.defun logior &rest integers
.defun1 logxor &rest integers
.defun1 logand &rest integers
.defun1 logeqv &rest integers
These return the bit-wise logical 2inclusive or*, 2exclusive
or*, 2and*, or 2equivalence* (also known as 2exclusive
nor*) of their arguments.  If no arguments are given, the results
are 30* for fun{logior} and fun{logxor}, and 3-1* for
fun{logand} and fun{logeqv}, which are the identities for those
operations.  Note that these functions are not yet defined;  for use
on fixnums only, use fun{logior&}, fun{logxor&}, fun{logand&},
or fun{logeqv&} ((logior&-fun)).
.end_defun

.defun lognand integer1 integer2
.defun1 lognor integer1 integer2
.defun1 logandc1 integer1 integer2
.defun1 logandc2 integer1 integer2
.defun1 logorc1 integer1 integer2
.defun1 logorc2 integer1 integer2
These are the other six non-trivial bit-wise logical operations on two
arguments.  Because they are not commutative or associative, they
take exactly two arguments rather than any non-negative number of
arguments.

The "c1" and "c2" in some of the above names should be read as "having
complemented argument 1 (2or* 2)";  for instance, 3logorc1* is
the logical 2or* of the logical complement of 2integer1*, with
2integer2*.

fun{logandc1} and fun{logandc2} are often used as bit-clearing
functions.  However, the ordering given to such names as
3bit-clear* or 3logclr* is often confusing (and
historically, has been incompatible from one macro-package to
another).  fun{logandc1} returns 2integer2* with all bits which
are on in 2integer1*, cleared;  fun{logandc2} returns
2integer1*, after clearing any bits which are set in
2integer2*.
.end_defun

.defun boole op integer1 integer2
The function fun{boole} takes an operation 2op* and two
integers, and returns an integer produced by performing the logical
operation specified by 2op* on the two integers.

There are sixteen variables (the names of which are listed below)
which have the boolean functions as their values;  the boolean
functions are represented as fixnums from 0 to 15 (inclusive).

The lan{nil} implementation of fun{boole} defines the boolean
functions such that they map into the standard "truth table" used in
lan{maclisp}.  That is, if the binary representation of 2op* is
2abcd*, then the truth table for the boolean operation is
.lisp
        y
    | 0   1
------------
  0 | a   c
x   |
  1 | b   d
.end_lisp
For example, the boolean function 34* has binary representation
30100*.  This shows that the result will have a bit set only when
the corresponding bit of 2integer1* is 31* and 2integer2*
is 30*.  This is the 3logandc2* operation.  New code,
especially that intended to be transported between lan{common lisp}
implementations, should 2never* rely on this--this coincidence is
provided 2only* for lan{maclisp} compatibility.

For lan{maclisp} compatibility, when lan{nil} fun{boole}
receives more than three arguments, it goes from left to right, thus:
.lisp
(boole k x y z) <=> (boole k (boole k x y) z)
.end_lisp
In certain cases it may accept less than three arguments.  Again,
new code should not rely on this behaviour.
.end_defun

.defun lognot integer
Returns the bit-wise logical 2not* of its argument.  Every bit of
the result is the complement of the corresponding bit in the argument.
.end_defun

.defun logtest integer1 integer2
fun{logtest} is a predicate which is true if any of the bits
designated by the 31*'s in 2integer1* are 31*'s in
2integer2*.
.lisp
(logtest 2x* 2y*) <=> (not (zerop (logand 2x* 2y*)))
.end_lisp
.end_defun

.defun logbitp index integer
fun{logbitp} is true if the bit in 2integer* whose index is
2index* (that is, its weight is 3(expt 2 2index*)*) is a
one-bit;  otherwise, it is false.
.end_defun

.defun ash integer count
Shifts 2integer* arithmetically left by 2count* bit positions
if 2count* is positive, or right -2count* bit positions if
2count* is negative.  The sign of the result is always the same as
the sign of 2integer*.

The actual implementation of fun{ash} works on, and will produce,
bignums.  There is also an fun{ash&} function which deals only with
fixnums.  

In practice, 2count* is only allowed to be a fixnum...
.end_defun

.defun logcount integer
If 2integer* is non-negative, 3logcount* returns the number of
"1" bits on in its twos-complement representation.  If it is negative,
then the number of "0" bits in that representation is returned;  this
is then the same as the count of "1" bits in the logical complement of
it.
.end_defun

.defun integer-length integer
3integer-length* returns the zero-origined index of the sign bit
of the field needed to represent 2integer* in twos-complement
notation.  That is, any integer 2i* may be represented in
twos-complement notation in a field 3(1+ (integer-length
2i*))* long.  If 2integer* is non-negative, then it may be
represented in unsigned binary form in a field 3(integer-length
2integer*)* long.  For instance,
.lisp
(integer-length 5)  =>  3
.end_lisp
because the binary representation of 35* is 3...0101*.
.end_defun

The following two functions are provided for lan{maclisp}
compatibility.  They both do some semblance of manipulation of the
binary representation of integers.  However, the results of these
functions are defined in terms of the absolute value of the integer
they are examining--because in lan{nil} integers are oriented
towards manipulation of their twos-complement representation, these
routines may not be particularly efficient on negative integers.

.defun haulong integer
Returns the number of significant bits in the absolute value of
2integer*.  The precise computation performed is
2ceiling*(log2(2abs*(2integer*)+1)).

For example:
.lisp
(haulong 0) => 0
(haulong 3) => 2
(haulong 4) => 3
(haulong -7) => 3
.end_lisp
3haulong* is provided for lan{maclisp} compatibility;
3integer-length* should be used in preference.
.end_defun

.defun haipart integer count
This function exists primarily for lan{maclisp} compatibility.  Its
functionality is subsumed by the byte manipulation functions 3ldb*
and 3dpb*, which are described in the following section.

3haipart* returns the high 2count* bits of the binary
representation of the absolute value of 2integer*, or the low
-2count* bits if 2count* is negative.
.end_defun


.section "Byte Manipulation Functions"
.setq byte-manipulation-section-page section-page

There are various functions in lan{nil} and lan{common lisp} to
deal with arbitrary-width contiguous fields of bits within integers.

Conceptually, most of these functions use objects called term_i{byte
specifiers} to describe such fields.  The representation of a byte
specifier, and the restrictions on the fields it is capable of
describing, are implementation dependent.  The function fun{byte}
accepts two integers representing the 2size* and 2position* of
the byte, and returns a byte specifier.  Such a specifier designates a
byte whose width is 2size*, and whose right-hand bit has weight
3(expt 2 2position*)*, in the terminology of integers used as
logical bit vectors.

.defun byte size position
Returns a byte-specifier.
.end_defun

.defun byte-size bytespec
.defun1 byte-position bytespec
Returns the size/position of the bytespec.
.end_defun

Historically, the functions fun{ldb} and fun{dpb}, although first
implemented in Lisp Machine Lisp, are derived from the lan{pdp-10}
instruction set.  In that context, a four-digit octal number is used
as a bytespec;  it is typically referred to as term_i{ppss},
because, in octal, the byte position is 2pp*, and the byte size is
2ss*.  The fun{ldb}, fun{dpb}, fun{mask-field}, and
fun{deposit-field} functions were originally implemented with such a
bytespec, usually typed in by the user in octal.  Both lan{maclisp}
and lan{nil} originally implemented fun{ldb} and fun{dpb} in
this way, such that they only operated on fixnums.  However, the
lan{common lisp} definitions must work on all integers.
Additionally, it was decided that the range restrictions of the
2ppss* bytespec were too limiting.  For that reason, lan{nil} has
incompatibly changed the bytespec format previously used.  Functions
are provided which utilize both the new and the old bytespecs.

.defun ldb bytespec integer
2bytespec* specifies a byte of 2integer* to be extracted.  The
result is returned as a positive integer.

A fixnum-only version which utilizes the new lan{nil} bytespec
format is available as fun{ldb&}, (ldb&-fun).

The original fixnum-only version, which utilizes the obsolete
2ppss* bytespec format, is available as fun{%ldb}, (%ldb-fun).

There is also fun{load-byte} ((load-byte-fun)), which takes the
byte position and size separately, and operates only on fixnums.
.end_defun

.defun ldb-test bytespec integer
.lisp
(not (zerop (ldb 2bytespec* 2integer*)))
.end_lisp
.end_defun

.defun mask-field bytespec integer
??Not yet in??
.end_defun

.defun dpb newbyte bytespec integer
Returns a number which is the same as 2integer* except that the bits
specified by 2bytespec* are replaced by 2newbyte*, which is
interpreted as twos-complement, and truncated if necessary.

For limited
fixnum-only applications using new the bytespec format, see
fun{dpb&} and fun{set-ldb&}, (dpb&-fun).  For utilizing the
obsolete 2ppss* bytespec format, see fun{%dpb}, (%dpb-fun).

There is also the fixnum-only fun{deposit-byte}
((deposit-byte-fun)), which takes the position and size separately,
and operates only on fixnums.
.end_defun

.defun deposit-field newbyte bytespec integer
??not yet in??
.end_defun


.section "Random Numbers"
.cindex random numbers

.defun random &optional modulus random-state
If no 2modulus* argument is given, then this is compatible with
the lan{maclisp} 3random* function of no arguments:  it returns
a number randomly distributed over the range of all fixnums.
(lan{Common lisp} does not define 3random* of no arguments.)
Otherwise, the answer returned by 3random* is a number of the same
type evenly distributed between zero (inclusive) and 2modulus*
(exclusive).  

If 2random-state* is supplied, it must be an object of type
3random-state*;  this is what holds the state of the random number
generator.  If it is not supplied, then the global random number state
(the value of 3*random-state**) is used.

The random number returned is random over "all its bits";
2random-state* is used to compute a sequence of random bits which
are used to construct the result.  For a floating-point number, this
is used as the significand (fraction) of a constructed number which is
scaled to the appropriate range;  for an integer, a sequence of bits
is constructed approximately 10 bits longer than that needed for the
result, and then a modulus operation performed.
.end_defun

.defvar *random-state*
This holds the global random state used by default by 3random*.
One may, for instance, lambda-bind this variable to a new object of
type 3random-state* to save and restore the state of the random
number generator.
.end_defvar

.defun make-random-state &optional state
This creates a new 3random-state* object.  If 2state* is
3nil* or not supplied, then a copy of the current value of
3*random-state** is returned.  If 2state* is 3t*, then a
new random-state is returned, seeded from the time.  Otherwise,
2state* should be a 3random-state*;  its state is copied.
.end_defun

When lan{nil} is first loaded up, the random-state object in
3*random-state** is always in the same state.  It may be seeded
from the current time by doing
.lisp
(setq *random-state* (make-random-state t))
.end_lisp
if that is necessary for applications.  There is, however, no
officially defined way to get a "known" random-state from which the
same sequence of pseudo-random numbers may be generated, other than
copying one with 3make-random-state* and saving it.  If this is
found to be necessary (for instance to reproducibly debug a program
which uses the random number generator), the form
.lisp
(si:make-random-state-internal)
.end_lisp
will create a new random-state the same as the one lan{nil} starts
up with.

For lan{maclisp} compatibility, the 3random* option to the
fun_i{status} and fun_i{sstatus} macros is supported.  3(status
random)* returns a copy of the current value of
3*random-state**;  3(sstatus random 2random-state*)*
restores 3*random-state** to a copy of that.  One may also reseed
by doing 3(sstatus random 2integer*)*.

.section "Fixnum-Only Arithmetic"
.setq fixnum-only-arithmetic-section-page section-page

Currently, the lan{nil} compiler does not make any use of type
declarations to help it decide to inline-code arithmetic routines.
Primarily for this reason, lan{nil} provides a full complement of
fixnum-only and double-float-only arithmetic routines, which will be
inline-coded by the compiler (when possible and reasonable) into
fairly efficient code.

In lan{nil}, as in lan{maclisp}, the totally open-compiled
fixnum-only routines behave "as the machine does";  that is, overflow
is generally not detected.  Note that the lan{vax} hardware detects
division by zero, however, and those routines not compiled as machine
instructions, such as fun_i{^&}, may detect overflow and signal an
error.

.subsection "Comparisons"

.defun =& number &rest more-numbers
.defun1 /=& number &rest more-numbers
.defun1 <& number &rest more-numbers
.defun1 >& number &rest more-numbers
.defun1 <=& number &rest more-numbers
.defun1 >=& number &rest more-numbers
Fixnum-only versions of the 3=*, 3/=*, 3<*, etc. functions.
.end_defun

.defun max& fixnum &rest more-fixnums
.defun1 min& fixnum &rest more-fixnums
Fixnum-only fun{max} and fun{min}.
.end_defun

.subsection "Arithmetic Operations"

.defun +& &rest fixnums
Fixnum-only fun{+} (fun{plus}).
.end_defun

.defun -& fixnum &rest more-fixnums
One arg:  unary negation.  Otherwise, fixnum-only subtraction.
.end_defun

.defun *& &rest fixnums
Fixnum-only multiplication.
.end_defun

.defun /& fixnum &rest more-fixnums
Fixnum-only division.  With one argument, reciprocates, which seems
singularly useless to me;  since this is truncating division,
reciprocation is an error if the argument is zero, one if it is one,
otherwise zero.
.end_defun


.defun \& fixnum1 fixnum2
Fixnum-only remainder.  Although there is no lan{common lisp}
fun{\} function to make the fixnum-only (as inherited from
lan{maclisp}) fun{\} function change incompatibly, the name of
fun{\} is being changed to fun{\&} for consistency.  Note that
this function must normally be typed in as 3\\&*, because 3\*
is the "quoting" character in lan{nil}.
.end_defun

.defun 1+& fixnum
.defun1 1-& fixnum
Fixnum-only fun{1+} and fun{1-}.
.end_defun

.defun abs& fixnum
Fixnum-only fun{abs}.
.end_defun

.defun signum& fixnum
Fixnum-only fun{signum}.
.end_defun

.defun ^& fixnum1 fixnum2
Fixnum-only fun{expt}.  It is an error for the result to exceed the
range representable by a fixnum.
.end_defun

.subsection "Bits and Bytes"

.defun logand& &rest fixnums
.defun1 logior& &rest fixnums
.defun1 logxor& &rest fixnum
.defun1 logeqv& &rest fixnums
.defun1 lognand& fixnum1 fixnum2
.defun1 lognor& fixnum1 fixnum2
.defun1 logandc1& fixnum1 fixnum2
.defun1 logandc2& fixnum1 fixnum2
.defun1 logorc1& fixnum1 fixnum2
.defun1 logorc2& fixnum1 fixnum2
Fixnum-only boolean functions
.end_defun

.defun boole& op fixnum1 fixnum2
Fixnum-only fun{boole}.
.end_defun

.defun lognot& fixnum
Fixnum-only fun{lognot}.
.end_defun

.defun logtest& fixnum1 fixnum2
Fixnum-only fun{logtest}.
.end_defun

.defun logbitp& index fixnum
Fixnum-only fun{logbitp}.  This is defined for an 2index* larger
than the number of bits in a fixnum;  however, 2index* must be a
fixnum.
.end_defun

.defun ash& fixnum count
Fixnum-only fun{ash}.  Shifting by a positive 2count* may shift
bits into the sign position, thus changing the sign of the result (and
losing bits).  It is an error if 2count* is not of type
3(signed-byte 8)*, that is, between -128 and 127 inclusive.
.end_defun

.defun logcount& fixnum
Not yet in?
.end_defun

.defun haulong& fixnum
Not inline-coded, but provided for completeness (see, perhaps,
fun{%fixnum-haulong}, (%fixnum-haulong-fun)).  Maybe this should
be diked, since fun{haulong} should dispatch just as rapidly.
.end_defun

.defun ldb& bytespec fixnum
Fixnum-only fun{ldb}.  This is not strictly a version of generic
fun{ldb} which takes a fixnum second argument, but rather a version
of low-level fixnum byte-extraction which takes a general bytespec as
an argument:  it is an error for the byte to extend outside of the
fixnum (for the position plus the size of the bytespec to be greater
than 30).
.end_defun

.defun dpb& newbyte bytespec fixnum
As fun{ldb&} is to fun{ldb}, so fun{dpb&} is to fun{dpb}.
Other 3ldb&* restrictions apply.
.end_defun

.defun set-ldb& bytespec fixnum newbyte
Maybe this shouldn't be here, but it is in case fun{setf} gets used
on fun{ldb&}.
.end_defun

Back in the olden days when there were few thoughts about integers
'cindex ppss
'cindex byte specifier
greater than 34359738367 (or something like that), the byte-specifier to
3ldb* and its friends used to be designated as 2ppss*.  The
interpretation of this is that, if you consider 2ppss* to be a
4-digit octal number, the number (octal) 2pp* tells the
2position* of the byte being referenced, and the 2ss* the
size.  In order that a byte specifier not be so restricted in the size
of the "byte" it is referencing (since the 2pp* can be
upwards-compatibly extended to the left but the 2ss* cannot),
lan{nil} has incompatibly abandoned that format.  So that code which
uses this old format may be trivially converted, however, the old
functionality may be obtained with the 3%ldb* and 3%dpb*
functions, below.

.defun %ldb ppss fixnum
Extracts the byte defined by 2ppss* (as described above) from
2fixnum*.  It is an error if the byte so referenced lies outside
of the fixnum (that is, the size plus the position is greater than
30).
.end_defun

.defun %dpb val ppss fixnum
Returns a fixnum which is 2fixnum* with the byte defined by
2ppss* replaced by the fixnum 2val* (truncated as necessary).
It is an error if the byte so referenced lies outside of the fixnum
(that is, the size plus the position is greater than 30).
.end_defun

.subsection "The Super-Primitives"

Getting closer still to the hardware...

.defun load-byte fixnum position size
This is the primitive lan{nil} extract-a-byte-from-a-fixnum
function.  In the style of many lan{nil} primitives, and in the
style of the lan{vax} byte-extracting instructions, it takes
arguments of position and size (different ordering from the
fun{byte} function).  It is an error for the byte described by
2position* and 2size* to lie out of bounds of the internal
representation of a fixnum (30 bits).
.end_defun

.defun deposit-byte fixnum position size newbyte
Modifies the byte, as per fun{load-byte}.  Note argument ordering is
different from fun{dpb} in that 2newbyte* comes last.  This is
to make it convenient for fun{setf} to use.
.end_defun

.defspec sys:%fixnum-plus-with-overflow-trapping x y overflow-code...
.defspec1 sys:%fixnum-difference-with-overflow-trapping x y overflow-code...
.defspec1 sys:%fixnum-times-with-overflow-trapping x y overflow-code...
.defspec1 sys:%fixnum-ash-with-overflow-trapping x y overflow-code...
These are special forms which primarily exist for the benefit of
implementing generic arithmetic functions.  The appropriate binary
operation on 2x* and 2y*, inline-coded, is performed;  if
afterwards there has been no overflow, that result is returned.
Otherwise, 2overflow-code* is run, and the resultant value
returned.

Only the compiler knows how to use these right now.
.end_defspec


.section "Double-Float-Only Arithmetic"
.setq double-float-only-arithmetic-section-page section-page

lan{nil} provides some functions (like those in lan{maclisp})
which operate only on double-floats.  It is unlikely that
corresponding functions will be provided for other floating-point
types when they are added, however;  inline-coded arithmetic on such
numbers will be handled by declarations to the compiler eventually.

.defun +$ &rest double-floats
.defun1 *$ &rest double-floats
.defun1 -$ double-float &rest more-double-floats
.defun1 /$ double-float &rest more-double-floats
.defun1 1+$ double-float
.defun1 1-$ double-float
Double-float-only stuff.  Essentially this is maclisp-compatible.
.end_defun

.defun abs$ double-float
Double-float-only fun{abs}.
.end_defun

.defun max$ &rest double-floats
.defun1 min$ &rest double-floats
.end_defun

.defun ^$ double-float fixnum
The double-float only exponentiation function.
.end_defun


.section "Decomposition of Floating Point Numbers"

All of the following routines are defined by lan{common lisp}.
The basic premise is that a floating point number is represented by
some number of digits in a base 2b*, multiplied by 2b* to some
exponent, with a sign.  In lan{nil} on the lan{vax}, 2b* is of
course 32* for the primitive floating-point data types, so the
exponent is a binary exponent.

.defun float-radix float
This returns the radix 2b* of 2float*.  For the lan{nil}
primitive float data types (3short-float*, 3single-float*,
3double-float*, and 3long-float*), it always returns 32*.
.end_defun

.defun decode-float float
This function returns three values:
.table 2 250 250 0 0 0
.item (1)
The term_i{significand} of 2float*.  This is a number between
31/2b** (inclusive) and 31* (exclusive), which represents
the bits of 2float*.  The sole exception is for zero, for which
the returned significand is zero (of the same floating-point type as
2float*).
.item (2)
The 2exponent* of 2float*.  This is an integer which, if used
to scale the significand (using 3scale-float*, below), will
produce a number with the same absolute value as 2float*.
.item (3)
The sign of 2float*;  this is either 31.0* or 3-1.0*, in
the same floating-point format as 2float*.
.end_table
Thus,
.lisp
(multiple-value-bind (significand exponent sign)
		     (decode-float float)
  (= float (* (scale-float significand exponent) sign)))
 => t
.end_lisp
.end_defun

.defun scale-float float integer
This is like doing
.lisp
(* 2float* (expt 2b* 2integer*))
.end_lisp
where 2b* is the radix of 2float*.  It is done, of course,
somewhat more efficiently and without danger of any sort of
intermediate overflow or underflow if the final result can be
represented.  It is an error if the final result cannot be
represented;  3scale-float* will signal an error.  (In a future
lan{nil} with a smarter compiler and type declarations, however, it
may be the case that open-compilation of this function will not signal
an error.)

Those familiar with the lan{pdp10} lan{maclisp} fun_i{fsc}
function will recognize this as being somewhat of the same thing,
although it is not subject to the kludges that 3fsc* is (partly
because the lan{vax} does not represent unnormalized floating point
numbers).
.end_defun

.defun float-sign float &optional other
If 2other* is not supplied, then this returns the sign of
2float*, 31.0* or 3-1.0*, in the same format as
2float*.  This is the same as the third value returned by
3decode-float*.

If 2other* is supplied, then the effect is of transfering the sign
of 2float* to 2other*;  the result will be of the same
floating-point format and absolute value as 2other*, but have the
same sign as 2float*.
.end_defun

.defun float-digits float
This returns the number of base 2b* digits in the representation
of 2float*.  In lan{nil}, this is a constant for any particular
one of the primitive floating-point types.  Specifically,
3short-float* has 319*, 3single-float* has 324*,
3double-float* has 356*, and 3long-float* has 3128*.
.end_defun

.defun float-precision float
This (he said while looking the other way) is the same as
3float-digits* except that it returns 30* for zero.
.end_defun

.defun integer-decode-float float
This returns three values, like 3decode-float*.  The difference is
that the significand is returned as an integer, and the exponent
differs accordingly.  The magnitude of the integer is such that it is
between 32^2p** (exclusive), and 32^(2p*-1)*
(inclusive), where 2p* is the precision of 2float* (as would
be returned by 3float-precision*).  If the float radix is 32*
as it is for the lan{nil} primitive floating types, then the integer
will have the same number of bits (3integer-length*,
(integer-length-fun)) as the precision.  Again, an exception for zero
exists;  the first value will then be 30*.
.end_defun


.section "Implementation Constants"

.defconstant most-positive-fixnum
.defconstant1 most-negative-fixnum
These have as their values the most positive and negative fixnums
representable in lan{nil};  integers of the same sign but greater
magnitudes have to be represented as bignums.  Because lan{nil} uses
twos-complement representation for fixnums, the absolute value of
3most-negative-fixnum* is one greater than
2most-positive-fixnum*.
.end_defconstant

.defconstant most-positive-short-float
.defconstant1 most-positive-single-float
.defconstant1 most-positive-double-float
.defconstant1 most-positive-long-float
These have as their values the most positive numbers of the
corresponding formats which can be represented.
.end_defconstant

.defconstant most-negative-short-float
.defconstant1 most-negative-single-float
.defconstant1 most-negative-double-float
.defconstant1 most-negative-long-float
These have as their values the most negative numbers of the
corresponding formats which can be represented.
.end_defconstant

.defconstant least-positive-short-float
.defconstant1 least-positive-single-float
.defconstant1 least-positive-double-float
.defconstant1 least-positive-long-float
These have as their values the smallest numbers of the corresponding
formats that can be represented, which are still positive.
.end_defconstant

.defconstant least-negative-short-float
.defconstant1 least-negative-single-float
.defconstant1 least-negative-double-float
.defconstant1 least-negative-long-float
These have as their values the most positive negative numbers
representable in the corresponding formats.
.end_defconstant

.defconstant short-float-epsilon
.defconstant1 single-float-epsilon
.defconstant1 double-float-epsilon
.defconstant1 long-float-epsilon
These have as their values the smallest positive numbers which, when
added to 31.0* of the corresponding fomat, produce a different
answer.
.end_defconstant

.defconstant short-float-negative-epsilon
.defconstant1 single-float-negative-epsilon
.defconstant1 double-float-negative-epsilon
.defconstant1 long-float-negative-epsilon
These are broken and wrong.
.end_defconstant

