Обзор библиотек для работы с большими числами в C++Обзор библиотек для работы с большими числами в C++

При работе с криптографией или с адресами IPv6 часто возникает потребность в арифметике с очень большими числами. В этой статье рассмотрим, как разные библиотеки C/C++ выполняют эту функцию на примере перемножения двух больших чисел и расскажем о ещё одном предложении рабочей группы.

Российская рабочая группа по стандартизации C++ разрабатывает предложения по улучшению работы с языком и выносит их на обсуждении Международного комитета по стандартизации. Уже шесть внесенных рабочей группой предложений приняты и будут внесены в стандарт, ещё 12 находятся на рассмотрении.

OpenSSL

В OpenSSL есть встроенный механизм работы с большими числами. Возвести большое число в квадрат можно так:

#include <climits>
#include <openssl/bn.h>
#include <stdio.h>

int main() {
BN_CTX *ctx = BN_CTX_new(); // контекст для вычислений
BIGNUM *mybignum = nullptr; // число, которое будем умножать
BIGNUM *mul = BN_new(); // результат умножения

BN_dec2bn(&mybignum, «18446744073709551615»); // 2^64-1
BN_mul(mul, mybignum, mybignum, ctx);

// распечатаем результат
char *dec = BN_bn2dec(mul);
if (dec) {
printf(«%sn», dec);
OPENSSL_free(dec);
}

// освободим выделенную память
BN_free(mybignum);
BN_free(mul);
}

Это скорее код на C, а не на C++. От этого работать с ним в среде с исключениями — небезопасно, и грозит утечками памяти.

Gcrypt

Библиотека libgcrypt родилась из проекта GnuPG и предоставляет базовые функции для работы с шифрованием, а в том числе и с большими числами. С этой библиотекой наш пример выглядел бы вот так:

#include <gcrypt.h>
#include <cassert>

int main() {
unsigned long long mybignum = 18446744073709551615ull; // 2^64-1
gcry_mpi_t max_ul = gcry_mpi_new(64); // представление mybignum в формате gcrypt
gcry_mpi_t mul = gcry_mpi_new(128); // результат умножения

// переводим mybignum в формат gcrypt
size_t scanned = 0;
gcry_mpi_scan(&max_ul, GCRYMPI_FMT_USG, &mybignum, sizeof(unsigned long long), &scanned);
assert(scanned==sizeof(unsigned long long) && «failed to scan the whole number»);

// умножаем
gcry_mpi_mul(mul, max_ul, max_ul);
// выводим на экран
gcry_mpi_dump(mul);

// освобождаем ресурсы
gcry_mpi_release(mul);
gcry_mpi_release(max_ul);
}

Проблемы всё те же — мы получаем код на C, в котором самому нужно следить за ресурсами.

GMP

Предыдущие две библиотеки были заточены на использование в криптографии. GMP — специализированная библиотека, работающая только с числами. С её помощью возведение в квадрат можно было бы сделать так:

#include <stdio.h>
#include <gmp.h>

int main() {
mpz_t mybignum;
mpz_t mul;

mpz_init_set_str(mybignum, «18446744073709551615», 10);
mpz_init(mul);

mpz_mul(mul, mybignum, mybignum);
gmp_printf(«%Zdn», mul);

// освобождаем память
mpz_clear(mybignum);
mpz_clear(mul);
}

Выглядит уже лучше и понятнее, но это всё ещё код на C.

Boost.Multiprecision

Эта библиотека не реализует арифметику с большими числами сама, а лишь предоставляет удобный C++ интерфейс для работы с ними, используя сторонние библиотеки в качестве backend для вычислений. Насколько интерфейс удобен — судите сами:

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>

int main() {
using namespace boost::multiprecision;
int128_t mybignum = 18446744073709551615ull;
std::cout << mybignum * mybignum << std::endl;
}
Предложение в стандарт

Использовать сторонние библиотеки для такой часто возникающей задачи затратно как по памяти, так и по производительности. Российские разработчики из Национальной рабочей группы по стандартизации C++ считают так же, поэтому они составили предложение по включению целочисленных типов произвольной ширины в стандартную библиотеку. В нашем случае пример выглядел бы так:

#include <wide_integer>
#include <iostream>

int main() {
auto mybignum = 18446744073709551615_int128;
std::cout << mybignum * mybignum << std::endl;
}

Хотите работать с числами, занимающими мегабайт памяти? Не проблема, вот так например можно подсчитать 100! :

#include <wide_integer>
#include <iostream>

using int_mb = std::wide_int<1024*1024>;

int main() {
int_mb factorial_100 = 1;
for (unsigned i = 2 ; i <= 100; ++i)
factorial_100 *= i;
std::cout << «100! is » << factorial_100 << std::endl;
}

Возможно, мы увидим это предложение в стандартной библиотеке уже в C++23. Прототип доступен по этой ссылке , а самые любопытные могут всегда прочесть самый свежий текст предложения здесь.

Игорь Клевенец, разработчик Яндекса

Антон Полухин, разработчик Яндекс.Такси


Читайте также:

Добавить комментарий

Войти с помощью: