игрыстатьиматематические программырусский языкразноеоб авторе

Библиотека для работы с большими числами

en

Иногда возникают задачи, где для операций с целыми числами не хватает разрядности стандартных типов int и int64. Например, необходимо посчитать 100!=1*2*...*99*100. Библиотека для работы с большими числами позволяет выполнять точные операции с целыми числами большой разрядности. В ней есть класс для беззнаковых чисел BigUnsigned и чисел со знаком BigInteger. Внутреннее представление чисел класса шестнадцатеричное. Также для исключений используется класс BigNumberException. Для представления дробей (рациональных чисел) используется шаблонный класс Fraction. В примере вычисляются суммы степеней натуральных чисел. Например, S2(n) = 12+22+...+n2 = n3/3+n2/2+n/6. Si(n) будет полиномом от n с рациональными коэффициентами, которые и вычисляются. Также в программе вычисляются числа Бернулли, являющиеся рациональными числами. Более подробно о Si(n) и числах Бернулли можно прочитать здесь

скачать исходный код исходный код на github

Большие числа (классы BigUnsigned и BigInteger)
создание
преобразование в строку, вывод
операции
дополнительные функции
исключения
Дроби (класс Fraction)
создание
преобразование в строку, вывод
операции
дополнительные функции
исключения

Создание

Создание возможно из целых чисел, а также из строк десятичных или шестнадцатеричных, в которых могут присутствовать разделители ',', которые игнорируются. Если строка начинается с префикса 0x то она считается шестнадцатеричной, иначе десятичной.

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

Преобразование в строку, вывод

Для преобразования в десятичную строку используется функция toDecString() или toString(), для шестнадцатеричных строк toHexString() и to0xHexString(). В каждой из этих функций можно задать число позиций для вывода и символ разделитель. По умолчанию строка при выводе не разделяется, если же задано только число позиций, то символ разделитель по умолчанию ','. Для вывода можно использовать функцию print()

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

Операции

Переопределены операторы сложения, вычитания, умножения, деления, взятия остатка, а также операции сравнения. Есть функция div(), которая одновременно находит частное и остаток.

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

Дополнительные функции

//Факториал factorial(), биномиальный коэффициент binomial() и возведение в степень pow().
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

//Преобразование в double и long double, мантисса, показатель степени.
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

//Преобразование в uint64_t только класс BigUnsigned.
BigUnsigned bu = BigUnsigned::factorial(20);
auto v = bu.toUint64_t();
cout << v << endl; //2432902008176640000

/*Преобразование шестнадцатеричной строки в десятичную и наоборот
hexToDecString(), decToHexString(). В этих функциях как и в функциях преобразования
в строку можно использовать число позиций и символ разделитель.*/
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

//Операторы сдвига operator>> и operator<<
BigUnsigned bu = 1;
bu <<= 32;
cout << bu.to0xHexString() << endl; //0x100000000

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

//Побитовые операции & | ^ ~
BigUnsigned bu = 0x1a3c;
cout << (bu & 0x53bc).toHexString() << " " << (bu | 0x53bc).toHexString()
    << endl; //123c 5bbc
cout << (~bu).toHexString() << " " << (bu ^ 0x53bc).toHexString() << endl; //ffffe5c3 4980

//Абсолютное значение abs(), getUnsigned() (только класс BigInteger)
BigInteger bi = -0xadb;
cout<< bi.abs() <<" "<< bi.getUnsigned() <<endl; //2779 2779

Исключения

При выполнении некоторых операций могут возникать исключения.

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 - это шаблон, в качестве параметра которого, можно использовать беззнаковые типы uint64_t или BigUnsigned.

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

Преобразование в строку, вывод дробей

Для преобразования в десятичную строку используется функция toString(), в которой можно задать число позиций для вывода и символ разделитель. По умолчанию строка при выводе не разделяется, если же задано только число позиций, то символ разделитель по умолчанию ','. Для вывода можно использовать функцию print(). Также есть вспомогательная функция specialString(), которая используется для вывода формул в строковом виде и в виде latex.

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}

Операции с дробями

Переопределены операторы сложения, вычитания, умножения, деления, а также операции сравнения.

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

Дополнительные функции с дробями

Функция init() используется для создания дроби. Функция normilize() для приведения дроби к несократимой. Функция gcd() для поиска наибольшего общего делителя.

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

Исключения при работе с дробями

Как и при работе с большими числами, при операциях с дробями могут возникать исключения, для которых используется тот же класс BigNumberException.

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