Самая быстрая 128-битная целочисленная библиотека
Я работаю над приложением для числовых вычислений с большим количеством процессоров. Не вдаваясь во многие детали, это исследовательский проект по вычислительной математике, который включает вычисление определенной функции f(x) для большого целого числа x.
Прямо сейчас все реализовано в C++ в режиме x64 с использованием собственных 64-битных целых. Это ограничивает меня х<2^64~1,8*10^19. Я хочу пойти дальше, для этого мне нужна библиотека, которая выполняет 128-битную арифметику. И это должно быть очень быстро. В частности, целочисленные деления должны быть быстрыми. В противном случае я буду сидеть здесь в ожидании результатов до дня благодарения. И я бы не стал изобретать велосипед.
Я нашел список из ~20 больших целочисленных библиотек в Википедии, но большинство из них, похоже, нацелены на числа с произвольной точностью, что является избыточным для моей задачи, и мне не нужны дополнительные расходы, связанные с этим.
Кто-нибудь знает, какая библиотека может работать на 128-битных целых числах быстрее всего?
3 ответа
Вы не упомянули свои требования к платформе / переносимости. Если вы готовы использовать gcc или же clangна 64-битных платформах они имеют встроенные 128-битные типы, которые предоставляются бесплатно, __uint128_t а также __int128_t, Возможно, другие платформы имеют аналогичные расширения типов.
В любом случае должна быть возможность найти соответствующий общий код в gcc источники, которые собирают два целых числа ширины N синтезировать одно целое число ширины 2N, Это, вероятно, будет хорошей отправной точкой для создания отдельной библиотеки для этой цели.
Это может быть не для всех, но я бы выбрал библиотеку произвольно целых чисел с самой высокой производительностью и исходным кодом, подходящую для работы, и взломал ее для фиксированных целочисленных размеров. Измените некоторую переменную "nbits" на 128 жестко закодированных. Вероятно, он выделяет память во время выполнения, не зная количества байтов до тех пор. Измените его, чтобы использовать struct с данными на месте, сохраняя указатель разыменовывая при каждом чтении данных. Разверните некоторые критические петли вручную. Жесткий код всего, что может быть критичным. Тогда компилятору будет легче оптимизировать вещи. Конечно, большая часть этого будет собираться, используя причудливую SIMD с любой технологией, используемой на этой неделе.
Было бы весело! Но затем, как программист, я начал с машинного кода и очень низкого уровня материала.
Но для тех, кто не такой сумасшедший, как я, возможно, одна из доступных библиотек использует шаблоны или имеет некоторые средства для генерации кода, настраиваемого под определенный размер. И некоторые компиляторы имеют целочисленный тип long long, который может подойти.