The Integer
class provides multiple precision integer arithmetic
facilities. Some representation details are discussed in the
Representation section.
Integers
may be up to b * ((1 << b) - 1)
bits long, where
b
is the number of bits per short (typically 1048560 bits when
b = 16
). The implementation assumes that a long
is at least
twice as long as a short
. This assumption hides beneath almost all
primitive operations, and would be very difficult to change. It also relies
on correct behavior of unsigned arithmetic operations.
Some of the arithmetic algorithms are very loosely based on those provided in the MIT Scheme `bignum.c' release, which is Copyright (c) 1987 Massachusetts Institute of Technology. Their use here falls within the provisions described in the Scheme release.
Integers may be constructed in the following ways:
Integer x;
Integer x = 2; Integer y(2);
Integer u(x); Integer v = x;
Integer
back into longs via the long
coercion operator. If the Integer cannot fit into a long, this returns
MINLONG or MAXLONG (depending on the sign) where MINLONG is the most
negative, and MAXLONG is the most positive representable long.
Integer
is < MAXLONG
and > MINLONG
.
Integer
to a double
, with potential
loss of precision.
+/-HUGE
is returned if the Integer cannot fit into a double.
Integer
can fit into a double.
All of the usual arithmetic operators are provided (+, -, *, /,
%, +=, ++, -=, --, *=, /=, %=, ==, !=, <, <=, >, >=
). All operators
support special versions for mixed arguments of Integers and regular
C++ longs in order to avoid useless coercions, as well as to allow
automatic promotion of shorts and ints to longs, so that they may be
applied without additional Integer coercion operators. The only
operators that behave differently than the corresponding int or long
operators are ++
and --
. Because C++ does not
distinguish prefix from postfix application, these are declared as
void
operators, so that no confusion can result from applying
them as postfix. Thus, for Integers x and y, ++x; y = x;
is
correct, but y = ++x;
and y = x++;
are not.
Bitwise operators (~
, &
, |
, ^
, <<
,
>>
, &=
, |=
, ^=
, <<=
, >>=
) are
also provided. However, these operate on sign-magnitude, rather than
two's complement representations. The sign of the result is arbitrarily
taken as the sign of the first argument. For example, Integer(-3)
& Integer(5)
returns Integer(-1)
, not -3, as it would using
two's complement. Also, ~
, the complement operator, complements
only those bits needed for the representation. Bit operators are also
provided in the BitSet and BitString classes. One of these classes
should be used instead of Integers when the results of bit manipulations
are not interpreted numerically.
The following utility functions are also provided. (All arguments are Integers unless otherwise noted).
this
in place.
Integer sqr(x)
Integer sqrt(x)
long lg(x);
int sign(x)
if (sign(x) == 0)
is a generally faster method
of testing for zero than using relational operators.
int even(x)
int odd(x)
void setbit(Integer& x, long b)
void clearbit(Integer& x, long b)
int testbit(Integer x, long b)
Integer atoI(char* asciinumber, int base = 10);
void Integer::printon(ostream& s, int base = 10, int width = 0);
(*this)
as a base base
number, in field width at least width
.
ostream << x;
istream >> x;
int compare(Integer x, Integer y)
int ucompare(Integer x, Integer y)
add(x, y, z)
sub(x, y, z)
mul(x, y, z)
div(x, y, z)
mod(x, y, z)
and(x, y, z)
or(x, y, z)
xor(x, y, z)
lshift(x, y, z)
rshift(x, y, z)
pow(x, y, z)
complement(x, z)
negate(x, z)