Fast mpz_bin_ui

[Yann Laigle-Chapuy]

Niels Möller nisse at lysator.liu.se
<gmp-devel%40gmplib.org?Subject=Re%3A%20Fast%20mpz_bin_ui&In-Reply-To=%3Cnny3oocupm.fsf%40armitage.lysator.liu.se%3E>
writes:

> >*   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.

Regards,

Yann