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 code

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";
  cout<<bu.toDecString(3,' ')<<" "<<bu.toHexString(6,'.')<<endl;//81 985 529 216 486 895 123.456789.abcdef

  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() 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=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

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){
    fprintf(stderr,"%s",e.what());//..\src\BigUnsigned.cpp:230 operator- [try to subtract bigger number]
  }

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]
  }