Divisione intera più veloce quando è noto il denominatore?

Question

Sto lavorando su un dispositivo GPU che ha una latenza di interi di divisione molto elevata, diverse centinaia di cicli. Sto cercando di ottimizzare le divisioni.

Tutte le divisioni per denominatore che è in un set {1,3,6,10}, tuttavia il numeratore è un valore positivo di runtime, approssimativamente 32000 o meno. a causa di vincoli di memoria, la tabella di ricerca potrebbe non essere una buona opzione.

Riesci a pensare a alternative? Ho pensato di calcolare invers float point e di usare quelli per moltiplicare il numeratore.

Grazie

PS. grazie gente il bit shift hack è davvero fantastico. per recuperare da arrotondamento, uso seguente segmento C:

sistemi

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

puoi creare una tabella di ricerca per i denominatori? dal momento che hai detto 15 numeratori bit, è possibile utilizzare 17 per gli spostamenti se tutto è senza segno a 32 bit:

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

Più grande è il turno di meno l'errore di arrotondamento. Puoi fare un controllo della forza bruta per vedere quante volte, se ce ne sono, questo è veramente sbagliato.

Answer 2

La norma incorporato hack per questo è di convertire una divisione intera da N in un punto fisso moltiplicazione per 1/N.

Supponendo 16 bit, 0,33333 può essere rappresentato come 21845 (decimale). Moltiplicare, dare un prodotto intero a 32 bit e spostare verso il basso 16 bit.

Quasi certamente si verificherà un errore di arrotondamento (troncamento). Questo può o non può essere qualcosa con cui puoi vivere.

Potrebbe essere utile valutare attentamente la GPU e verificare se è possibile eseguire manualmente una routine di divisione integer più rapida, sfruttando la propria conoscenza della gamma limitata del numeratore.

Answer 3

Il libro, "Hacker's Delight" by Henry Warren, ha un intero capitolo dedicato alla divisione di interi mediante costanti, comprese le tecniche che trasformano una divisione intera in una serie di operazioni di moltiplicazione/spostamento/aggiunta.

Questa pagina calcola i numeri magici per la moltiplicazione/SHIFT/ADD operazioni:

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