¿División de enteros más rápida cuando se conoce el denominador?

Question

Estoy trabajando en un dispositivo GPU que tiene latencia de enteros de división muy alta, varios cientos de ciclos. Estoy buscando optimizar divisiones.

Todas las divisiones por denominador que están en un conjunto {1,3,6,10}, sin embargo el numerador es un valor positivo en tiempo de ejecución, aproximadamente 32000 o menos. debido a restricciones de memoria, la tabla de búsqueda puede no ser una buena opción.

¿Puedes pensar en alternativas? He pensado en calcular las inversas del punto flotante y usarlas para multiplicar el numerador.

Gracias

PS. gracias a la gente hackear cambio de bit es realmente genial. para recuperarse de redondeo, lo uso siguiente segmento C:

sistemas

// 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 

¿Puedes construir una tabla de búsqueda para los denominadores? ya que dijo numeradores 15 bits, puede utilizar 17 para los turnos si todo está sin signo de 32 bits:

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

Cuanto mayor sea el cambio de menor será el error de redondeo. Puede hacer un control de fuerza bruta para ver cuántas veces, si es que hay alguna, esto es realmente incorrecto.

Answer 2

El estándar incrustado corte para esto es para convertir una división entera por N en una multiplicación de punto fijo por 1/N.

Suponiendo 16 bits, 0.33333 se puede representar como 21845 (decimal). Multiplica, dando un producto entero de 32 bits, y bajando 16 bits.

Es casi seguro que encontrará algún error de redondeo (truncamiento). Esto puede o no ser algo con lo que puedas vivir.

PODRÍA merecer la pena observar detenidamente su GPU y ver si puede codificar manualmente una rutina de división de enteros más rápida, aprovechando su conocimiento del rango restringido del numerador.

Answer 3

, el libro, "Hacker's Delight" by Henry Warren, tiene un capítulo completo dedicado a la división de enteros por constantes, incluidas las técnicas que transforman una división de enteros en una serie de operaciones de multiplicación/desplazamiento/suma.

Esta página calcula los números mágicos para la multiplicación/SHIFT/ADD operaciones:

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