// Programm: integer.h
// Implements integer numbers of arbitrary size
#include
#include
#include
#include
#include
#include
namespace ifm {
class integer {
public:
// constructors
// ------------
integer(); // 0
integer(int i); // i
integer(unsigned int i); // i
integer(float f); // f
integer(double d); // d
// arithmetic operators (with the standard semantics)
// --------------------------------------------------
integer operator-() const;
integer& operator+=(const integer& x);
integer& operator++();
integer operator++(int);
integer& operator-=(const integer& x);
integer& operator--();
integer operator--(int);
integer& operator*=(const integer& x);
integer& operator/=(const integer& x);
integer& operator%=(const integer& x);
// global friend operators
// -----------------------
friend bool operator==(const integer& x, const integer& y);
friend bool operator<(const integer& x, const integer& y);
friend std::ostream& operator<<(std::ostream& o, const integer& x);
friend std::istream& operator>>(std::istream& i, integer& x);
private:
// typedefs
// --------
typedef std::deque Seq;
typedef Seq::iterator It;
typedef Seq::const_iterator Cit;
typedef Seq::const_reverse_iterator Crit;
// data members
// ------------
// an integer is represented by a base, a sign, and a sequence
// of digits in the given base.
// the base must be a power of 10 to facilitate decimal input and output
static const unsigned int power_ = 4;
static const unsigned int base_ = 10000;
// the sign
bool sign_; // false <=> negative
// the sequence
Seq seq_;
// represents the nonnegative number
//
// \sum_{i=0}^{seq_.size()-1} seq_[i]*base_^i
// The number 0 is represented by a length-1-sequence with seq_[0] == 0
// private member functions
// ------------------------
// PRE: seq_ is empty
// POST: seq_ is initialized to represent the number i
void init(unsigned int i);
// POST: return value is true iff |*this| < |x|.
bool abs_less(const integer& x) const;
// POST: seq_ is updated to represent |*this| + |x|
integer& add(const integer& x);
// PRE: |x| <= |*this|
// POST: seq_ is updated to represent |*this| - |x|
integer& subtract(const integer& x);
// PRE: *this != 0, x < base_
// POST: seq_ is updated to represent |*this| * |x|
integer& mult(unsigned int x);
// PRE: x != 0
// POST: *this is replaced by the remainder of the division
// of *this by x; r holds the result of the division
integer& div(const integer& x, integer& r);
// PRE: s >= 0
// POST: *this is multiplied by base_^s
integer& leftshift (int s);
// POST: returns true true iff highest significand digit is nonzero
bool is_normalized() const;
// POST: returns true iff *this has value 0
bool is_zero() const;
};
// global operators
// ----------------
bool operator!=(const integer& x, const integer& y);
bool operator<=(const integer& x, const integer& y);
bool operator>(const integer& x, const integer& y);
bool operator>=(const integer& x, const integer& y);
integer operator+(const integer& x, const integer& y);
integer operator-(const integer& x, const integer& y);
integer operator*(const integer& x, const integer& y);
integer operator/(const integer& x, const integer& y);
integer operator%(const integer& x, const integer& y);
// Implementation: public member functions
// ---------------------------------------
integer::integer() : sign_(true)
{
seq_.push_back(0);
assert (is_normalized());
}
void integer::init(unsigned int i)
{
assert (seq_.empty());
if (i == 0)
seq_.push_back(0);
else
while (i > 0) {
seq_.push_back(i % base_);
i /= base_;
}
}
integer::integer(int i) : sign_(i >= 0)
{
if (i < 0) i = -i;
init(i);
assert (is_normalized());
}
integer::integer(unsigned int i) : sign_(true)
{
init(i);
assert (is_normalized());
}
integer::integer(float f) : sign_ (f >= 0)
{
int exp;
float m = std::frexp (std::abs(f), &exp);
// if |f| is nonzero, then |f| = 0.b_1b_2....b_24 * 2^exp
// the integer resulting from this is obtained by moving the
// comma exp places to the right (and forgetting about the digits
// that may still follow)
integer b;
for (; exp > 0; --exp) {
b *= 2;
if (m >= 0.5f) {
b += 1;
m = 2.0f * (m - 0.5f);
} else
m = 2.0f * m;
}
seq_ = b.seq_;
assert (is_normalized());
}
integer::integer(double d) : sign_ (d >= 0)
{
int exp;
double m = std::frexp (std::abs(d), &exp);
// if |d| is nonzero, then |d| = 0.b_1b_2....b_53 * 2^exp
// the integer resulting from this is obtained by moving the
// comma exp places to the right (and forgetting about the digits
// that may still follow)
integer b;
for (; exp > 0; --exp) {
b *= 2;
if (m >= 0.5) {
b += 1;
m = 2.0 * (m - 0.5);
} else
m = 2.0 * m;
}
seq_ = b.seq_;
assert (is_normalized());
}
bool integer::abs_less(const integer& x) const
{
if (seq_.size() < x.seq_.size()) return true;
if (seq_.size() > x.seq_.size()) return false;
Crit i = seq_.rbegin();
Crit j = x.seq_.rbegin();
for (; i != seq_.rend(); ++i, ++j) {
if (*i < *j) return true;
if (*i > *j) return false;
}
return false;
}
integer integer::operator-() const
{
integer x = *this;
if (!is_zero()) x.sign_ = !sign_;
return x;
}
integer& integer::operator+=(const integer& x)
{
if (sign_ == x.sign_) return add(x);
if (!abs_less(x)) return subtract(x);
integer z = x;
z.subtract(*this);
std::swap(z, *this);
assert (is_normalized());
return *this;
}
integer& integer::operator++()
{
return *this += 1;
}
integer integer::operator++(int)
{
integer z = *this;
*this += 1;
return z;
}
integer& integer::operator-=(const integer& x)
{
if (sign_ != x.sign_) return add(x);
if (!abs_less(x)) return subtract(x);
integer z = x;
z.subtract(*this);
z.sign_ = !z.sign_;
std::swap(z, *this);
assert (is_normalized());
return *this;
}
integer& integer::operator--()
{
return *this -= 1;
}
integer integer::operator--(int)
{
integer z = *this;
*this -= 1;
return z;
}
integer& integer::operator*=(const integer& x)
{
if (is_zero()) return *this;
integer r = 0;
r.sign_ = (sign_ && x.sign_ || !sign_ && !x.sign_);
for (Cit i = x.seq_.begin(); i != x.seq_.end(); ++i) {
integer z = *this;
z.mult(*i);
r.add(z);
seq_.push_front(0);
}
std::swap(r, *this);
assert (is_normalized());
return *this;
}
integer& integer::operator/=(const integer& x)
{
assert(!x.is_zero());
integer r;
div(x, r);
std::swap(*this, r);
assert (is_normalized());
return *this;
}
integer& integer::operator%=(const integer& x)
{
assert(!x.is_zero());
integer r;
return div(x, r);
}
integer& integer::leftshift(int s)
{
assert (s >= 0);
if (!is_zero())
for (int i=0; i= base_);
if (carry) *i -= base_;
}
if (!carry) return *this;
for (; i != seq_.end(); ++i)
if (++*i == base_) *i = 0; else return *this;
seq_.push_back(1);
return *this;
}
integer& integer::subtract(const integer& x)
{
assert(!abs_less(x));
It i = seq_.begin();
bool carry = false;
for (Cit j = x.seq_.begin(); j != x.seq_.end(); ++j, ++i) {
assert(i != seq_.end());
*i += base_ - *j;
if (carry) --*i;
carry = (*i < base_);
if (!carry) *i -= base_;
}
if (carry) {
assert(i != seq_.end());
while (*i == 0) {
*(i++) = base_ - 1;
assert(i != seq_.end());
}
--*i;
}
while (seq_.back() == 0)
if (seq_.size() == 1) {
sign_ = true;
return *this;
} else
seq_.pop_back();
return *this;
}
integer& integer::mult(unsigned int x)
{
assert (!is_zero());
if (x == 0) return *this = 0;
assert(x < base_);
unsigned int carry = 0;
for (It i = seq_.begin(); i != seq_.end(); ++i) {
carry = *i * x + carry;
*i = carry % base_;
carry /= base_;
}
if (carry > 0) seq_.push_back(carry);
return *this;
}
integer& integer::div(const integer& x, integer& r)
{
if (abs_less(x)) {
r = 0;
return *this;
}
// compute sign
r.sign_ = (sign_ && x.sign_ || !sign_ && !x.sign_);
r.seq_.clear();
// align divisor and initialize upper and lower bound for
// binary search for multiplicator
integer d = x;
unsigned int sh = 1;
unsigned int denh = d.seq_.back(); // highest digit of denominator
while (d.seq_.size() < seq_.size()) {
d.seq_.push_front(0);
++sh;
}
if (abs_less(d)) {
d.seq_.pop_front();
--sh;
}
do {
// binary search for multiplicator in suitable range [low,upp)
// there are three cases:
// (a) *this < d
// (b) *this >= d and both have the same size
// (c) *this >= d and *this has one digit more
unsigned int numh; // leading 0, 1, or 2 digits of *this
if (abs_less (d))
numh = 0; // case (a)
else {
numh = seq_.back(); // cases (b), (c)
if (d.seq_.size() < seq_.size())
numh = numh * base_ + seq_[seq_.size()-2]; // case (c)
}
unsigned int low = numh / (denh + 1);
unsigned int upp = numh / denh + 1;
if (upp > base_) upp = base_;
unsigned int t;
integer dt;
// Invariant: multiplicator in [low, upp)
do {
t = (low + upp) / 2;
dt = d;
dt.mult(t);
if (abs_less(dt)) upp = t; else low = t;
} while (upp - low > 1);
// subtract multiple of divisor
r.seq_.push_front(low);
if (t != low) {
dt = d;
dt.mult(low);
}
subtract(dt);
// cut off trailing zero in divisor
d.seq_.pop_front();
} while (--sh > 0);
assert (is_normalized());
return *this;
}
bool integer::is_normalized() const
{
return !seq_.empty() && (seq_.size()==1 || seq_[seq_.size()-1] != 0);
}
bool integer::is_zero() const
{
return seq_.size()==1 && seq_[0] == 0;
}
// global operators
// ----------------
bool operator==(const integer& x, const integer& y)
{
return x.sign_ == y.sign_ && x.seq_ == y.seq_;
}
bool operator!=(const integer& x, const integer& y) { return !(x == y); }
bool operator<(const integer& x, const integer& y)
{
if (x.sign_ != y.sign_) return x.sign_ < y.sign_;
if (x.sign_) return x.abs_less(y);
return y.abs_less(x);
}
bool operator<=(const integer& x, const integer& y) { return !(y < x); }
bool operator> (const integer& x, const integer& y) { return y < x; }
bool operator>=(const integer& x, const integer& y) { return !(x < y); }
integer operator+(const integer& x, const integer& y)
{
integer z = x;
z += y;
return z;
}
integer operator-(const integer& x, const integer& y)
{
integer z = x;
z -= y;
return z;
}
integer operator*(const integer& x, const integer& y)
{
integer z = x;
z *= y;
return z;
}
integer operator/(const integer& x, const integer& y)
{
integer z = x;
z /= y;
return z;
}
integer operator%(const integer& x, const integer& y)
{
integer z = x;
z %= y;
return z;
}
std::ostream& operator<<(std::ostream& o, const integer& x)
{
if (!x.sign_) o << "-";
bool leading_zeros = true; // need to skip them
for (integer::Crit i = x.seq_.rbegin(); i != x.seq_.rend(); ++i) {
std::deque decimal_digits;
unsigned int decimal_number = *i;
for (unsigned int j=0; j>(std::istream& i, integer& x)
{
const char zero = '0';
char c;
for (;;) {
c = i.peek();
if (std::isspace(c))
i.get();
else
break; // all whitespaces eaten
}
// check for sign
bool negative = false;
if (c == '+' || c == '-') {
negative = (c == '-');
i.get();
c = i.peek();
}
// now c is the first digit; we collect the digits
// in bunchs of integer::power_ many
if (std::isdigit(c)) {
x = 0;
unsigned int y = 0;
unsigned int read = 0;
unsigned int ten_to_read = 1;
do {
y = 10 * y + (c-zero);
i.get();
++read;
ten_to_read *= 10;
if (read == integer::power_) {
x.leftshift(1);
x.seq_[0] = y;
y = 0;
read = 0; ten_to_read = 1;
}
c = i.peek();
} while (std::isdigit(c));
// handle remaining y
if (read > 0)
x = ten_to_read * x + y;
if (negative) x = -x;
}
return i;
}
} // namespace math
