Fast mpz_bin_ui

[Yann Laigle-Chapuy]

Sat Oct 14 13:30:57 UTC 2017, Marco Bodrato wrote:

> I agree. It sounds difficult to generalise, but surely there are other

> more or less elegant formulas of the same kind. I trivially tried some,
> e.g.:

> n*(n-1)*(n-2)*(n-3) == ((n-1)^2 - n)^2 - 1
>  [2 squares and some linear combinations ...]

> n*(n-2)*(n-4)*(n-6)*(n-8)*(n-10)*(n-12)*(n-14) ==
> ((x - 21)^2 - 336)^2 - (x<<12) | x = (n-7)^2
>  [3 squares and some linear combinations ...]

> n*(n-1)*(n-2)*(n-3)*(n-4)*(n-5)*(n-6)*(n-7) ==
> (x^2 - 21)^2 + (x<<8) + 336 | x = (n-3)^2 - n - 2
>  [3 squares and some linear combinations ...]


Hi,

Here's one more step:
with

t = (n - 15)^2
u = (t -85)^2
v = (u - 5712)^2

we have

prod(n-2*i for i in range(16)) = (v - 348160*t)^2 - 8912896*((u + 120*t)^2
 - 16496*u - 1970560*t) - 598143754305536

[5 squares and some linear combinations ...]

This starts to be ugly though :)

Yann