[TUTORIAL] Basic Lagrange Interpolation

Revision en9, by grhkm, 2020-09-23 20:28:58

Lagrange Interpolation by grhkm

No polynomial stuff because I don't know $$$O(n\log{n})$$$ polynomial multiplication :(

Main results:

Given $$$f(x_1)=y_1, f(x_2)=y_2, ..., f(x_n)=y_n$$$ we can calculate $$$f(X)$$$ where $$$f$$$ is the unique $$$(n+1)$$$-degree polynomial

For general {$$$x_i$$$} we can do so in $$$O(n^2)$$$

For consecutive {$$$x_i$$$} i.e. $$$x_j=x_1+(j-1)$$$, we can do so in $$$O(n)$$$ excluding binary exponentiation

Why useful?

Calculate $$$1^n+2^n+...+X^n$$$ in $$$O(n)$$$

DP optimization

With polynomials you can do cool things but not gonna cover this blog

Let's get started :)

Assume all polynomials below are $$$(n+1)$$$ degree unless specified.

disclaimer
Why (n+1) degree?

Idea:

To start let's deal with first problem:

Given $$$f(x_1)=y_1, f(x_2)=y_2, ..., f(x_n)=y_n$$$ and an integer $$$X$$$ we can calculate $$$f(X)$$$ where $$$f$$$ is the unique $$$(n+1)$$$-degree polynomial

Let's consider an easier version:

Find polynomial satisfying $$$f(x_1)=y_i, f(x_2)=0, ..., f(x_n)=0$$$

As we learn in school, $$$f(r)=0 \implies (x-r)$$$ is divisor

We can write this down:

$$$f(x)=(x-x_2)(x-x_3)\cdots (x-x_n)$$$

Now notice that $$$f(x_1)=\prod_{i=2}^n (x_1-x_i)$$$ (a constant), but we want it to be $$$y_1$$$

We can simply scale the polynomial by a correct factor i.e.

$$$f_1(x)= \prod_{i=2}^n (x-x_i) \cdot \frac{y_1}{\prod_{i=2}^n (x_1-x_i)}=y_1\prod_{i=2}^n \frac{x-x_i}{x_1-x_i}$$$

Similarly, we can find a similar polynomial such that $$$f_i(x_i)=y_i$$$ and $$$f_i(x_j)=0 \forall j \neq i$$$

$$$f_i(x) = y_i \prod_{j=1,j\neq i}^n \frac{x-x_i}{x_i-x_i}$$$

Okay now finally to answer the original question, we can notice that $$$f(x)=\sum_{i=1}^n f_i(x)$$$ satisfies the constraints. So there we have it! Lagrange interpolation:

$$$f(x)=\sum_{i=1}^n y_i \prod_{j=1,j\neq i}^n \frac{x-x_j}{x_i-x_j}$$$

$$$O(n^2)$$$ excluding inverse for division

Optimization:

Let's try to optimise it now! Assume that we're given $$$f(1), f(2), \cdots, f(n)$$$, how can we calculate $$$f(X)$$$ quickly?

Notice that here, $$$x_i=i$$$ and $$$y_i=f(i)$$$. Substitute!

$$$f(x) = \sum_{i=1}^n f(i) \prod_{j=1,j\neq i}^n \frac{x-j}{i-j} = \sum_{i=1}^n f(i) \frac{\prod_{j=1,j\neq i}^n x-j}{\prod_{j=1,j\neq i}^n i-j}$$$

Let's consider the numerator and denominator separately

Numerator

$$$\prod_{j=1,j\neq i}^n x-j = [(x-1)(x-2)\cdots (x-(i-1))] \cdot [(x-(i+1))(x-(i+2))\cdots (x-n)]$$$

We can pre-calculate prefix and suffix product of x, then we can calculate the numerator (for each $$$i$$$) in $$$O(1)$$$

Denominator

$$$\prod_{j=1,j\neq i}^n i-j = [(i-1)(i-2)(i-3)\cdots(i-(i-1))] \cdot [(i-(i+1))(i-(i+2))\cdots (i-n)]$$$
$$$=(i-1)! \cdot (-1)^{n-(i+1)+1} \cdot (n-i)!$$$
$$$=(-1)^{n-i} (n-i)! (i-1)!$$$

So we can precompute factorials (preferably their inverse directly) then $$$O(1)$$$ calculation

So now we can calculate $$$f(X)$$$ in $$$O(n)$$$

Example 0

Find_ $$$\sum_{i=1}^N i^k$$$, $$$k\leq 1e6, N\leq 1e12$$$

Solution: Notice that the required sum will be a degree $$$(k+1)$$$ polynomial, and thus we can interpolate the answer with $$$(k+2)$$$ data points (Remember, we need $$$deg(f)+1$$$ points)

To find the data points simply calculate $$$f(0)=0, f(x)=f(x-1)+x^k$$$

Here is my code for 622F: here

Example 1

(BZOJ 3453, judge dead): Find_ $$$\sum_{i=0}^n \sum_{j=1}^{a+id} \sum_{k=1}^j k^x \mod 1234567891, x \leq 123, a, n, d \leq 123456789$$$

Hint

Example 2 (ADVANCED)

(Luogu P4463 submit here): Given $$$n \leq 500, k \leq 1e9$$$, we call a sequence $$${a_n}$$$ nice if $$$1\leq a_i \leq k \forall i$$$ and $$$(a_i\neq a_j) \forall i\neq j$$$. Find the sum of (products of elements in the sequence) over all nice sequences._

Hint
Hint2
Hint3
Hint4

Example 3 (ADVANCED TOO)

Problem https://www.codechef.com/problems/XETF : Find $$$\sum_{i=1,gcd(i,N)=1}^N i^k, N \leq 1e12, k \leq 256$$$

Hint

If you have any questions feel free to ask below

Practice question:

CF 622F (Example 0) Luogu P4463 (Example 2) Codechef XETF (Example 3)

Not in order of difficulty: SPOJ ASUMEXTR SPOJ HARD which is harder than EXTREME Codechef COUNTIT

Tags lagrange-interpolation, math, number-theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en18 English grhkm 2020-09-27 16:45:16 69
en17 English grhkm 2020-09-24 15:08:26 246
en16 English grhkm 2020-09-24 04:36:04 61
en15 English grhkm 2020-09-24 04:32:30 90 :)
en14 English grhkm 2020-09-24 02:58:51 81
en13 English grhkm 2020-09-23 20:53:46 187
en12 English grhkm 2020-09-23 20:52:53 610
en11 English grhkm 2020-09-23 20:31:15 69
en10 English grhkm 2020-09-23 20:29:53 145
en9 English grhkm 2020-09-23 20:28:58 351
en8 English grhkm 2020-09-23 20:20:39 62
en7 English grhkm 2020-09-23 20:02:14 11
en6 English grhkm 2020-09-23 19:54:48 197
en5 English grhkm 2020-09-23 19:53:27 494 no comment idk why im capping
en4 English gupta_samarth 2020-09-23 19:50:29 65 Tiny change: 'calculate f(X) where f is the un' -> 'calculate $f(X)$ where $f$ is the un'
en3 English grhkm 2020-09-23 19:22:27 211
en2 English grhkm 2020-09-23 19:20:52 78
en1 English grhkm 2020-09-23 19:14:05 5510 Initial revision (published)