Fast mpz_bin_ui

[Marco Bodrato]

Saluton!

Il Gio, 12 Ottobre 2017 10:03 pm, Niels Möller ha scritto:
>>   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

How much will it save? As usual, it depends on the operands.

I bet the saving is unnoticeable if one needs binomial(99999999,11111111),
but it can be detected if one computes binomial(9^9999999,7).

> the reasons given above, I wouldn't expect the trick to generalize much
> further.

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

... all of them contains some long additions,

Ĝis,
m
-- 
http://bodrato.it/papers/