IntInf
structureThe optional IntInf structure is one of the possible implementations of the INTEGER interface. In addition to the INTEGER operations, it provides some operations useful for programming with arbitrarily large integers. Note that operations in IntInf that return a value of type IntInf.int will never raise the Overflow exception.
signature INT_INF
structure IntInf
: INT_INF
include INTEGER
val divMod : (int * int) -> (int * int)
val quotRem : (int * int) -> (int * int)
val pow : (int * Int.int) -> int
val log2 : int -> Int.int
val orb : (int * int) -> int
val xorb : (int * int) -> int
val andb : (int * int) -> int
val notb : int -> int
val << : (int * Word.word) -> int
val ~>> : (int * Word.word) -> int
divMod (i, j)
(i div j, i mod j)
, but is likely to be more efficient than computing both components separately. Raises Div if j = 0.
quotRem (i, j)
(i quot j, i rem j)
, but is likely to be more efficient than computing both components separately. Raises Div if j = 0.
pow (i, j)
pow (i, j)
is is 1
; in particular, pow(0, 0)
is 1
. When j < 0, we define the following exceptional cases.
i | pow(i,j) |
---|---|
0 | Raise Div |
|i| = 1 | i^{(j)} |
|i| > 1 | 0 |
log2 i
k
for which pow
(2, k) <= i. Raises Domain if i <= 0. Raises Overflow if the result is not representable as an Int.int.
orb (i, j)
xorb (i, j)
andb (i, j)
notb i
~(i + 1)
.
<< (i, n)
~>> (i, n)
floor
(i / 2^{(n)}).
If an implementation provides the IntInf structure, then the type LargeInt.int must be the same as IntInf.int type.
The bit-wise operations (andb
, orb
, notb
, <<
, etc.) treat the integer arguments as having 2's complement representation. In particular, if we let bit = pow
(2,n), for all sufficiently large values of n we have
andb
(i, bit) = 0 if i >= 0andb
(i, bit) = bit if i < 0
Rationale:
It is useful to have a module providing bit-wise operations on an unbounded domain. Such a module can serve as the basis for implementing sets or bit vectors. These operations seemed to naturally fit into the specification of the IntInf module, rather than require an additional
WordInf
structure.
Implementation note:
Having this structure as part of the basis allows implementations to provide compiler or run-time support to optimize integer representation and operations.
INTEGER, LargeInt
Last Modified October 6, 1997
Comments to John Reppy.
Copyright © 1997 Bell Labs, Lucent Technologies