Самая быстрая 128-битная целочисленная библиотека [закрыта]

Я работаю над приложением для численных вычислений с интенсивным использованием процессора. Не вдаваясь в подробности, это исследовательский проект по вычислительной математике, который включает в себя вычисление определенной функции f(x) для большого целого числа x.

Сейчас все реализовано на C++ в режиме x64, с использованием собственных 64-битных целых чисел. Это ограничивает меня до x‹2^64~1,8*10^19. Я хочу пойти дальше, для этого мне нужна библиотека, которая выполняет 128-битные арифметические операции. И это должно быть очень быстро. В частности, целочисленные деления должны быть быстрыми. Иначе я буду сидеть здесь и ждать результатов до Дня Благодарения. И я бы не хотел изобретать велосипед.

Я нашел в Википедии список примерно из 20 больших целочисленных библиотек, но большинство из них, похоже, ориентированы на числа произвольной точности, что является излишним для моей задачи, и мне не нужны дополнительные затраты, связанные с этим.

Кто-нибудь знает, какая библиотека может быстрее всего работать со 128-битными целыми числами?


c c++ biginteger numerical
person Eugene Smith    schedule 11.09.2010    source источник
comment
x86-64.org/pipermail/discuss/2005-August/ 006412.html   -  person Anycorn    schedule 12.09.2010
comment
Вот интересно, не знал такого. Сейчас я работаю в Windows, но попробую с gcc в Unix. Мой код должен быть достаточно переносимым.   -  person Eugene Smith    schedule 12.09.2010
comment
Вы можете использовать Cygwin/GCC или MinGW.   -  person alternative    schedule 12.09.2010
comment
Библиотеки, как правило, строятся так, чтобы охватывать общий случай, а не частный случай, если только частный случай не является достаточно распространенным на практике. Так что, я думаю, если вы считаете, что произвольная точность — это излишество, вам, вероятно, придется использовать свою собственную для 128-битных значений. Это не слишком сложно.   -  person MAK    schedule 12.09.2010

Ответы (3)


arrow_upward
16
arrow_downward

Вы не упомянули свои требования к платформе/переносимости. Если вы хотите использовать gcc или clang, на 64-битных платформах у них есть встроенные 128-битные типы, которые предоставляются бесплатно, __uint128_t и __int128_t. Возможно, другие платформы имеют аналогичные расширения типов.

В любом случае должна быть возможность найти соответствующий общий код в gcc источниках, который собирает два целых числа ширины N для синтеза одного целого числа ширины 2N. Это, вероятно, было бы хорошей отправной точкой для создания отдельной библиотеки для этой цели.

person Jens Gustedt    schedule 11.09.2010

arrow_upward
5
arrow_downward

Библиотека ttmath делает то, что вам нужно.

person rafak    schedule 15.09.2010

arrow_upward
1
arrow_downward

Это может быть не для всех, но я бы выбрал самую высокопроизводительную библиотеку произвольных целых чисел с исходным кодом и в остальном подходящую для работы, и взломал бы ее для фиксированных целочисленных размеров. Измените некоторую переменную «nbits» на 128 жестко закодированных. Вероятно, он выделяет память во время выполнения, не зная до этого количества байтов. Измените его, чтобы использовать структуру с данными на месте, сохраняя разыменование указателя при каждом чтении данных. Разверните определенные критические циклы вручную. Жестко запрограммируйте все остальное, что может быть критическим. Тогда компилятору, вероятно, будет легче оптимизировать вещи. Конечно, большая часть этого будет сборкой с использованием причудливой SIMD с любой технологией, которая будет использоваться на этой неделе.

Было бы весело! Но затем, как программист, я начал с машинного кода и очень низкоуровневых вещей.

Но для тех, кто не настолько сумасшедший, как я, возможно, одна из доступных библиотек использует шаблоны или имеет какие-то средства для создания пользовательского кода определенного размера. И некоторые компиляторы имеют целочисленный тип "long long", который может быть подходящим.

person DarenW    schedule 14.09.2010