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

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

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

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

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

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

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

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


algorithm floating-point math simd language-agnostic
person caffiend    schedule 16.03.2010    source источник
comment
Можно вычислить любой модуль степени двойки без деления; Вы уверены, что задаете вопрос, который намереваетесь задать? Я полагаю, что вы на самом деле ищете расчеты модов 2^7 - 1 и 2^31 - 1.   -  person Stephen Canon    schedule 16.03.2010
comment
2 ^ 7 и 2 ^ 31 не являются простыми числами. Не могли бы вы перефразировать свой вопрос более точно?   -  person Paul R    schedule 16.03.2010
comment
На какие наборы инструкций вы ориентируетесь?   -  person user287792    schedule 17.03.2010
comment
Да, значения x и y должны быть целыми. Во-первых, я хочу ориентироваться на векторные встроенные функции в Windows (у них есть целочисленная поддержка, но она медленная). В конце концов я перешел на графику ATI (CTM API), которая поддерживает только 16-битную/32-битную FP.   -  person caffiend    schedule 18.03.2010

Ответы (1)


arrow_upward
1
arrow_downward

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

person user287792    schedule 24.03.2010
comment
контрольная сумма, которую я имел в виду, заключалась в том, чтобы просто сложить числа и взять модуль результата за простое число. Я все еще немного смущен вашим ответом. X - текущая контрольная сумма, y - число, которое я добавляю... оба в диапазоне целых чисел 0... 2**31. Даже если у меня есть округление, как мне вычислить модуль? - person caffiend; 02.05.2010