Целые числа фиксированного размера с gmp?

Я несколько дней пытался установить библиотеку GMP под MINGW. Я использовал в течение нескольких недель __uint128_t с gcc в 64-битной среде Linux, затем перенес ту же программу в GMP и mingw (32-битная версия). Я использовал mpz_class целых чисел вместо __uint128_t. Затем я начал свою новую программу и...! С __uint128_t и 64-битной версией это занимает 16 минут, с GMP и MINGW - 91 ЧАС!!!

Что мне сделать, чтобы немного ускорить процесс? Есть ли более быстрый способ выполнить 128-битную целочисленную математику в 32-битной среде? Мне не нужно больше 128 бит, так есть ли способ сказать GMP: «Хорошо, мне просто нужно 128 бит, не меняйте точность, но, пожалуйста, ДЕЙСТВУЙТЕ БЫСТРЕЕ»?


c c++ mingw gmp 128-bit
person Matteo Monti    schedule 31.08.2011    source источник
comment
Какие операции вам нужно сделать на 128 бит? (+, -, </>, *, /, что-нибудь поинтереснее?)   -  person osgx    schedule 01.09.2011
comment
64-битная версия изначально поддерживается компилятором. Найдите код, выполняющий 64-битные арифметические операции с использованием 32-разрядных uint, и используйте принципы его реализации для 128-битных uint с использованием 64-битных uint. Это будет не так быстро, как встроенная 128-битная поддержка (которую вы можете получить, например, с помощью SSE), но, вероятно, она будет быстрее, чем libgmp.   -  person user786653    schedule 01.09.2011
comment
64-битная версия может поддерживаться компилятором, но особенно такие вещи, как деление (и по модулю) и умножение, могут быть намного быстрее в реальной 64-битной среде (IOW, 64-битные регистры и многое другое).   -  person Rudy Velthuis    schedule 01.09.2011

Ответы (2)


arrow_upward
3
arrow_downward

Нет, когда вы используете mpz_t, вы не можете ограничить GMP целыми числами с фиксированной длиной. mpz_t — это структура с длиной массива конечностей (выделенных; используемых) и указателем на фактическое значение, которое хранится в виде массива целых чисел (конечностей; массива int32 или int64). GMP готов увеличить длину любого значения, когда оно вырастет до большого.

Вы можете выделить 128 бит для каждого mpz_t при инициализации, используя mpz_init2:

 mpz_init2(mpz_t*, bit_number);

Но ускорение от этого небольшое, есть еще data-indirection и length-handling.

Вы можете использовать конечности напрямую, переключившись на mpn_ низкоуровневые функции:

http://www.gnu.org/software/gmp/manual/html_node/Low-level-Functions.html#Low-level%20Functions

Не будет указателя на конечности (это хорошо для кеша), простого кода ввода/вывода; и нет автоматической обработки размера конечностей (ни автоматического расширения, ни распределения). Вы должны сделать все хранение самостоятельно; может быть даже некоторый перенос должен быть обработан вручную, но будут быстрые операции GMP *, / и %; вы можете реконструировать mpz_t для удобного ввода/вывода с помощью mpz_t t;t._mp_size = t._mp_alloc=limb_number;t._mp_d=pointer_to_limb_array.

Кроме того, вы просто можете использовать uint128_t, если вы переключитесь на 64-битный mingw.

person osgx    schedule 31.08.2011
comment
И использование mpz_init2 и выделение 128 бит сделает его быстрее..? - person Matteo Monti; 01.09.2011
comment
@Matteo, сказал он, но ускорение от этого небольшое. - person Seth Carnegie; 01.09.2011
comment
@Сет (спасибо, но он отредактировал ответ! :D Я его раньше не видел!) - person Matteo Monti; 01.09.2011

arrow_upward
1
arrow_downward

Вместо этого вы можете использовать MinGW-w64, если компьютеры Windows, на которые вы ориентируетесь, достаточно новые для поставки 64-битная Windows (например, Vista или 7).

person michel-slm    schedule 31.08.2011