performance - positivos - multiplicacion y division de numeros enteros wikipedia
¿División de enteros más rápida cuando se conoce el denominador? (3)
Estoy trabajando en un dispositivo GPU que tiene una latencia de enteros de división muy alta, varios cientos de ciclos. Estoy buscando optimizar las divisiones.
Todas las divisiones por denominador que se encuentran 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.
¿Se te ocurren alternativas? He pensado en calcular inversos de punto flotante y usarlos para multiplicar numerador.
Gracias
PD. gracias gente El cambio de bit hack es realmente genial. Para recuperarme del redondeo, uso el siguiente segmento C:
// q = m/n
q += (n*(j +1)-1) < m;
El libro, "Hacker''s Delight" de Henry Warren , tiene un capítulo completo dedicado a la división de enteros por constantes, que incluye técnicas que transforman una división de enteros en una serie de operaciones de multiplicación / desplazamiento / adición.
Esta página calcula los números mágicos para las operaciones de multiplicación / cambio / adición:
El sistema estándar incorporado para esto es 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 baja 16 bits.
Es casi seguro que encontrará algún error de redondeo (truncamiento). Esto puede o no ser algo con lo que puedes vivir.
Puede que valga la pena mirar 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.
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 dijiste numeradores de 15 bits, podrías usar 17 para los turnos si todo está sin firmar 32 bits:
a/b=a*((1<<17)/b)>>17
Cuanto mayor sea el desplazamiento, menor será el error de redondeo. Puede hacer una verificación de fuerza bruta para ver cuántas veces, si es que hay alguna, esto es realmente incorrecto.