Title: **Topic: Fast 3-digit Squaring, Toom-Cook **

Post by:**Zeda** on **June 26, 2018, 06:36:55 pm**

Post by:

Hi all, I realized that I have a __lot__ of unshared results that I've worked out over the years! (Then again, I have a __lot__ of shared results :P )

Today's is dealing with squaring 3-digit numbers.

If you aren't familiar with the Toom-Cook algorithm, read the spoiler! It's cool stuff. Otherwise, continue down.

To square a 3-digit number, we'll result in a degree-4 polynomial. Consequently, we'll need to evaluate at 5 points. The points I chose were {0,1,i,-1,-i} where 'i' is the imaginary unit. It may seem like evaluating at a complex point would be, well, complex, but we'll see. First, let's write our polynomial as a_{0}+a_{1}x+a_{2}x^{2}.

Then:

b_{0}=f(0)=a_{0}^{2}

b_{1}=f(1)=(a_{0}+a_{1}+a_{2})^{2}

b_{2}=f(i)=(a_{0}+a_{1}i-a_{2})^{2}

b_{3}=f(-1)=(a_{0}-a_{1}+a_{2})^{2}

b_{4}=f(-i)=(a_{0}-ia_{1}-a_{2})^{2}

Squaring complex numbers is easy though-- (a+bi)^{2}= a^{2}-b^{2}+2abi = (a-b)(a+b)+2abi

So simplifying:

b_{2}=(a_{0}-a_{2}+a_{1})(a_{0}-a_{2}-a_{1})+2i(a_{0}-a_{2})a_{1}

b_{4}=(a_{0}-a_{2}+a_{1})(a_{0}-a_{2}-a_{1})-2i(a_{0}-a_{2})a_{1}

Noticing symmetry, let's define instead:

c_{3}=(a_{0}-a_{2}+a_{1})(a_{0}-a_{2}-a_{1})

c_{4}=2(a_{0}-a_{2})a_{1}

Then:

b_{2}=c_{3}+ic_{4}

b_{4}=c_{3}-ic_{4}

1 0 0 0 0 b_{0}

1 1 1 1 1 b_{1}

1 i -1 -i 1 c_{3}+ic_{4}

1 -1 1 -1 1 b_{3}

1 -i -1 i 1 c_{3}-ic_{4}

1 0 0 0 0 b_{0}

1 0 1 0 1 (b_{1}+b_{3})/2 = c_{1}

=> 0 1 0 1 0 (b_{1}-b_{3})/2 = c_{2}

1 0 -1 0 1 c_{3}

0 1 0 -1 0 c_{4}

1 0 0 0 0 b_{0}

1 0 0 0 1 (c_{1}+c_{3})/2 = d_{1}

=> 0 0 1 0 0 (c_{1}-c_{3})/2 = d_{2}

0 1 0 0 0 (c_{2}+c_{4})/2 = d_{3}

0 0 0 1 0 (c_{2}-c_{4})/2 = d_{4}

Then our polynomial is:

b_{0}+d_{3}x+d_{2}x^{2}+d_{4}x^{3}+(d_{1}-b_{0})x^{4}

So for an example, let's find 348*348

Then we have:

a_{0}=8

a_{1}=4

a_{2}=3

b_{0}=64

b_{1}=(8+4+3)^{2}=225

b_{3}=(8-4+3)^{2}=49

c_{3}=(8-3+4)(8-3-4)=9

c_{4}=2(8-3)*4=40

c_{1}=(225+49)/2 = 137

c_{2}=c_{1}-49 = 88

d_{1}=(137+9)/2 = 73

d_{2}=d_{1}-9 = 64

d_{3}=(88+40)/2 = 64

d_{4}=d_{3}-40 = 24

So then, our result is:

64+64x+64x^{2}+24x^{3}+9x^{4}

Evaluating at x=10~~eyelids~~ yields:

64+640+6400+24000+90000 = 121104, which is indeed 384*384

Now let's generate some Python code:

Note that three of the sub-multiplications are just squaring the input. Also note that all divisions are by a power of two, and all results and operations are integer operations, not complex (assuming all inputs are integers).

Today's is dealing with squaring 3-digit numbers.

If you aren't familiar with the Toom-Cook algorithm, read the spoiler! It's cool stuff. Otherwise, continue down.

To square a 3-digit number, we'll result in a degree-4 polynomial. Consequently, we'll need to evaluate at 5 points. The points I chose were {0,1,i,-1,-i} where 'i' is the imaginary unit. It may seem like evaluating at a complex point would be, well, complex, but we'll see. First, let's write our polynomial as a

Then:

b

b

b

b

b

Squaring complex numbers is easy though-- (a+bi)

So simplifying:

b

b

Noticing symmetry, let's define instead:

c

c

Then:

b

b

1 0 0 0 0 b

1 1 1 1 1 b

1 i -1 -i 1 c

1 -1 1 -1 1 b

1 -i -1 i 1 c

1 0 0 0 0 b

1 0 1 0 1 (b

=> 0 1 0 1 0 (b

1 0 -1 0 1 c

0 1 0 -1 0 c

1 0 0 0 0 b

1 0 0 0 1 (c

=> 0 0 1 0 0 (c

0 1 0 0 0 (c

0 0 0 1 0 (c

Then our polynomial is:

b

So for an example, let's find 348*348

Then we have:

a

a

a

b

b

b

c

c

c

c

d

d

d

d

So then, our result is:

64+64x+64x

Evaluating at x=10

64+640+6400+24000+90000 = 121104, which is indeed 384*384

Now let's generate some Python code:

Code Select

def sqr3(a,b,c):

d=a+b+c #roughly 75% of cases exceed the original bit-width

d*=d

e=a-b+c #roughly 1/6 of the time this will exceed the original bit-width. However, whenever this exceeds the bit-width, then d also exceeds it.

e*=e

d=(d+e)/2

e=d-e

f=(a+b-c)*(a-b-c) #it is never the case that both multiplicands exceed their original word width, but about 1/3 of the time, one of them exceeds it (~2/3 of the time, neither exceed).

b*=(a-c) #neither multiplicand exceeds the original bit-width (though the second operand may become negative).

b+=b

a*=a

e=(e+b)/2

b=e-b

d=(d-f)/2

f+=d-a

return [a,e,d,b,f]

Note that three of the sub-multiplications are just squaring the input. Also note that all divisions are by a power of two, and all results and operations are integer operations, not complex (assuming all inputs are integers).