Fast mpz_bin_ui

Yann Laigle-Chapuy yannlaiglechapuy at
Fri Oct 13 12:51:22 UTC 2017

Niels Möller nisse at

> >*   n (n-2)(n-4)(n-6) = [(n-3)^2 - 5]^2 - 25*

> I like this trick, replacing three multiplies by two squares (but it's
> unclear how much it will save compared to the total running time). For
> the reasons given above, I wouldn't expect the trick to generalize much
> further.

Here is one step further:

n(n-*2*)(n-*4*)(n-*6*)(n-*8*)(n-*10*)(n-*12*)(n-*14*) =
(((n-*7*)^*2*-*21*)^*2*-*336*)^*2* - *4096*(n-*7*)^*2*

We get three squares instead of seven multiplies.



More information about the gmp-devel mailing list