Оптимизации Отдела по Unknown знаменателя без использования Division Оператора

Question

Я пытаюсь написать функцию C, которая выполняет следующие вычисления во время выполнения:

Числителя/Знаменатель

где:

числителя предшествующего расчет результат, всегда положительна, и больше, чем Знаменатель

и

знаменателе s что (1 < = знаменатель < = 64).

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

Любая помощь?

Answer 1

Вот одна идея, которая использует одно умножение и одну смену, поэтому она будет быстрее, чем разделение на большинстве систем. Так как ваши числители превышают 768 000 000 ~ = 30 бит, у нас не осталось много места в 32-битном слове, поэтому нам придется использовать 64-битное умножение.

Основная идея заключается в том, чтобы воспользоваться тем, что:

x/y == (x * k)/(y * k) 

и делением на степени 2 является простым, быстрым сдвигом бит.

Так что, чтобы выбрать конкретный пример, предположим, что x = 700,000,000 и y = 47 (так что правильный коэффициент составляет 14 893 617). Чтобы избежать ошибок округления, наш сдвиг должен быть примерно размером с нашим самым большим возможным числителем - 30 бит. Найдите значение k, что дает максимальное приближение к y * k = 2^30, что в данном случае равно k = 22845571. Затем x * k = 0x38D08C4CE6F500. Сдвиг этого на 30 бит дает 0xE34231 = 14,893,617, наш ожидаемый коэффициент. Возможно, вам понадобится добавить еще 1-2 бита для некоторых комбинаций числителя/знаменателя для целей округления, если только вы не выбрали значение 1 в вашем частном.

Упражнение затем создает таблицу поиска с соответствующими умножителями для каждого из возможных знаменателей.

EDIT: как указано в комментарии ниже, выбор k = (2^30 + y - 1)/y должен давать лучшие и более последовательные результаты, чем просто k = round(2^30/y).

Answer 2

Большой стол @ss будет работать для малых чисел:

unsigned int divTable[kMaxNumerator][64] = {...} 

Где вы положили значения каждого возможного разрыва там. Не очень практично выше определенных размеров, но он работает для скрытых случаев и был распространенным решением для отображения текстур назад в тот же день :) Затем я прочитал ваши комментарии и увидел, что вы в диапазоне 768 000 000, и это потому, что совершенно непрактично, если только вы можете справиться с довольно высокой точностью.