In Elegia's blog How to composite (some) polynomials faster, we know how to compose some special power series in $$$\mathcal O(n\log n)$$$ time, especially for the quadratic rational fraction $$$(ax^2+bx+c)/(dx^2+ex+f)$$$ and the cubic polynomial $$$ax^3+bx^2+cx+d$$$. In this blog I will show how to use this method to calculate $$$\prod_{i=1}^n(x-g(i))$$$ in $$$\mathcal O(n\log n)$$$ time, where $$$g(x)$$$ is a quadratic rational fraction, written as $$$(ax^2+bx+c)/(dx^2+ex+f)$$$.

Basic Knowledge

Let's review how to calculate $$$f_n(x):=\prod_{i=1}^n(x-i)$$$ in $$$\mathcal O(n\log n)$$$ time. We solve this problem by recursion.

If $$$n$$$ is even, assuming we have already computed $$$f_{n/2}$$$, then $$$f_n(x)=f_{n/2}(x)\cdot f_{n/2}(x-n/2)$$$, which could be calculated in $$$\mathcal O(n\log n)$$$ time.

If $$$n$$$ is odd, assuming we have already computed $$$f_{n-1}$$$, then $$$f_n(x)=f_{n-1}(x)\cdot (x-n)$$$, which could be calculated in $$$\mathcal O(n)$$$ time.

Hence, we know that the time complexity of this algorithm is $$$T(n)=T(n/2)+\mathcal O(n\log n)$$$. According to Master Theorem, $$$T(n)=\mathcal O(n\log n)$$$.

Also, this is the classic solution for calculating (signed) Stirling numbers of the first kind $$${n\brack k}, 1\le k\le n$$$ in $$$\mathcal O(n\log n)$$$ time.

Main Tricks

For convenience, we may assume that $$$g(i)\neq0,\forall 1\le i\le n$$$.

From the above, we know how to find $$$\prod_{i=1}^n (x-g(i))$$$ when $$$g(x)=x$$$. At the same time, we know that we can use $$$ax+b,x^2,x^{-1}$$$ to construct a composition chain for any quadratic rational fractions. For example,

Therefore, it remains to show that if we can calculate $$$\prod_{i=1}^n (x-g(i))$$$ in $$$\mathcal O(n\log n)$$$ time, then so are $$$\prod_{i=1}^n [x-(ag(i)+b)],\prod_{i=1}^n (x-g(i)^2),\prod_{i=1}^n (x-1/g(i))$$$. Here, we regard $$$g(x)$$$ as some unknown function, not necessarily the quadratic rational fractions.

Let $$$G(x)=\prod_{i=1}^n (x-g(i))$$$.

For the first one, notice that

so we are done.

For the second one, notice that

so we are done.

For the third one, notice that

so we are done.

Quite easy!

As a reminder, $$$\prod_{i=1}^n (x-g(i)^k)$$$ could also be calculated in $$$\mathcal O(n\log n)$$$ time (omit $$$k$$$ in time complexity), if we acknowledge the existence of $$$k$$$-th primitive root.

Some Application

Using the ln-exp tricks, we can also calculate $$$\sum_{i=1}^n h(g(i)x)\bmod x^n$$$, where $$$g$$$ is quadratic rational fraction, $$$h$$$ is any power series. The key is to find out $$$\sum_{i=1}^n g(i)^j,1\le j\le n$$$, which is $$$-j[x^j]\log \prod_{i=1}^n(1-g(i)x)$$$. Therefore we are done!

Further Discussion

Compared to the basic element in the composition for cubic polynomial, we found that we didn't discuss how to calculate $$$\prod_{i=1}^n(x-g(i)^{1/2})$$$ yet! The main obstacle is that though it's easy to find $$$F(x)$$$ in the function equation $$$G(x)G(-x)=F(x^2)$$$ when $$$G(x)$$$ is known, we do not know how to solve $$$G(x)$$$ when $$$F(x)$$$ is given. Therefore, for any cubic polynomial $$$g(x)$$$, I don't know how to calculate $$$\prod_{i=1}^n(x-g(i))$$$ in $$$\mathcal O(n\log n)$$$ time.

Unfortunately!