Recursive squaring algorithm by reducing to squaring 5 numbers

Question

*(c) Describe a recursive algorithm that squares any $n$-digit number in $O(n^{log_35})$ time, by reducing to squaring only five $(n/3+O(1))$-digit numbers.
[Hint: What is $(a+b+c)^2+(a−b+c)^2$?]

I am currently studying the Toom-Cook algorithm which is highly related to this question. I came across a related post here but could not understand it sufficiently. For example, why the form of $10^{2m}x+10^my+z$ and the discovery of the last missing square.

Any help is appreciated.

Answer 1

Wikipedia's article on Toom–Cook multiplication has a nice explanation that doesn't involve guessing missing squares; let me simplify it for your case.

If you're writing your number as $10^{2m}a + 10^m b + c$ (essentially, breaking up the digits into three segments $a, b, c$) then you're writing your number as $p(10^m)$ where $p(x)$ is the quadratic polynomial $ax^2+bx+c$.

So the square of your number will be $p(10^m)^2$, which is the quartic polynomial $q(x) = p(x)^2 = (ax^2+bx+c)^2$ evaluated at $x=10^m$.

Now, we're going to try to find $q(x)$ in a different way. Specifically, we know the following:

• The constant term of $q(x)$ is $c^2$, or in other words $q(0)=p(0)^2=c^2$.
• The coefficient of $x^4$ in $q(x)$ is $a^2$, which Wikipedia thinks of as $q(\infty) = p(\infty)^2 = a^2$.
• $q(1) = p(1)^2 = (a+b+c)^2$.
• $q(-1) = p(-1)^2 = (a-b+c)^2$.
• $q(-2) = p(-2)^2 = (4a-2b+c)^2$.

The above squares are the five squares we're going to evaluate. Then, if $q(x) = q_4 x^4 + q_3 x^3 + q_2 x^2 + q_1 x + q_0$, we have a system of five equations in five variables: \begin{align} q_0 &= c^2 \\ q_4 &= a^2 \\ q_4 + q_3 + q_2 + q_1 + q_0 &= (a+b+c)^2 \\ q_4 - q_3 + q_2 - q_1 + q_0 &= (a-b+c)^2 \\ 16q_4 - 8q_3 + 4q_2 - 2q_1 + q_0 &= (4a-2b+c)^2 \end{align} Solve these for the $q_i$'s and then evaluate $q(10^m)$ to find $(10^{2m}a+10^mb+c)^2$.