Быстрый, векторизуемый метод взятия модуля чисел с плавающей запятой специальных простых чисел?

Question

Существует ли быстрый метод определения модуля числа с плавающей запятой?

С целыми числами есть приемы для простых чисел Мерсенна, так что можно вычислить y = x MOD 2 ^ 31-1 без необходимости деления. целочисленный трюк

Можно ли применять подобные трюки к числам с плавающей запятой?

Предпочтительно таким образом, чтобы его можно было преобразовать в векторные / SIMD-операции или переместить в код GPGPU. Это исключает использование целочисленных вычислений для данных с плавающей запятой.

Простые числа, которые меня интересуют, будут 2 ^ 7-1 и 2 ^ 31-1, хотя, если есть более эффективные для чисел с плавающей запятой, они будут приветствоваться.

Одним из предполагаемых применений этого алгоритма было бы вычисление текущей «контрольной суммы» входных чисел с плавающей запятой при их считывании в алгоритм. Чтобы не тратить слишком много времени на вычисления, я бы хотел сохранить этот вес.

По-видимому, аналогичная техника используется для больших чисел, особенно 2 ^ 127 - 1. К сожалению, математика в статье мне не подходит, и я не смог понять, как преобразовать ее в меньшие простые числа. 1015 * Пример с плавающей точкой MOD 2 ^ 127 - 1 - HASH127

Answer 1

Я посмотрел на бумагу djb, и вам стало проще, поскольку 31 бит удобно вписывается в 53-битную точность с двойным значением. Предполагая, что ваша контрольная сумма состоит из некоторых кольцевых операций над Z / (2 ** 31 - 1), будет проще (и быстрее) решить упрощенную задачу вычисления небольшого представителя x mod Z / (2 ** 31 - 1); в конце вы можете использовать целочисленную арифметику, чтобы найти каноническую, которая медленная, но не должна происходить слишком часто.

Основной шаг сокращения состоит в замене целого числа x = y + 2 ** 31 * z на y + z. Уловка, которую использует djb, состоит в том, чтобы вычислить w = (x + L) - L, где L - большое целое число, тщательно выбранное, чтобы вызвать округление таким образом, чтобы z = 2 ** - 31 * w. Затем вычислите y = x - w и выведите y + z, который будет иметь величину не более 2 ** 32. (Я извиняюсь, если этой операции недостаточно, если да, пожалуйста, опубликуйте свой алгоритм контрольной суммы.)

Выбор L включает знание того, насколько точным является значение. Для модуля 2 ** 31 - 1 мы хотим, чтобы единица наименьшей точности (ulp) была 2 ** 31. Для пар в диапазоне [1.0, 2.0) ulp составляет 2 ** - 52, поэтому L должно быть 2 ** 52 * 2 ** 31. Если бы вы делали это с модулем 2 ** 7 - 1, то вы бы взяли L = 2 ** 52 * 2 ** 7. Как отмечает djb, этот трюк в решающей степени зависит от промежуточных результатов , а не , которые вычисляются с более высокой точностью.