gamesmathematical programsotherabout author

Big numbers library

ru

Sometimes we need to have a deal with big numbers where standard types int and int64 are too small for operations. For example we need to calculate 100!=1*2*...*99*100 Bignumber C++ library deals with exact operations with numbers. There are two number classes. For unsigned integers BigUnsigned and for signed integers BigInteger. Inner representation of numbers is hexadecimal. Class BigNumberException is used for exceptions. There is additional template class Fraction for rational numbers implementation. The example counts sums of power of natural numbers. For example, S2(n) = 12+22+...+n2 = n3/3+n2/2+n/6. Si(n) is polynomial of n with rational coefficients which are counted. Also program counts Bernoulli numbers which are rational numbers.

download source codesource code on github

Big numbers (BigUnsigned and BigInteger classes)
creation
string conversion, output
operations
additional functions
exceptions
Rational number (class Fraction)
creation
string conversion, output
operations
additional functions
exceptions

Creation

Creation of bignumbers is possible from int types, decimal or hexadecimal strings, which can include separator symbols ','. If string starts with 0x prefix then it's hexadecimal string otherwise it's decimal string.

BigUnsigned bu("+0x1234f");
cout << bu << endl; //74575

bu = "1234";
bu.print("\n"); //1234

bu = uint64_t(-1);
cout << bu.toDecString(6) << endl; //18,446744,073709,551615

try {
  bu = -1;
} catch (const BigNumberException &e) {
  cerr << e.what() << endl; //..\src\BigUnsigned.h:141 operator= [negative value]
}

BigInteger bi;
bi = "-0xab,cd,ef,ab,cd,ef"; // bi="-0xabcdefabcdef"
cout << bi << " " << bi.to0xHexString() << endl; //-188900977659375 -0xabcdefabcdef

bi = INT_MIN;
cout << bi << " " << bi.toHexString() << endl; //-2147483648 -80000000

try {
  bi = "2345af";
} catch (const BigNumberException &e) {
  cerr << e << endl; //..\src\BigUnsigned.cpp:547 prepareString [invalid symbol in decimal string]
}

String conversion, output

Functions toDecString() or toString() convert big integers to decimal string, toHexString() and to0xHexString() convert numbers to hex strings. One can use number of positions and separator symbol in functions. By default separator is not used. If only number of positions is set then default separator is ','. For output it's possible to use print() function

BigUnsigned bu = "0x123456789abcdef";
//81 985 529 216 486 895 123.456789.abcdef
cout << bu.toDecString(3, ' ') << " " << bu.toHexString(6, '.') << endl;

BigInteger bi = "-0x123456789abcdef";
cout << bi.to0xHexString(6) << endl; //-0x123,456789,abcdef

bi.print("\n"); //-81985529216486895

printf("%s\n",bi.toHexString().c_str()); //-123456789abcdef

Operations

All standard operators addition, subtraction, multiplication, division, remainder and comparison are overloaded. There is div() function which found quotient and remainder at the same time.

BigUnsigned q, r;
int divisor = 80;
BigUnsigned bu = 100;
bu = bu + 200;
bu += "0xff";
bu -= std::string("255");
bu = bu * uint64_t(3); //bu=900
bu.div(divisor, q, r); //q=bu/divisor r=bu%divisor
cout << bu << "=" << divisor << "*" << q << "+" << r << endl; //900=80*11+20

BigInteger bi("-345");
cout << (bi <= 0xff) << (bi >= "-1") << (bi == 345) << endl; //100
cout << bi % 44 << " " << bi / 28 << endl; //-37 -12

Additional functions

//Factorial(), binomial coefficient binomial() and power pow() functions.
BigUnsigned bu = 10;
cout << bu.factorial() << " " << BigUnsigned::factorial(5) << endl; //3628800 120

BigInteger bi = 0;
cout << bi.factorial() << " " << BigInteger::factorial(6) << endl; //1 720

bu = BigUnsigned::binomial(10, 20);
cout << bu << endl; //184756

bi = BigInteger::binomial(13, 26);
cout << bi << endl; //10400600

bu = 2;
cout << bu.pow(16) << " " << BigUnsigned::pow(16, 2) << endl; //65536 256

bi = -3;
cout << bi.pow(3) << " " << BigInteger::pow(-5, 3) << endl; //-27 -125

//Conversion to double and long double, mantissa, exponent.
BigUnsigned bu = BigUnsigned::factorial(20);
std::pair<double, int> p = bu.getMantissaExponent();
int i;
double v = 1;
for (i = 2; i <= 20; i++) {
  v *= i;
}
printf("%.2le\n", v);
printf("%lfe%+d\n", p.first, p.second);

BigInteger bi = 123;
v = bi.toDouble();
p = bi.getMantissaExponent();
printf("%le\n", v);
printf("%lfe%+d\n", p.first, p.second);

BigUnsigned bu = BigUnsigned::factorial(200);
auto v = bu.toDouble();
auto vl = bu.toLongDouble();
cout << v << " " << vl << endl; //inf 7.88658e+374
auto p = bu.getMantissaExponentLongDouble();
cout << p.first << " " << p.second << endl; //7.88658 374

//Conversion to uint64_t only BigUnsigned class.
BigUnsigned bu = BigUnsigned::factorial(20);
auto v = bu.toUint64_t();
cout << v << endl; //2432902008176640000

/* Functions hexToDecString() and decToHexString() convert hexadecimal to decimal string and
vice versa. This functions have two additional parameters: number of positions and separator
symbol. This parameters are the same with string conversion functions.*/
cout << BigUnsigned::decToHexString("123456789", 2, '.') << endl; //7.5b.cd.15
cout << BigUnsigned::hexToDecString("0xaaa") << endl; //2730

cout << BigInteger::decToHexString("65535") << endl; //ffff
cout << BigInteger::hexToDecString("0xffff,ffff", 6) << endl; //4294,967295

//Shift operators >> and <<
BigUnsigned bu = 1;
bu <<= 32;
cout << bu.to0xHexString() << endl; //0x100000000

BigInteger bi = bu;
bi >>= 16;
cout << bi << endl; //65536

//Bitwise operators & | ^ ~
BigUnsigned bu = 0x1a3c;
cout << (bu & 0x53bc).toHexString() << " " << (bu | 0x53bc).toHexString()
    << endl; //123c 5bbc
cout << (~bu).toHexString() << " " << (bu ^ 0x53bc).toHexString() << endl; //ffffe5c3 4980

//Absolute value abs(), getUnsigned() (only BigInteger class)
BigInteger bi = -0xadb;
cout << bi.abs() << " " << bi.getUnsigned() << endl; //2779 2779

Exceptions

Sometime exceptions can appear.

try {
  BigUnsigned bu = "0xadbg";
} catch (BigNumberException const &e) {
  cerr << e << endl; //..\src\BigUnsigned.cpp:547 prepareString [invalid symbol in hex string]
}

try {
  BigUnsigned bu = 0xadb;
  bu = bu - 0xfff;
} catch (BigNumberException const &e) {
  //..\src\BigUnsigned.cpp:230 operator- [try to subtract bigger number]
  fprintf(stderr, "%s", e.what());
}

Fraction creation

Fraction is template class which presents rational numbers. One can use unsigned types uint64_t or BigUnsigned as template parameter.

Fraction < uint64_t > e(2, 3);
cout << e << endl; //2/3

Fraction < uint64_t > f(2); //2/1
cout << f << endl; //2

Fraction < BigUnsigned > g(128, -16); //128/-16
cout << g << endl; //-8

Fraction < BigUnsigned > h("0xffffff", "28");
cout << h << endl; //2396745/4

String conversion, output fractions

Function toString() converts fraction to decimal string. It's possible to set number of positions and separator symbol. String isn't separated by default. If only number of positions is set then symbol ',' is used as default separator. For output one can use print() function. There is helper function specialString(), which is used for formulas and latex output.

Fraction < uint64_t > f("0xfffffffffff", "-56795365");
cout << f.toString(6) << endl; //-3,518437,208883/11,359073
cout << f.toString(4, '.') << endl; //-3.5184.3720.8883/1135.9073

f.print("\n"); //-3518437208883/11359073

cout << f.specialString(false) << endl; //-3518437208883/11359073
cout << f.specialString(true, 3, ' ') << endl; //-\frac{3 518 437 208 883}{11 359 073}

Fraction operations

Addition, subtraction, multiplication, division and comparison operators are overloaded.

typedef Fraction<BigUnsigned> Frac;
Frac f(1, 2);
f -= Frac(1, 6);
cout << f << endl; //1/3
f /= Frac(10, 8);
cout << f << endl; //4/15

cout << (f <= 0) << endl; //0

Additional fraction functions

Function init() creates fraction. Function normilize() makes irreducible fraction. Function gcd() returns the greatest common divisor.

typedef Fraction<BigUnsigned> Frac;
Frac f;
f.init(false, 2, 7);
cout << f << endl; //-2/7
f.init(true, 2, 8);
cout << f << endl; //1/4

f.dividend = 100;
f.divider = 35;
cout << f << endl; //100/35
f.normilize();
cout << f << endl; //20/7

cout << Frac::gcd(35, 100) << endl; //5

Fraction exceptions

Sometimes exceptions can appear when one deal with fractions. For exceptions the same class BigNumberException is used.

typedef Fraction<BigUnsigned> Frac;

try {
  Frac f(1, 0); //1/0
} catch (BigNumberException const &e) {
  cerr << e << endl; //..\src\Fraction.h:52 init [zero division]
}

try {
  Frac f(1);
  f /= Frac(0, 1);
} catch (BigNumberException const &e) {
  cerr << e << endl; //..\src\Fraction.h:52 init [zero division]
}