Fast mpz_bin_ui
Marco Bodrato
bodrato at mail.dm.unipi.it
Sat Oct 14 13:30:57 UTC 2017
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/
More information about the gmp-devel
mailing list