Acelerando el rendimiento del bucle que realiza la operación de módulo largo sin firma.

Question

Necesito realizar muchas operaciones de encontrar restos del número de División GeneracDicetAtGode por el módulo de 16 bits:

unsigned long long largeNumber;
long residues[100];
unsigned long modules[100];
intiModules(modules); //set different 16-bit values

for(int i = 0; i < 100; i++){
     residues[i] = largeNumber % modules[i];
}

¿Cómo puedo acelerar este bucle?

El recuento de iteración no es grande (32-128), pero este bucle se realiza muy a menudo, por lo que su velocidad es crítica.

Answer 1

La división

por una constante (y solo hay 65536 de ellos) se puede realizar mediante multiplicación del recíproco, seguido / precedido por algún ajuste fino.Dado que este método es preciso para un rango limitado, se puede usar algunas técnicas para reducir el operando de 64 bits a un valor mucho más pequeño (que aún es congruente con el valor original):

// pseudo code -- not c
a = 0x1234567890abcdefULL;
a = 0x1234 << 48 + 0x5678 << 32 + 0x90ab << 16 + 0xcdef;

a % N === ((0x1234 * (2^48 % N) +     // === means 'is congruent'
           (0x5678 * (2^32 % N)) +    // ^ means exponentation
           (0x90ab * (2^16 % N)) + 
           (0xcdef * 1)) % N;

El valor intermedio se puede calcular solo con (pequeñas) multiplicaciones solo y el resto final (% N) tiene potencial para calcularse con la multiplicación recíproca.

Answer 2

If speed is critical, according to this answer about branch prediction and this one, loop unrolling may be of help, avoiding the test induced by the for instruction, reducing the number of tests and improving "branch prediction".

The gain (or none, some compilers do that optimization for you) varies based on architecture / compiler.

On my machine, changing the loop while preserving the number of operations from

for(int i = 0; i < 500000000; i++){
    residues[i % 100] = largeNumber % modules[i % 100];
}

to

for(int i = 0; i < 500000000; i+=5){
    residues[(i+0) % 100] = largeNumber % modules[(i+0) % 100];
    residues[(i+1) % 100] = largeNumber % modules[(i+1) % 100];
    residues[(i+2) % 100] = largeNumber % modules[(i+2) % 100];
    residues[(i+3) % 100] = largeNumber % modules[(i+3) % 100];
    residues[(i+4) % 100] = largeNumber % modules[(i+4) % 100];
}

with gcc -O2 the gain is ~15%. (500000000 instead of 100 to observe a more significant time difference)