Более быстрое целочисленное деление, когда знаменатель известен?

Я работаю над устройством GPU с очень высокой задержкой целочисленного деления, несколькими сотнями циклов. Я ищу оптимизацию разделов.

Все деления на знаменатель, который находится в наборе {1,3,6,10}, однако числитель - это положительное значение времени выполнения, примерно 32000 или меньше. из-за ограничений памяти, таблица поиска может не быть хорошим вариантом.

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

Спасибо

PS. спасибо людям. бит-сдвиг взлома - это действительно здорово. для восстановления после округления, я использую следующий сегмент C:

// q = m/n
q += (n*(j +1)-1) < m;

Ответ 1

a/b=a*(1/b)
x=(1<<16)/b
a/b=(a*x)>>16

Вы можете создать таблицу поиска для знаменателей? так как вы сказали, что 15-битные числители, вы можете использовать 17 для сдвигов, если все без знака 32 бит:

a/b=a*((1<<17)/b)>>17

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

Ответ 2

Стандартными взломами встроенных систем для этого является преобразование целочисленного деления на N в умножение на фиксированную точку на 1/N.

Предполагая, что 16 бит, 0.33333 можно представить как 21845 (десятичный). Умножьте, предоставив 32-битное целочисленное произведение и сдвиньте 16 бит.

Вы почти наверняка столкнетесь с некоторой ошибкой округления (усечения). Это может быть или не быть чем-то, с чем вы можете жить.

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

Ответ 3

В книге "Хакерский восторг" Генри Уоррена имеется целая глава, посвященная целочисленному делению по константам, включая методы, которые преобразуют целое число деление на операцию умножения/сдвига/добавления.

Эта страница вычисляет магические числа для операций умножения/сдвига/добавления:

http://www.hackersdelight.org/magic.htm