mpz_addmul_ui with ui = 2^n

Jim White mathimagics at
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?

Jim White
ANU, Canberra

More information about the gmp-discuss mailing list