Can we somehow compute $(z^2 - 1)(z^2 - 4)(z^2 - 9)(z^2 - 16) \cdots (z^2 - k^2)$ in half the number of operations?

Question

Let $f(z, k) = (z^2 - 1)(z^2 - 2^2)(z^2 - 3^2)(z^2 - 4^2) \cdots (z^2 - k^2)$ in less than $1 + k + k + k + (k-1) = 4k$ arithmetic operations, specifically I need it to be roughly $2k$ operations or less.

In the cost formula, the first $1$ comes from needing to square $z$, the first $k$ from incrementing a counter $k$ times to make up $1, 2, 3, \dots k$, i.e. you don't get to have arbitrary constants or tables of constants which really wouldn't add much efficiency anyway. The second $k$ comes from squaring each $k$, the third $k$ comes from the subtraction in each parenthesis. The $(k-1)$ comes from the $(k-1)$ multiplications. So that the totals is $4k$ arithmetic operations if computed directly using the given formula for $f$.

Where does this come from? These are the factors (combined) in $\dfrac{x!}{(x - 2k - 1)!}$ where $z$ is taken to the median factor in the sequence $x(x-1)(x-2)\cdots (z+1)z(z-1) \cdots (z-k)$. I don't know if that is 100% accurate, but that part doesn't matter. Just to tell you where it comes from. Computing this directly requires twice as many operations as $f(z,k)$. So already in computing a factorial I've reduced the operations by half. So I'm just wondering if we can or can't find a way of reducing it by another half.

Question. How can we compute $f(z,k)$ in $2k$ arithmetic operations or less (roughly)?

If you can do it with $\dfrac{8k}{5}$ operations or something that would also be interesting if you get my drift.

---

This might help because of group theory: All the arithmetic is done modulo some $n\in \Bbb{N}\setminus 1$ and $\sqrt{n} \geq z,k$. But note $n$ will be huge or 1000's of digits (think RSA numbers that are hard to factor). But also note that we can take each $1,2,3,\dots, k$ as well as $z$ to be coprime to $n$ because in any factorization algorithm you can check the result of every arithmetic operation and only add a polynomial factor slow-down (the cost of computing $\gcd(x\pmod n, n)$). Thus on the right we have that the results of all arithmetic operations are units in $\Bbb{Z}/n$. If it turns out that they're not, then we can halt the algorithm because a factor has been found or $\gcd(x\pmod n, n) = n$ in which case we can stop computing the long factorial and change the binary search parameters to another range $[y,x]$ because a $\gcd$ result of $n$ would indicate "you've gone too far" and included all factors of $n$, so back up and try again.

Because of coprimality, the set $\{ y^2 \pmod n\} \leqslant (\Bbb{Z}/n)^{\times}$ forms a subgroup of the units. We're also able to "pretend that we're working in a field" because of this, that is until a factor is found. I know that other integer factorization algorithms do just that.

Answer 1

Expanding on my comment, the central symmetry of the product suggests looking at symmetric pairs:

$$ \begin{align} (z^2-j^2)(z^2-(k-j+1)^2) &=\color{red}{(z-j)}\color{blue}{(z+j)}\color{red}{\big(z-(k+1-j)\big)}\color{blue}{\big(z+(k+1-j)\big)} \\ &= \color{red}{\big(z^2 - (k+1)z +j(k+1-j)\big)}\color{blue}{\big(z^2 + (k+1)z +j(k+1-j)\big)} \\ &= \big(z^2+j(k+1-j)\big)^2 - (k+1)^2z^2 \\ &= \big(z^2+n_j\big)^2 - (k+1)^2z^2 \end{align} $$

Here $\,n_j=j(k+1-j)\,$, which can be calculated recursively with $\,n_1=k\,$ and $\,n_{j+1}=n_{j}+k-2j\,$.

For $\,j=1\,$ to $\,k/2\,$, an approximate count ignoring some half $\,1/2\,$ ops:

• the sequence $\,k-2j\,$ can be calculated iteratively by subtracting $\,2\,$ at each step, total $\,k/2\,$ ops;

• the sequence $\,n_{j+1}=n_j+(k-2j)\,$ then takes one addition at each step, total $\,k/2\,$ ops;

• the term $\,\big(z^2+n_j\big)^2\,$ takes $\, 2 \cdot k/2 = k\,$ ops;

• the difference of terms takes $\,k/2\,$ op.

• the multiplication of pairs take $\,k/2\,$ ops.

In the end, it adds up to about $\,3k\,$ ops, which is slightly better than the baseline, but still short of the target $\,2k\,$.

Answer 2

Using $(n+1)^2=n^2+(2n+1)$, set $m=1, j=3, y=z^2-1, p=y$.

Then $m=m+j, j=j+2, y=y-m, p=p*y$ until $j=(k+1)^2$.

So $j=3, 5, 7, ..., m=1, 4, 9, ..., y=z^2-1, z^2-4, ... $.

Each step takes 2 adds, 1 subtract, and 1 multiply.

Don't immediately how to do it faster.

Answer 3

This method is similar to marty cohen's. It uses recursive addition to evaluate polynomials.
It takes $2$ adds and $1/2$ a multiply for each of your quadratic factors $(z^2-i^2)$.
I don't know if your language requires an extra step for a counter that you don't use, but that would be an extra half an add.
Take the $(z^2-i^2)$ in pairs.
$$G(z,m)=(z^2-(2m-1)^2)(z^2-(2m)^2)$$ $G(z,m)$ is a degree-4 polynomial in $m$. Define $$H(z,m)=G(z,m+1)-G(z,m)\\ I(z,m)=H(z,m+1)-H(z,m)\\ J(z,m)=I(z,m+1)-I(z,m)\\ K(z)=J(z,m+1)-J(z,m)$$ $H(z,m)$ is cubic in $m$, $I(z,m)$ is quadratic in $m$, $J(z,m)$ is linear in $m$ and $K(z)$ is independent of $m$.
Each of $J,I,H,G$ can be calculated with one addition.
$$J(z,m+1)=J(z,m)+K(z)\\ I(z,m+1)=I(z,m)+J(z,m)\\ H(z,m+1)=H(z,m)+I(z,m)\\ G(z,m+1)=G(z,m)+H(z,m)$$ So each $G(z,m)$ can be calculated in a total of four additions.
Multiply them all together as you go along, with one multiply per pair.
You don't need subscripts as you overwrite $G,H,I,J$ as you go.
A similar trick, with $7k/3$ or $8k/3$ steps per $(z^2-i^2)$, works if you group the $(z^2-i^2)$ in threes, and so on.