Toom Cook Multiplication Algorithm
• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 summer project pal Active In SP Posts: 308 Joined: Jan 2011 22-01-2011, 05:46 PM Toom Cook Multiplication Algorithm B.Tech Seminar Report by Fayyas Manzoor M Department of Computer Science And Engineering Government Engineering College, Thrissur December 2010   Toom Cook Multiplication Algorithm.pdf (Size: 86.24 KB / Downloads: 80) Abstract There are a number algorithms used for multiplication of large integers, Toom Cook Multiplication Algorithm is one of them. What this algorithm does is that it divides large numbers into smaller parts and perform operations on the parts. Multiplication operations on smaller parts can be done using Toom Cook algorithm recursively. General Toom Cook algorithm is also known as Toom-k algorithm where k represents the number of parts into which large number is divided. Complexity of Toom-k algorithm is (nlog(2k−1)/log(k)). Chapter 1 Introduction This seminar and presentation describes about Toom Cook Multiplication algorithm. Toom Cook Multiplication algorithm is used for multiplying large integers. It was Andrei Toom who first described this algorithm, later Stephen Cook improved the algorithm and thus the name Toom Cook Algorithm. Toom Cook algorithm (Toom-k) divide numbers to be multiplied into k smaller parts and does some operations on the parts. Toom Cook algorithm can be used recursively for doing the operations on sub parts. Toom-3 which is illustrated using examples in this report is a single instance of Toom Cook algorithms where a number is divided into three parts. Using ordinary multiplication(known as grade school multiplication) requires nine multiplication to find product of two 3 digit numbers. Toom-3 reduces nine multiplications into three and its complexity is (nlog(5)/log(3))=(n1.465). Steps involved in Toom Cook algorithm are: 1. Splitting 2. Evaluation 3. Pointwise Multiplication 4. Interpolation 5. Recomposition 1.1 Organization Of the report Here after each chapter in this report describes each step involved in the algorithm. For illustration purposes, I used following two numbers throughout this report: m = 12 3456 7890 1234 5678 9012 and n = 9 8765 4321 9876 5432 1098 section 1.1 Seminar Report 2010 1. Chapter 2 is on Splitting. 2. Chapter 3 describes Evaluation step. 3. Chapter 4 is on Pointwise multiplication step. 4. Chapter 5 discusses Interpolation. 5. Chapter 6 explains Recomposition step. 6. Chapter 7 is on applications of the algorithm. Dept. of CSE, GEC, Thrissur 2 Seminar Report 2010 Chapter 2 Splitting First step in the algorithm is splitting. In splitting each number is split in to k sub parts. • First we have to select a base B=bi such that number of digits of both the numbers are atmost k where i is given by following formula. i=max{⌊⌈logbm⌉/k⌋, ⌊⌈logbn⌉/k⌋} • Then use these digits as coefficients in degree k-1 polynomials p and q such that p(B)=m and q(B)=n. • Our aim is to find out a polynomial r such that r(x)=p(x)q(x). Then r(B)=m∗n will be our result. 2.1 Toom-3 illustration In Toom-3, k=3 and so we choose i=b6/3=108 • Now we seperate m and n into their base B digits. m0=56789012 m1=78901234 m2=123456 n0=54321098 n1=43219876 n2=98765 Dept. of CSE, GEC, Thrissur 3 section 2.1 Seminar Report 2010 • Now using this digits in degree 2 polynomial p(x) = m2x2 + m1x + m0 = 123456x2 + 78901234x + 56789012 q(x) = n2x2 + n1x + n0 = 98765x2 + 43219876x + 54321098 Dept. of CSE, GEC, Thrissur 4 Seminar Report 2010 Chapter 3 Evaluation In this step, we evaluate the polynomials formed in earlier step at various points. • We evaluate both polinomials at deg(p) + deg(q) + 1 = km+kn-1 points. • Choosing small integers like 0, 1, -1 and -2 will make algorithm easy. • Also infinity is choosen as a point. Value of a polynomial at infinity is computed by evaluating limit of polynomial/xdegreeofpolymomial as x goes to infinity. As a result value of polynomial at infinity will be always the value of highest degree coefficient. 3.1 Toom-3 illustration For Toom-3 we use km + kn-1 = 5 points. We take the points 0, 1, -1, -2, ∞. p(0) = m0 + m1(0)+m2(0)2 = m0 = 56789012 p(1) = m0 + m1(1)+m2(1)2 = m0 + m1 + m2 = 135813702 Dept. of CSE, GEC, Thrissur 5 section 3.1 Seminar Report 2010 p(-1) = m0 + m1(-1)+m2(-1)2 = m0 - m1 + m2 = 21988766 p(-2) = m0 + m1(-2)+m2(-2)2 = m0 - 2m1 + 4m2 = 100519632 p(∞) = m2 = 123456 Similarly q(0) = n0 = 54321098 q(1) = n0 + n1 + n2 = 97639739 q(-1) = n0 - n1 + n2 = 11199987 q(-2) = n0 - 2n1 + 4n2 = 31723594 q(∞) = n2 = 98765 Chapter 4 Pointwise Multiplication In this step we multiply values of both polynomial at each point to get value of the product polynomial at corresponding point, ie we multiply p(a) and q(a) to get r(a) for all ’a’ in the set of selected points in previous step. This step just involves multiplication of integers. It can be done by using Toom Cook algorithm recursively. 4.1 Toom-3 illustration r is the product polynomial. r(0) = p(0)q(0) = 56789012 ∗ 54321098 = 3084841486175176 r(1) = p(1)q(1) = 135813702 ∗ 97639739 = 13260814415903778 r(-1) = p(-1)q(-1) = -21988766 ∗ 11199987 = -246273893346042 r(-2) = p(-2)q(-2) = -100519632 ∗ -31723594 = 3188843994597408 r(∞) = p(∞)q(∞) = 123456 ∗ 98765 = 12193131840 Chapter 5 Interpolation This step is actually the reverse of evaluation step. Now we have values of product polynomial at various points. So we can find out the coefficients of product polynomial and that process is called interpolation. 5.1 Toom-3 illustration We have to solve the following matrix equation: 26666664 r(0) r(1) r(−1) r(−2) r(∞) 37777775 = 26666664 00 01 02 03 04 10 11 12 13 14 (−1)0 (−1)1 (−1)2 (−1)3 (−1)4 (−2)0 (−2)1 (−2)2 (−2)3 (−2)4 0 0 0 0 1 37777775 26666664 r0 r1 r2 r3 r4 37777775 = 26666664 1 0 0 0 0 1 1 1 1 1 1 −1 1 −1 1 1 −2 4 −8 16 0 0 0 0 1 37777775 26666664 r0 r1 r2 r3 r4 37777775 where r0, r1, r2, r3, r4 are coefficients of product polynomial r. Using Gaussian elimination method to solve above equation is too expensive. So what we do is, when selecting points in evaluation step, we choose suitable points such that the matrix is invertible. Dept. of CSE, GEC, Thrissur 8 section 5.3 Seminar Report 2010 So coefficients of product polynomial can be computed as follows: 26666664 r0 r1 r2 r3 r4 37777775 = 26666664 1 0 0 0 0 1 1 1 1 1 1 −1 1 −1 1 1 −2 4 −8 16 0 0 0 0 1 37777775 −1 26666664 r(0) r(1) r(−1) r(−2) r(∞) 37777775 = 26666664 1 0 0 0 0 1/2 1/3 −1 1/6 −2 −1 1/2 1/2 0 −1 −1/2 1/6 1/2 −1/6 2 0 0 0 0 1 37777775 26666664 r(0) r(1) r(−1) r(−2) r(∞) 37777775 5.2 Marco Bodrato’s sequence for matrix product Finding an efficient sequence of operations to compute matrix product is a difficult design challenge. Marco Bodrato proposed a sequence for computing matrix product in his paper Towards Optimal Toom Cook Matrices for Integer and Polynomial Multiplication which is applied here for our example: r0 ← r(0) = 3084841486175176 r4 ← r() = 12193131840 r3←(r(-2) - r(1))/3 = (3188843994597408 - 13260814415903778)/3= -3357323473768790 r1←(r(1) - r(-1))/2 = (13260814415903778- (-246273893346042))/2= 6753544154624910 r2 ← r(-1) - r(0) = -246273893346042 - 3084841486175176 = -3331115379521218 r3←(r2 - r3)/2 + 2r() = (-3331115379521218 - (-3357323473768790))/2+ 212193131840 = 13128433387466 r2 ← r2 + r1 - r() = -3331115379521218 + 6753544154624910 - 12193131840 = 3422416581971852 r1 ← r1 - r3 = 6753544154624910 - 13128433387466 = 6740415721237444 Dept. of CSE, GEC, Thrissur 9 section 5.3 Seminar Report 2010 5.3 Product polynomial Now we computed all coefficients of product polynomial. Thus the product polynomial is : r(x) = 3084841486175176 + 6740415721237444x + 3422416581971852x2 + 13128433387466x3 + 12193131840x4 Chapter 6 Recomposition We got product polynomial in previous step. All that remains to do is that we have to find out r(B). But in first step, we selected B as a power of b. So multiplication by powers of B (during computation of r(B)) is nothing but shifts by a whole number of digits in base b. 6.1 Final Answer Here we shift numbers by 8 digits and find their sum to get final result. 3084 8414 8617 5176 + 6740 4157 2123 7444 3422 4165 8197 1852 13 1284 3338 7466 121 9313 1840 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 9326 3124 6761 1632 4937 6009 5208 5858 8617 5176 Dept. of CSE, GEC, Thrissur 11 Seminar Report 2010 Chapter 7 Conclusion 7.1 Applications of Toom Cook algorithm Toom Cook Multiplication Algorithm is having a several applications in calculations involving large integers. Typical application areas are: • Big Num arithmatic • Cryptography like PGP, SSL, IPSec for dealing with keys having large length. • For calculation of mathematical constants like , e etc. Seminar described each step in Toom Cook algorithm illustrating Toom-3 algorithm which is a special instance of general Toom Cook algorithm. References [1] Marco Bodrato, Alberto Zanoni Towards Optimal Toom-Cook Matrices for Integer and Polynomial Multiplication, Springer 2006 [2] Marco Bodrato Towards Optimal Toom-Cook Multiplication for Univariate 2. and Multivariate Polynomials in Characteristic 2 and 0, WAIFI’07, Springer 2007.