{"id":161,"date":"2014-09-10T11:58:29","date_gmt":"2014-09-10T17:58:29","guid":{"rendered":"http:\/\/jacobncalvert.com\/?p=161"},"modified":"2018-02-10T15:44:11","modified_gmt":"2018-02-10T21:44:11","slug":"toom-k-polynomial-multiplication","status":"publish","type":"post","link":"https:\/\/jacobncalvert.com\/blog-archive\/2014\/09\/10\/toom-k-polynomial-multiplication\/","title":{"rendered":"Toom-k Polynomial Multiplication"},"content":{"rendered":"<p>I&#8217;ve been pretty busy with classes the past two weeks, but I&#8217;ve learned a few neat things and I&#8217;d like to share one of them.<br \/>\nMultiplying big numbers is a problem when the numbers are\u00a0<i>really, really\u00a0<\/i>big. How big is\u00a0<i>really, really\u00a0<\/i>big? Depends on the hardware your using.<\/p>\n<p>But to multiply really big numbers, we represent the two multiplicands as polynomials where each term is in the form\u00a0cx<sup>n<\/sup>, where x is the base in the number system, c is its coefficent modifier and n is the power to which the base is modified. For example, we can represent 4587 as 4x<sup>3<\/sup>\u00a0+ 5x<sup>2<\/sup>\u00a0+ 8x<sup>1<\/sup>\u00a0+ 7x<sup>0<\/sup>, where x = 10.<br \/>\nNow, two numbers in this polynomial base representation can be multiplied to give the result. Here&#8217;s a small example:<\/p>\n<pre>321 = 3*10^2 + 2*10^1 + 1*10^0 ==&gt; 3x^2 + 2x + 1\r\n\r\n123 = 1*10^2 + 2*10^1 + 3*10^0 ==&gt; 1x^2 + 2x + 3\r\n\r\n321 * 123 = (3x^2 + 2x + 1)*(1x^2 + 2x + 3) = 3x^4 + 6x^3 + 9x^2 + 2x^3 + 4x^2 + 6x + x^2 +2x + 3 \r\n= 3x^4 + 8x^3 + 14x^2 + 8x + 3\r\n\r\nNow plugging in x = 10 ==&gt;  3(10)^4 + 8(10)^3 + 14(10)^2 + 8(10) + 3 = 39483\r\n\r\nNow verify with a calculator that 123*321 = 39483\r\n\r\nCool, huh?\r\n\r\n<\/pre>\n<p>We can use this knowledge to multiply some\u00a0<i>really, really\u00a0<\/i>big numbers. Since we have a way to calculate them product using polynomials, the question now is this: how do we multiply these polynomials when the order is large (like order-50 or order-n)? This is where the Toom-k algorithm becomes helpful.<br \/>\nFirst, let&#8217;s represent the polynomials as arrays where the position\u00a0<i>i\u00a0<\/i>indicates the power and the value at\u00a0<i>i\u00a0<\/i>represents the coefficient.<\/p>\n<pre>3x^2 + 2x + 1\r\n\r\nwill be represented as\r\n\r\n[1, 2, 3]\r\n<\/pre>\n<p>Toom-k states that we can divide the polynomial array into sub-arrays of length (n\/k) and perform (2*k)-1 recursive calls on those sub-arrays, then recombine them in O(n) time, and have a solution. For this article I want to focus on Toom-3, or otherwise called the Toom-Cook algorithm. To simplfiy the algorithm, we&#8217;ll require the length of our input arrays to be divisible by 3. Call the two input polynomials P and Q. P and Q get partitioned into n\/3 or otherwise stated, they are divided into thirds. Call these sub-arrays A, B, C, D, E, and F where these are each of size n\/3. Create 5 more arrays of size n\/3 called G, H, J, L, M. Their values are as follows:<br \/>\nG = A+C, H = D+F, J = G-B, K = H-E, L = 2(J+A)-C, M = 2(K+D)-F<br \/>\nHere comes some serious math.<br \/>\nIn this method of representing polynomials as arrays, an order-n polynomial takes up an array of length (n+1). Like in our previous example:<\/p>\n<pre>3x^2 + 2x + 1 is order-2\r\n\r\nso n = 2, but its array representation takes up (n+1) = 3 length\r\n\r\n[1, 2, 3]\r\n<\/pre>\n<p>Since this is known, then we can determine that multiplying two polynomials together of any order-n will generate in our system of representation an array of length (2*n)-1.<br \/>\nOk, back to the Toom-3. We now create 5 more arrays of length (2*n)-1 named R, S, T, U, V. They are defined as R = AD, S = CF, T = (G+B)(H+E), U = JK, V = LM.<br \/>\nOne more set of arrays of length (2*n\/3)-1 named W, X, Y, Z and are defined as W = (V-T)\/3, X = (T-U)\/2, Y = U-S, Z = (Y-W)\/2 + 2R.<br \/>\nNow we need to recombine these arrays into the final solution form. The product P*Q is defined as follows:<br \/>\nP*Q = Rx^(4n\/3) + Zx^n + (X+Y-R)x^(2n\/3) + (X-Z)x^(n\/3) + S<br \/>\nThis formula can look confusing, but it makes sense with some code to go with it:<\/p>\n<pre>BigInt* make_array(BigInt size)\r\n{\r\n\tBigInt*res = new BigInt[size];\r\n\tfor(BigInt i = 0; i &lt; size; i ++)\r\n\t{\r\n\t\tres[i] = 0;\r\n\t}\r\n\treturn res;\r\n}\r\nBigInt* Toom3(BigInt* P, BigInt*Q, BigInt n)\r\n{\r\n\tBigInt pq_size = (2*n) -1 ;\r\n\tBigInt *PQ_Res = make_array(pq_size);\r\n\tBigInt sub_eq_size = n\/3;\r\n\tBigInt *A = new BigInt[sub_eq_size], *B =new BigInt[sub_eq_size], *C=new BigInt[sub_eq_size], *D=new BigInt[sub_eq_size], *E=new BigInt[sub_eq_size], *F=new BigInt[sub_eq_size];\r\n\tmemcpy(C,&amp;P[0], sizeof(BigInt) * sub_eq_size);\r\n\tmemcpy(B,&amp;P[sub_eq_size], sizeof(BigInt) * sub_eq_size);\r\n\tmemcpy(A,&amp;P[sub_eq_size*2], sizeof(BigInt) * sub_eq_size);\r\n\tmemcpy(F,&amp;Q[0], sizeof(BigInt) * sub_eq_size);\r\n\tmemcpy(E,&amp;Q[sub_eq_size], sizeof(BigInt) * sub_eq_size);\r\n\tmemcpy(D,&amp;Q[sub_eq_size*2], sizeof(BigInt) * sub_eq_size);\r\n\r\n\tBigInt *G = new BigInt[sub_eq_size], *H =new BigInt[sub_eq_size], *J =new BigInt[sub_eq_size], *K =new BigInt[sub_eq_size], *L =new BigInt[sub_eq_size],*M =new BigInt[sub_eq_size];\r\n\tBigInt* GpB=new BigInt[sub_eq_size], *HpE=new BigInt[sub_eq_size];\r\n\tfor(BigInt i = 0; i &lt; sub_eq_size; i++)\r\n\t{\r\n\t\tG[i] = A[i] + C[i];\r\n\t\tH[i] = D[i] + F[i];\r\n\t\tJ[i] = G[i] - B[i];\r\n\t\tK[i] = H[i] - E[i];\r\n\t\tL[i] = (2* (J[i] + A[i])) - C[i];\r\n\t\tM[i] = (2* (K[i] + D[i])) - F[i];\r\n\t\tGpB[i] = G[i] + B[i];\r\n\t\tHpE[i] = H[i] + E[i];\r\n\t}\r\n\tBigInt *R, *S, *T, *U, *V; \/\/finally!\r\n\tR = mult(A, D, sub_eq_size, sub_eq_size);\r\n\tS = mult(C, F, sub_eq_size, sub_eq_size);\r\n\tU = mult(J, K, sub_eq_size, sub_eq_size);\r\n\tV = mult(L, M, sub_eq_size, sub_eq_size);\r\n\tT = mult(GpB, HpE, sub_eq_size, sub_eq_size);\r\n\t\r\n\tBigInt *W=new BigInt[2*n\/3 -1], *X=new BigInt[2*n\/3 -1], *Y=new BigInt[2*n\/3 -1], *Z=new BigInt[2*n\/3 -1]; \/\/ i just thought i was done.\r\n\tfor(BigInt i = 0; i &lt; 2*n\/3 -1; i++)\r\n\t{\r\n\t\tW[i] = (V[i] - T[i])\/3;\r\n\t\tX[i] = (T[i] - U[i])\/2;\r\n\t\tY[i] = U[i] - S[i];\r\n\t\tZ[i] = ((Y[i] - W[i])\/2) + (2*R[i]);\r\n\t}\r\n\tfor(BigInt i = 0; i &lt; 2*n\/3 -1; i++)\r\n\t{\r\n\t\tPQ_Res[i] \t\t+= S[i];\r\n\t\tPQ_Res[i + (n\/3)]\t+= (X[i] - Z[i]);\r\n\t\tPQ_Res[i + (2*n\/3)] \t+= (X[i] + Y[i] - R[i]);\r\n\t\tPQ_Res[i + (n)] \t+= Z[i];\r\n\t\tPQ_Res[i + (4*n)\/ 3] \t+= R[i];\r\n\t}\r\n\treturn PQ_Res;\r\n}\r\n<\/pre>\n<p>This method can be analyzed in its runtime using the\u00a0<a href=\"http:\/\/en.wikipedia.org\/wiki\/Master_theorem\">Master Recurrence Theorem<\/a>. Take Toom-3 for example. Its running time is T(n) = \u03b8(1) + 5T(n\/3) + \u03b8(n). Using the Recurrence theorem we can show that the running time of Toom-3 is n<sup>log<sub>3<\/sub>5<\/sup>.For any general Toom-k, it can be shown that since we do (2*k) &#8211; 1 recursions and we split the arrays in to sub-arrays of size (n\/k), the running time of Toom-k is T(n) = \u03b8(1) + ((2*k)-1)T(n\/k) + \u03b8(n) which when used against the Recurrence theorem we show that it is of n<sup>log<sub>k<\/sub>(2*k)-1<\/sup>\u00a0time complexity. I found this very interesting and I hope you do too!!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I&#8217;ve been pretty busy with classes the past two weeks, but I&#8217;ve learned a few neat things and I&#8217;d like to share one of them. Multiplying big numbers is a problem when the numbers are\u00a0really, really\u00a0big. How big is\u00a0really, really\u00a0big? Depends on the hardware your using. But to multiply really big numbers, we represent the two multiplicands as polynomials where each term is in the form\u00a0cxn, where x is the base in the number system, c is its coefficent modifier&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[21],"tags":[60,11,22],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v16.4 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Toom-k Polynomial Multiplication - Jacob N Calvert<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jacobncalvert.com\/blog-archive\/2014\/09\/10\/toom-k-polynomial-multiplication\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Toom-k Polynomial Multiplication - Jacob N Calvert\" \/>\n<meta property=\"og:description\" content=\"I&#8217;ve been pretty busy with classes the past two weeks, but I&#8217;ve learned a few neat things and I&#8217;d like to share one of them. Multiplying big numbers is a problem when the numbers are\u00a0really, really\u00a0big. How big is\u00a0really, really\u00a0big? Depends on the hardware your using. But to multiply really big numbers, we represent the two multiplicands as polynomials where each term is in the form\u00a0cxn, where x is the base in the number system, c is its coefficent modifier&hellip;\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jacobncalvert.com\/blog-archive\/2014\/09\/10\/toom-k-polynomial-multiplication\/\" \/>\n<meta property=\"og:site_name\" content=\"Jacob N Calvert\" \/>\n<meta property=\"article:published_time\" content=\"2014-09-10T17:58:29+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2018-02-10T21:44:11+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"6 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jacobncalvert.com\/blog-archive\/#website\",\"url\":\"https:\/\/jacobncalvert.com\/blog-archive\/\",\"name\":\"Jacob N Calvert\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":\"https:\/\/jacobncalvert.com\/blog-archive\/?s={search_term_string}\",\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jacobncalvert.com\/blog-archive\/2014\/09\/10\/toom-k-polynomial-multiplication\/#webpage\",\"url\":\"https:\/\/jacobncalvert.com\/blog-archive\/2014\/09\/10\/toom-k-polynomial-multiplication\/\",\"name\":\"Toom-k Polynomial Multiplication - Jacob N Calvert\",\"isPartOf\":{\"@id\":\"https:\/\/jacobncalvert.com\/blog-archive\/#website\"},\"datePublished\":\"2014-09-10T17:58:29+00:00\",\"dateModified\":\"2018-02-10T21:44:11+00:00\",\"author\":{\"@id\":\"https:\/\/jacobncalvert.com\/blog-archive\/#\/schema\/person\/f4b22a996d41bf09ed2bbe22912a8c8a\"},\"breadcrumb\":{\"@id\":\"https:\/\/jacobncalvert.com\/blog-archive\/2014\/09\/10\/toom-k-polynomial-multiplication\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jacobncalvert.com\/blog-archive\/2014\/09\/10\/toom-k-polynomial-multiplication\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jacobncalvert.com\/blog-archive\/2014\/09\/10\/toom-k-polynomial-multiplication\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"item\":{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jacobncalvert.com\/blog-archive\/\",\"url\":\"https:\/\/jacobncalvert.com\/blog-archive\/\",\"name\":\"Home\"}},{\"@type\":\"ListItem\",\"position\":2,\"item\":{\"@id\":\"https:\/\/jacobncalvert.com\/blog-archive\/2014\/09\/10\/toom-k-polynomial-multiplication\/#webpage\"}}]},{\"@type\":\"Person\",\"@id\":\"https:\/\/jacobncalvert.com\/blog-archive\/#\/schema\/person\/f4b22a996d41bf09ed2bbe22912a8c8a\",\"name\":\"Jacob\",\"image\":{\"@type\":\"ImageObject\",\"@id\":\"https:\/\/jacobncalvert.com\/blog-archive\/#personlogo\",\"inLanguage\":\"en-US\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/64a2dd1c00cb39dfc19bb1204c87efbc?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/64a2dd1c00cb39dfc19bb1204c87efbc?s=96&d=mm&r=g\",\"caption\":\"Jacob\"},\"sameAs\":[\"https:\/\/jacobncalvert.com\"],\"url\":\"https:\/\/jacobncalvert.com\/blog-archive\/author\/jcalvert\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","_links":{"self":[{"href":"https:\/\/jacobncalvert.com\/blog-archive\/wp-json\/wp\/v2\/posts\/161"}],"collection":[{"href":"https:\/\/jacobncalvert.com\/blog-archive\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jacobncalvert.com\/blog-archive\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jacobncalvert.com\/blog-archive\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jacobncalvert.com\/blog-archive\/wp-json\/wp\/v2\/comments?post=161"}],"version-history":[{"count":1,"href":"https:\/\/jacobncalvert.com\/blog-archive\/wp-json\/wp\/v2\/posts\/161\/revisions"}],"predecessor-version":[{"id":162,"href":"https:\/\/jacobncalvert.com\/blog-archive\/wp-json\/wp\/v2\/posts\/161\/revisions\/162"}],"wp:attachment":[{"href":"https:\/\/jacobncalvert.com\/blog-archive\/wp-json\/wp\/v2\/media?parent=161"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jacobncalvert.com\/blog-archive\/wp-json\/wp\/v2\/categories?post=161"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jacobncalvert.com\/blog-archive\/wp-json\/wp\/v2\/tags?post=161"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}