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

Question

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

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

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

Спасибо

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

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

Answer 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

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

Answer 2

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

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

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

Answer 3

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

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

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

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