mpz_addmul_ui with ui = 2^n
mathimagics at yahoo.co.uk
Fri Jan 30 10:59:33 CET 2009
Once again, referring to the calculation of convergents in CF algorithms, we also have a very high incidence of ui multipliers with value 2 or 4 (20% for RCF, over 30% in alternative CF algorithms).
The basic convergent calculation is B = m.BB + B, with m an unsigned integer. We then exchange B and BB, calculate the next value of m, and repeat ad nauseam.
The convergent calculation and exchange are done with mpz_addmul_ui and mpz_swap.
But what if we did not have the (admirable) mpz_addmul_ui function, and had to do this with two separate steps, an mpz_mul_ui followed by an mpz_add?
In that case we get considerable advantage by using mpz_mul_2exp for the cases m = 2, 4.
This advantage does not apply in reality, of course, since we DO have mpz_addmul_ui. But it does prompt me to ask whether an "mpz_addmul_2exp" function makes sense? Could it be faster than mpz_addmul_ui for ui values that are powers of 2?
More information about the gmp-discuss