così essenzialmente si sta facendo
k_0 = h_1 mod s
k_1 = h_1 + h_2 mod s = k_0 + h_2 mod s
k_2 = h_1 + h_2 + h_2 mod s = k_1 + h_2 mod s
..
k_n = k_(n-1) + h_2 mod s
A seconda di overflow problemi (che non dovrebbe differire da quello originale se la dimensione è meno della metà di 2**64
), questo potrebbe essere più veloce (meno facile da parallelizzare però):
uint64_t h_one = hash[0];
uint64_t h_two = hash[1];
k_hash[0] = h_one % size;
for (int i=1; i<k; ++i)
{
(uint64_t *) k_hash[i] = (k_hash[i-1] + h_two) % size;
}
Nota esiste la possibilità che il compilatore sia già arrivato in questo modulo, a seconda dei flag di ottimizzazione che si utilizzano.
Ovviamente questo ha eliminato solo una moltiplicazione. Se si vuole eliminare o ridurre il modulo, credo che sulla base di h_two%size
e h_1%size
è possibile predeterminare i passi in cui si deve chiamare esplicitamente %size
, qualcosa di simile:
uint64_t h_one = hash[0]%size;
uint64_t h_two = hash[1]%size;
k_hash[0] = h_one;
step = (size-(h_one))/(h_two)-1;
for (int i=1; i<k; ++i)
{
(uint64_t *) k_hash[i] = (k_hash[i-1] + h_two);
if(i==step)
{
k_hash[i] %= size;
}
}
Nota Non sono sicuro del formula (non testarlo), è più un'idea generale. Ciò dipenderebbe in gran parte da quanto è buona la tua previsione di branca (e quanto è grande una prestazione - ha colpito una misprediction). Inoltre, è molto probabile che aiuti se il passo è grande.
edit: o più semplice (e probabilmente con le stesse prestazioni) -Grazie al mistico:
uint64_t h_one = hash[0]%size;
uint64_t h_two = hash[1]%size;
k_hash[0] = h_one;
for (int i=1; i<k; ++i)
{
(uint64_t *) k_hash[i] = (k_hash[i-1] + h_two);
if(k_hash[i] > size)
{
k_hash[i] -= size;
}
}
Sai niente di 'size'? – Mysticial
Ho modificato la domanda per chiarire alcune cose come richiesto –
Esistono metodi là fuori che rendono ripetute divisioni/modulo sullo stesso numero molto efficienti. Ma non è banale. – Mysticial