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

Question

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

Что я должен сделать, чтобы немного ускорить процесс?Есть ли более быстрый способ сделать 128-битную целочисленную математику в 32-битной среде?Мне не нужно больше, чем 128 бит, поэтому есть ли способ сказать GMP: «Хорошо, мне просто нужно 128 бит, сохраняйте суждение фиксированным, но, пожалуйста, GO FASTER»?

Answer 1

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

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

 mpz_init2(mpz_t*, bit_number);

Но ускорение от этого невелико, все еще существует перенаправление данных и обработка длины.

Вы можете использовать конечности напрямую, переключившись на 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.

Answer 2

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