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