Как эффективно сложить 3 больших целых числа с помощью GMP

Я хочу сделать x = a + b + c для ~ 2048-битных целых чисел со знаком. В настоящее время мой код выглядит так

mpz_add(x, a, b);
mpz_add(x, x, c);

Есть ли одна функция для этого? Это происходит много раз в моем приложении. Я профилировал свой код, и этап трехэтапного добавления занимает значительную часть времени выполнения. Если есть альтернативный способ сделать это за один проход, это может помочь.


c++ performance bignum gmp
person akashnil    schedule 26.12.2018    source источник
comment
Я не думаю, что подходящая operator+()overload даст что-то существенное в производительности gmp.   -  person πάντα ῥεῖ    schedule 26.12.2018
comment
Да, перегрузка операторов была бы просто синтаксическим сахаром. Я думаю, что лежащий в основе алгоритм может перебирать конечности за один проход по сравнению с двумя проходами.   -  person akashnil    schedule 26.12.2018
comment
Трудно ответить без контекста. Является ли x новой переменной каждый раз или той, которую вы повторно используете в цикле? Все ли числа одинакового размера/знака? И т.д. Я сомневаюсь, что есть много преимуществ от 3-стороннего сумматора, но кто знает... Вы указали профилировщику, какая часть mpz_add требует времени?   -  person Marc Glisse    schedule 26.12.2018
comment
Люди думают, что временные файлы в оценке будут проблемой для C++, но gmpxx хорошо спроектирована для таких выражений и использует современные методы, такие как семантика перемещения.   -  person Brett Hale    schedule 14.03.2019

Ответы (2)


arrow_upward
0
arrow_downward

Я широко использовал MPFR и просмотрел почти все части документации. Я почти уверен, что ничего подобного не существует в MPFR, и поэтому я почти уверен, что ничего подобного нет в GMP.

Одним из решений может быть переход на MPFR и использование MPFR C++ Павла Голобородько, который добавляет операторы для функций МПФР. Я не могу себе представить, что это улучшит производительность (хотя, вероятно, это не сильно повлияет на нее), она находится под лицензией GPL, и вам придется установить другую библиотеку, но она объединит операции.

Я не знаю никаких быстрых алгоритмов, которые при добавлении трех чисел не просто добавляют два из них, а затем добавляют последнее число за кулисами. Я не думаю, что объединение этих двух операций в одну с использованием любой библиотеки на любом языке улучшит производительность. Произвольная точность просто медленная, даже при использовании GNU MP. У меня есть сравнение скоростей здесь на Code Review, если это поможет.

person Byte11    schedule 04.01.2019

arrow_upward
0
arrow_downward

Двойной вызов функций не приведет к заметным накладным расходам. Однако перераспределение x при необходимости может быть очень медленным. Чтобы избежать этого, вы можете измерить размеры a, b и c и убедиться, что x выделил максимальный размер трех чисел плюс 2 (в худшем случае 1 бит для сложения). Вы можете использовать

mpz_init2(x, maxsize+2);

или, если x уже был инициализирован,

if (mpz_sizeinbase(x, 2) < maxsize+2)
  mpz_realloc2(x, maxsize+2);
person luisp    schedule 09.01.2019