********
Integers
********
.. current-library:: dylan
.. current-module:: dylan
.. TODO:
* This should be combined into language-extensions/
* Note that content below includes things compeletely unrelated to numbers.
This document describes the Open Dylan implementation of arithmetic
functions, especially integer arithmetic. It describes a number of
extensions to the Dylan language, which are available from the Dylan
library. It also describes a generic arithmetic facility that, through
the use of other libraries, allows you to extend arithmetic to special
number types, such as "big" (64-bit) integers.
Throughout this document, arguments are instances of the class specified
by the argument name (ignoring any numeric suffixes), unless otherwise
noted. Thus, the arguments *integer*, *integer1*, and *integer2* would
all be instances of the class :drm:``.
The goals of the extensions to the Dylan language described in this
document are as follows:
* Provide arithmetic operations that are closed over small integers.
This allows type inference to propagate small integer declarations more
widely, because there is no possibility of automatic coercion into some
more general format.
* Make the arithmetic operations that are closed over small integers
easily accessible to programmers.
* Allow the Dylan library to be described in such a way that only small
integers are present by default, moving support for infinite precision
integer arithmetic to the Big-Integers library, which must be explicitly
used.
* Support infinite precision integer arithmetic through the Big-Integers
library.
.. note:: Using that library in another library does not have a negative
effect on the correctness or performance of other libraries in the same
application that do not use it.
* Maintain compatibility with the DRM specification.
In particular, the extensions support the production of efficient code
for programs written to be portable with respect to the DRM
specification. Use of implementation-specific types or operations in
order to get reasonable efficiency is not required. This precludes
relegating the :drm:`` class and *limited-* types to
inefficient implementations.
.. note:: When there are several distinct interfaces with the same name
but in different modules, the notation *interface* *#* *module* is used
in this document to remove ambiguity.
* Specify that the class :drm:`` has a finite,
implementation-dependent range, bounded by the constants
``$minimum-integer`` and ``$maximum-integer``.
The representation for integers must be at least 28 bits, including the
sign. That is, the minimum conforming value for ``$maximum-integer`` is ``2 ^
27 - 1`` and the maximum conforming value for ``$minimum-integer`` is ``-2 ^
27``.
.. note:: *Rationale:* Restricting :drm:`` in this way allows the programmer
to stay in the efficient range without requiring exact knowledge of what
that range might be. The full generality of extended precision integers
is provided by the Big-Integers library, for programmers who actually
need that functionality.
* Define the type ```` to be the type union of :drm:`` and
:drm:``.
The Dylan library provides implementations of the generic functions and
functions described in this document. If the result of one of these
operations is specified to be an instance of :drm:`` and the
mathematically correct result cannot be represented as an :drm:``
then an error is signaled. This removes fully generic arithmetic from
the Dylan library. In particular, it removes extended integers, ratios,
and rectangular complex numbers.
Extensions to the dylan Library
===============================
This section describes the extensions to the Dylan library that provide
the arithmetic operations available as standard to your applications.
You do not have to explicitly use any additional libraries to have
access to any of the functionality described in this section. Note that
this section only describes extensions to the Dylan library; for
complete descriptions, you should also refer to the *Dylan Reference
Manual*.
Note that the Common-Dylan library also has these extensions because it
uses the Dylan library.
Ranges
------
The initialization arguments for :drm:`` must all be instances of
```` rather than :drm:``.
Specific constructors
---------------------
The following specific constructors are available for use with the class
:drm:``.
.. generic-function:: limited
Defines a new type that represents a subset of the class :drm:``.
:signature: limited *integer-class* #key *min* *max* => *limited-type*
:parameter integer-class: The singleton().
:parameter min: The lower bound of the range. The default is
``$minimum-integer``.
:parameter max: The upper bound of the range. The default is ``$maximum-integer``.
:description:
The *integer-class* argument is the class :drm:``, and all other
arguments are instances of :drm:``. The range of :drm:`` is
bounded by default.
.. function:: range
This function is used to specify ranges of numbers.
:signature: range (#key from:, to:, above:, below:, by:, size:) =>
:description:
All of the supplied arguments must be instances of ````.
Equality comparisons
--------------------
The ``=`` function compares two objects and returns ``#t`` if the values of
the two objects are equal to each other, that is of the same magnitude.
.. generic-function:: =
:open:
Tests its arguments to see if they are of the same magnitude.
:signature: = *object1* *object2* => *boolean*
.. method:: =
:sealed:
:specializer:
Tests its arguments to see if they are of the same magnitude.
:signature: = *complex1* *complex2* => *boolean*
.. method:: =
:specializer:
Tests its arguments to see if they are of the same magnitude.
:signature: = *machine-number1* *machine-number2* => *boolean*
Magnitude comparisons
---------------------
The Dylan library provides the following interfaces for testing the
magnitude of two numbers:
.. generic-function:: <
:open:
Returns #t if its first argument is less than its second argument.
:signature: < *object1* *object2* => *boolean*
.. method:: <
:sealed:
:specializer:
Returns #t if its first argument is less than its second argument.
:signature: < *complex1* *complex2* => *boolean*
.. method:: <
:specializer:
Returns #t if its first argument is less than its second argument.
:signature: < *machine-number1* *machine-number2* => *boolean*
Properties of numbers
---------------------
Various number properties can be tested using the following predicates
in the Dylan library:
.. generic-function:: odd?
:open:
Tests whether the argument supplied represents an odd value.
:signature: odd? *object* => *boolean*
.. method:: odd?
:sealed:
:specializer:
Tests whether the argument supplied represents an odd value.
:signature: odd? *complex* => *boolean*
.. method:: odd?
:specializer:
Tests whether the argument supplied represents an odd value.
:signature: odd? *integer* => *boolean*
.. generic-function:: even?
:open:
Tests whether the argument supplied represents an even value
:signature: even? *object* => *boolean*
.. method:: even?
:sealed:
:specializer:
Tests whether the argument supplied represents an even value
:signature: even? *complex* => *boolean*
.. method:: even?
:specializer:
Tests whether the argument supplied represents an even value
:signature: even? *integer* => *boolean*
.. generic-function:: zero?
:open:
Tests whether the argument supplied represents a zero value.
:signature: zero? *object* => *boolean*
.. method:: zero?
:specializer:
:sealed:
Tests whether the argument supplied represents a zero value.
:signature: zero? *complex* => *boolean*
.. method:: zero?
:specializer:
Tests whether the argument supplied represents a zero value.
:signature: zero? *machine-number* => *boolean*
.. generic-function:: positive?
:open:
Tests whether the argument supplied represents a positive value.
.. method:: positive?
:sealed:
:specializer:
Tests whether the argument supplied represents a positive value.
:signature: positive? *complex*
.. method:: positive?
:specializer:
Tests whether the argument supplied represents a positive value.
:signature: positive? *machine-number* => *boolean*
.. generic-function:: negative?
:open:
Tests whether the argument supplied represents a negative value.
:signature: negative? *object* => *boolean*
.. method:: negative?
:sealed:
:specializer:
Tests whether the argument supplied represents a negative value.
:signature: negative? *complex* => *boolean*
.. method:: negative?
:specializer:
Tests whether the argument supplied represents a negative value.
:signature: negative? *machine-number* => *boolean*
.. generic-function:: integral?
:open:
Tests whether the argument supplied represents an integral value.
:signature: integral? *object* => *boolean*
.. method:: integral?
:sealed:
:specializer:
Tests whether the argument supplied represents an integral value.
:signature: integral? *complex*
.. method:: integral?
:specializer:
Tests whether the argument supplied represents an integral value.
:signature: integral? *machine-number* => *boolean*
Arithmetic operations
---------------------
The following arithmetic operations are available in the Dylan library:
\+
Open generic function
\+ *object1* *object2* => #rest *object*
\+
Sealed domain
\+ *complex1* *complex* 2
\+
G.f. method
\+ *integer1* *integer* 2 => *integer*
\+
G.f. method
\+ *machine-number1* *machine-number2* => *machine-number*
Returns the sum of the two supplied arguments. The actual type of the
value is determined by the contagion rules when applied to the
arguments.
\-
Open generic function
\- *object1* *object2* => #rest *object*
\-
Sealed domain
\- *complex1* *complex2*
\-
G.f. method
\- *integer1 integer2* => *integer*
\-
G.f. method
\- *machine-number1* *machine-number2* => *machine-number*
Returns the result of subtracting the second argument from the first.
The actual type of the value is determined by the contagion rules when
applied to the arguments.
\*
Open generic function
\* *object1* *object2* => #rest *object*
\*
Sealed domain
\* *complex1* *complex2*
\*
G.f. method
\* *integer1* *integer* 2 => *integer*
\*
G.f. method
\* *machine-number1* *machine-number2* => *machine-number*
Returns the result of multiplying the two arguments. The actual type of
the value is determined by the contagion rules when applied to the
arguments.
/
Open generic function
/ *object1* *object2* => #rest *object*
/
Sealed domain
/ *complex1* *complex2*
/
G.f. method
/ *float1* *float* 2 => *float*
Returns the result of dividing the first argument by the second. The
actual type of the value is determined by the contagion rules when
applied to the arguments.
negative
Open generic function
negative *object* => #rest *negative-object*
negative
Sealed domain
negative *complex*
negative
G.f. method
negative *integer* => *negative-integer*
negative
G.f. method
negative *float* => *negative-float*
Negates the supplied argument. The returned value is of the same float
format as the supplied argument.
floor
Function
floor *machine-number* => *integer* *machine-number*
floor *integer* => *integer* *integer*
floor *float* => *integer* *float*
Truncates a number toward negative infinity. The integer part is
returned as *integer*, the remainder is of the same float format as the
argument.
ceiling
Function
ceiling *machine-number* => *integer* *machine-number*
ceiling *integer* => *integer* *integer*
ceiling *float* => *integer* *float*
Truncates a number toward positive infinity. The integer part is
returned as *integer*, the remainder is of the same float format as the
argument.
round
Function
round *machine-number* => *integer* *machine-number*
round *integer* => *integer* *integer*
round *float* => *integer* *float*
Rounds a number toward the nearest mathematical integer. The integer
part is returned as *integer*, the remainder is of the same float
format as the argument. If the argument is exactly between two integers,
then the result *integer* will be a multiple of two.
truncate
Function
truncate *machine-number* => *integer* *machine-number*
truncate *integer* => *integer* *integer*
truncate *float* => *integer* *float*
Truncates a number toward zero. The integer part is returned as
*integer*, the remainder is of the same float format as the argument.
floor/
Function
::
floor/ *machine-number1* *machine-number2* => *integer* *machine-number*
floor/ *integer1* *integer2* => *integer* *integer*
floor/ *machine-number1* *machine-number2* => *integer* *machine-number*
Divides the first argument into the second and truncates the result
toward negative infinity. The integer part is returned as *integer*,
the type of the remainder is determined by the contagion rules when
applied to the arguments.
ceiling/
Function
::
ceiling/ *machine-number1* *machine-number2* => *integer* *machine-number*
ceiling/ *integer1* *integer2* => *integer* *integer*
ceiling/ *machine-number1* *machine-number2* => *integer* *machine-number*
Divides the first argument into the second and truncates the result
toward positive infinity. The integer part is returned as *integer*,
the type of the remainder is determined by the contagion rules when
applied to the arguments.
round/
Function
::
round/ *machine-number1* *machine-number2* => *integer* *machine-number*
round/ *integer1* *integer2* => *integer* *integer*
round/ *machine-number1* *machine-number2* => *integer* *machine-number*
Divides the first argument into the second and rounds the result toward
the nearest mathematical integer. The integer part is returned as
*integer*, the type of the remainder is determined by the contagion
rules when applied to the arguments.
truncate/
Function
::
truncate/ *machine-number1* *machine-number2* => *integer* *machine-number*
truncate/ *integer1* *integer* 2 => *integer* *integer*
truncate/ *machine-number1* *machine-number2* => *integer* *machine-number*
Divides the first argument into the second and truncates the result
toward zero. The integer part is returned as *integer*, the type of the
remainder is determined by the contagion rules when applied to the
arguments.
modulo
Function
::
modulo *machine-number1* *machine-number2* => *machine-number*
modulo *integer1* *integer2* => *integer*
modulo *machine-number1* *machine-number2* => *machine-number*
Returns the second value of *floor/ (* *arg1* *,* *arg2* *)*. The
actual type of the second value is determined by the contagion rules
when applied to the arguments.
remainder
Function
::
remainder *machine-number1* *machine-number2* => *machine-number*
remainder *integer1* *integer2* => *integer*
remainder *machine-number1* *machine-number2* => *machine-number*
Returns the second value of *truncate/ (* *arg1* *,* *arg2* *)*.The
actual type of the second value is determined by the contagion rules
when applied to the arguments.
^
Open generic function
^ *object1* *object2* => #rest *object*
^
Sealed domain
^ *complex1* *complex* 2
^
G.f. method
^ *integer1* *integer2* => *integer*
^
G.f. method
^ *float1* *integer2* => *float*
Returns the first argument raised to the power of the second argument.
The value is of the same float format as the first argument. An error is
signalled if both arguments are 0.
abs
Open generic function
abs *object* => #rest *object*
abs
Sealed domain
abs *complex*
abs
G.f. method
abs *integer* => *integer*
abs
G.f. method
abs *float* => *float*
Returns the absolute value of the argument. The value is of the same
float format as the argument.
logior
Function
logior #rest *integers* => *integer*
Returns the bitwise inclusive *OR* of its integer arguments.
logxor
Function
logxor #rest *integers* => *integer*
Returns the bitwise exclusive *OR* of its integer arguments.
logand
Function
logand #rest *integers* => *integer*
Returns the bitwise *AND* of its integer arguments.
lognot
Function
lognot *integer1* => *integer2*
Returns the bitwise *NOT* of its integer arguments.
logbit?
Function
logbit? *index* *integer* => *boolean*
Tests the value of a particular bit in its integer argument. The *index*
argument is an instance of :drm:``.
ash
Function
ash *integer1* *count* => *integer*
Performs an arithmetic shift on its first argument.
lcm
Function
lcm *integer1* *integer2* => *integer*
Returns the least common multiple of its two arguments.
gcd
Function
gcd *integer1* *integer2* => *integer*
Returns the greatest common divisor of its two arguments.
Collections
-----------
The keys for sequences are always instances of :drm:``. This means
that certain kinds of collections cannot be sequences; very large (or
unbounded) sparse arrays are an example.
The Table Protocol
------------------
The following functions in the Dylan library are extended. Note that the
hash IDs for tables are always instances of :drm:``.
merge-hash-codes
Function
merge-hash-codes *id1* *state1* *id2* *state2* #key *ordered?*
=> *merged-id* *merged-state*
Returns a hash code created from the merging of two argument hash codes.
The *id* arguments are hash IDs, and the *state* arguments are hash
states (instances of :drm:`