#ifndef MMAHONEY_H
#define MMAHONEY_H

/* mmahoney.h -- Matt Mahoney, mmahoney@cs.fit.edu

The file defines two types, Integer and Real.  Both types represent
numbers with unlimited range.  In addition, Real may have unlimited
precision.  An Integer is a Real with 0 decimal places of precision.

Both types support arithmetic (+ - * / and unary -), comparison
(== != < > <= >=), assignment (= += -= *= /=), input ( >> ) and
output ( << ).  For expressions that mix types, the lesser type is
promoted to the greater type and the result is that of the greater
type.  From lesser to greater, the types are

  int -> double -> Integer -> Real (lower to higher precision)

An int is implicity converted to Real with 0 decimal places of
precision.  A double is implicitly converted with 20 decimal
places.  The number of places may also be given explicitly
as a second constructor argument.

  Real r(2.5, 4);  // 2.5000
  r / 3            // 0.8333, implicit Real(3, 0)
  r / 3.0          // 0.83333333333333333333, implicit Real(3.0, 20)

Explicit conversion from Real to Integer drops the decimal
points using floor().

  Integer(Real(-3.2))  // -4

Real() and Integer() default to 0 with precision 0.  Arithmetic
combined with assignment follow the same rules as if they were
two separate operations.

  Integer i;        // 0
  Real r;           // 0.
  r += i;           // OK, 0.  same as r = r + i;
  i += r;           // Error
  i += Integer(r);  // OK, 0

Input using >> reads a word delimited by white space and interprets
it as a decimal number up to the first invalid character.  Valid
characters are digits, at most one decimal point (for Real), and a
possible leading - sign.  Output is in the same format.  Input to
a Real does not change its precision.  For example

  Real r(0, 3);
  Integer i;

  Input          cin >> r  cin >> i 
  -----          --------  -------- 
  -12.34         -12.340   -12
  12             12.000    12
  1.23456        1.234     1
  1.2e7          1.200     1
  foo            0.000     0

Real and Integer are printed in decimal format with all decimal
places shown, including trailing zeros, i.e.

  cout << Real(-1.2, 3);  // -1.200
  cout << Real(.1234, 2); // 0.12
  cout << Real(4);        // 4
  cout << Integer(4.8);   // 4

All arithmetic operators are non-member non-friend functions.
A Real is represented as a sequence of digits in some base B, and
a precision, represnting the number of base B digits after the
decimal point.  An Integer is the same except that the precision
is always 0.  The following public members are used to access this
representation.

Real::Base()

  The base, B (a static method, inlined for speed).  Its value is
  fixed, but may be redefined to return any value 2 or higher
  with appropriate changes to Base10() and Digit_t below and to
  the implementation.

Real::Base10()

  The number of base 10 digits represented by one base B digit, or
  0 if B is not a power of 10.

r.prec10(n)

  Set the precision to n base 10 digits after the decimal.  Setting
  n to a smaller value may truncate digits, e.g.

  Real r(2.5, 4);  // 2.5000
  r.prec10(0);     // 2
  r.prec10(6);     // 2.000000

r.prec10()

  Returns n as set above.

r.prec()

  Returns the precision in base B digits.  For example, if B = 100 then

  Real r(2.5, 6);  // 2.500000
  r.base();        // 100
  r.base10();      // 2
  r.prec10();      // 6
  r.prec();        // 3

r.digit(i)

  Returns the i'th digit, where the least significant digit is 0
  and the ones digit is r.prec().  All digits are in the range 0
  to B-1 except the leading digit, which may be negative.  There is
  no restriction on i.

r.size()

  Returns the number of digits.  All digits where i<0 or i>=r.size()
  are 0.  For example

  For example, if B = 10:

  Real r(1.25, 2);  // 1.25
  r.prec()          // 2
  r.size()          // 3
  r.digit(0)        // 5
  r.digit(1)        // 2
  r.digit(2)        // 1   (ones digit)
  r.digit(3)        // 0
  r.digit(-1)       // 0

  A negative number is represented by a negative leading digit, e.g.
  1.25 is {1,2,5} meaning 1 + .2 +.05 but -1.25 is {-2,7,5) meaning
  -2 + .7 + .05.  A Real, r, may be converted to double, d, as follows:

    double d=0;
    for (int i=0; i<r.size(); ++i)
      d += r.digit(i) * pow(r.base(), i-r.prec());

  The leading digit is always 1-B to -1 or 1 to B-1 (never 0).  The
  representation is always as short as possible.  Thus, Real(0.0).size()
  is 0.  The leading digit is never -1 if the next digit is positive,
  e.g. -80 would not be represented as {-1,2,0} (-100 + 20 + 0)
  because the representation {-8,0) is shorter.

Real::Digit_t

  The type returned by r.digit(i).  It is a signed integer type that
  must be able to represent numbers in the range 1-B*B to B*B-1.
  For example, if B is 100000000 then digit_t is long long.

r.add(i, x)

  Add x to the i'th digit of r and then adjust the representation to that
  of a valid Real, equivalent to r += x * pow(r.base(), i-r.prec());
  x may be any number that can be represented by type Digit_t.

To compile:
1. #include "mmahoney.h" in yourfile.cpp
2. g++ yourfile.cpp mmahoney.cpp

*/

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cctype>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class Real {
private:
  typedef long BT;  // Digit type
  vector<BT> v;      // Least significant digit in v[0]
  int pr10;          // prec10(), base 10 precision
  int prb;           // prec(), base B precision
public:
  typedef long long Digit_t; // Integer type that can represent -B*B to B*B-1
  static inline Digit_t base() {return 1000000000;}  // Base B
  static inline int base10() {return 9;}     // log10(base())
  int size() const {return v.size();}        // How many base B digits
  Digit_t digit(int i) const {return i>=0 && i<int(v.size()) ? v[i] : 0;}
  void add(int i, Digit_t x);  // Add x to v[i] and propagate carries
  virtual void prec10(int n);        // Change precision to n decimal digits
  int prec10() const {return pr10;}  // Get n
  int prec() const {return prb;}     // Get precision in base B
  Real(double d=0, int p=20); // Convert from d with precision p decimals
  virtual ~Real() {}
};

class Integer: public Real {
public:
  Integer(double d=0): Real(d, 0) {}
  explicit Integer(const Real& r): Real(r) {Real::prec10(0);}
  void prec10(int n) {Real::prec10(0);}
};

// Subtraction
Real operator - (Real a, const Real& b);
inline Real& operator -= (Real& a, const Real& b) {return a=a-b;}
inline Real operator - (const Real& a) {return Real(0,0)-a;}  // Unary -

// Addition
inline Real operator + (const Real& a, const Real& b) {return a - -b;}
inline Real& operator += (Real& a, const Real& b) {return a=a+b;}

// Multiplication
Real& operator *= (Real& a, const Real& b);
inline Real operator * (Real a, const Real& b) {return a*=b;}

// Comparison
bool operator < (const Real& a, const Real& b);
inline bool operator >  (const Real& a, const Real& b) {return b<a;}
inline bool operator <= (const Real& a, const Real& b) {return !(b<a);}
inline bool operator >= (const Real& a, const Real& b) {return !(a<b);}
inline bool operator != (const Real& a, const Real& b) {return b<a || a<b;}
inline bool operator == (const Real& a, const Real& b) {return !(a!=b);}

// Division
Real operator / (Real a, Real b);
inline Real& operator /= (Real& a, const Real& b) {return a=a/b;}

// Integer arithmetic
inline Integer operator+(const Integer&a, const Integer&b) {
  return Integer(Real(a)+b);}
inline Integer operator-(const Integer&a, const Integer&b) {
  return Integer(Real(a)-b);}
inline Integer operator*(const Integer&a, const Integer&b) {
  return Integer(Real(a)*b);}
inline Integer operator/(const Integer&a, const Integer&b) {
  return Integer(Real(a)/b);}
inline Integer& operator+=(Integer& a, const Integer& b) {return a=a+b;}
inline Integer& operator-=(Integer& a, const Integer& b) {return a=a-b;}
inline Integer& operator*=(Integer& a, const Integer& b) {return a=a*b;}
inline Integer& operator/=(Integer& a, const Integer& b) {return a=a/b;}
inline Integer operator-(const Integer& a) {return Integer(0)-a;}
inline Integer operator%(const Integer& a, const Integer& b) {return a-a/b*b;}
inline Integer& operator%=(Integer& a, const Integer& b) {return a=a%b;}

// Input: accept digits and at most one decimal point and a leading minus
istream& operator >> (istream& in, Real& a);

// Output a Real
ostream& operator << (ostream& out, const Real& a);

#endif