[prev in list] [next in list] [prev in thread] [next in thread]
List: gmp-devel
Subject: Fast mpz_bin_ui
From: yannlaiglechapuy () gmail ! com (Yann Laigle-Chapuy)
Date: 2017-10-16 8:16:57
Message-ID: CAFS4oEGbBVN3=xiXu8DXriwd67DVj8c=K0Aw1buY-OhgzVm2Ng () mail ! gmail ! com
[Download RAW message or body]
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
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic