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

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

  • Статьи,
Обложка поста
Eucalyp Studio; Howcolour

При работе с криптографией или с адресами 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("%s\n", 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("%Zd\n", 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. Прототип доступен по этой ссылке , а самые любопытные могут всегда прочесть самый свежий текст предложения здесь.

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

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