Algorithms-1 01

Polynomial multiplication problem

Problem input

Problem output

---

Polynomial definition

• Polynomial can be represented in memory as an array of coefficients
• Polynomial can also be represented as arbitrary points such that

• Transformation from coefficients to points takes time
• Transformation from points to coefficients also takes time, this is to be proved in HWs

Fast Fourier Transformation (FFT) definition

An algorithm for performing transformations between coefficients and points representations in time

Karatsuba algorithm definition

An algorithm for performing polynomial multiplication in time (and subsequently n-digit multiplication)

---

Generalization

First solution

Fill with zeroes up to degree and use FFT. The result is

Second solution

Naive multiplication,

Combination of two solutions

Compare and choose either solution.

Third solution

Divide into -sized chunks and perform FFT. There are iterations of FFT (). All and all,

---

Using polynomial multiplication in the 3-SUM problem

Problem input

Problem output

First solution

Running 2-SUM for each element.

Second solution

Let

This means that can be represented as an array of coefficients 0, 1 of size , this takes time We can calculate in using FFT and then check which coefficients are non-zero. This check takes , all and all,

With the limitation of not using the same element twice, we simply check if the coefficient is larger than 1, not just non-zero