Surface of revolution: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
en>Lowellian
 
moved the constant r out of the integral sign to clarify
Line 1: Line 1:
This Halloween, create a hot custom. Instead of it being a day, or days, of indulging inside your favorite sugary treats, create it a day for creating healthy resolutions.<br><br>I know what you're thinking....."There's no means [http://safedietplans.com/bmr-calculator bmr calculator] I can drink which much water!" But rest assured, we can, and the body can thank we for it. At initially, we will invest a great deal of time in the bathroom. But inside regarding 2 weeks, your body is fully hydrated and a bathroom breaks will level off. During those first limited weeks of frequent pit stops, only think of it as piece of the exercise program. Consider all of the squats you're doing, plus in the event you wear clothing like overalls, you'll be getting some wise stretching in because we pull them on plus off!<br><br>We are all topic to what exactly is called the basal metabolic rate. This is the number of calories each living person demands to survive. It is based found on the amount of calories needed to keep the organs working. Even strolling to the refrigerator for some tempting snack or a cold 1, and then back to the sofa for the upcoming TV show will be considered 'exercise' when computing the BMR. It is the amount of calories you'll burn in the event you remain inside bed all day long and do nothing.<br><br>Reduce saturated fats: They should take not more than 8 percent of your calories from saturated fats. When purchasing and cooking food an obese individual should choose on a lot more those are fat-free or lean.<br><br>Next add the calories needed for a specific exercise we will be doing for that day to a bmr. For instance a girl which weighs 165 pounds at 5'9", requires 1650 calories for BMR (body weight X 10). Let's say she is moderately active thus add another 40% to her BMR: 1650 X .40 (40%) = 660 thus 1650 + 660 = 2310.<br><br>3) Eat gradually - Whenever you eat slowly, the process of chewing and mixing foods in our mouth with saliva is the initial step in digestion. The more we chew our foods, the less work is required to digest them. For persons whom are constantly experiencing bloating, stomach pain or heartburn following eating, they are eating too fast and are causing indigestion. The different advantage of eating gradually is to prevent over eating. By eating slowing, you allow the belly to signal the mind whenever you have eaten enough before we have eaten too much. For persons that like to eat less, eating slowly is best.<br><br>Tabata training is a fairly significant strength shape of exercise. For that reason the anaerobic plus aerobic abilities usually strengthen. Aerobics is the ability for the body to take in as much oxygen because required and circulate it to the muscles of the body. However, when you may be moving too fast where the oxygen has no time to circulate, then you start to create energy anaerobically with glucose. In this method tabata training can additionally heighten stamina.
'''Toom–Cook''', sometimes known as '''Toom-3''', named after [[Andrei Toom]] and [[Stephen Cook]], is a [[multiplication algorithm]], a method of multiplying two large integers.
 
Given two large integers, ''a'' and ''b'', Toom–Cook splits up ''a'' and ''b'' into ''k'' smaller parts each of length ''l'', and performs operations on the parts. As ''k'' grows, one may combine many of the multiplication sub-operations, thus reducing the overall complexity of the algorithm. The multiplication sub-operations can then be computed recursively using Toom–Cook multiplication again, and so on. Although the terms "Toom-3" and "Toom–Cook" are sometimes incorrectly used interchangeably, Toom-3 is only a single instance of the Toom–Cook algorithm, where ''k''&nbsp;=&nbsp;3.
 
Toom-3 reduces 9 multiplications to 5, and runs in Θ(''n''<sup>log(5)/log(3)</sup>), about Θ(''n''<sup>1.465</sup>). In general, Toom-''k'' runs in Θ(''c''(''k'')&nbsp;''n<sup>e</sup>''), where ''e'' = log(2''k''&nbsp;&minus;&nbsp;1) / log(''k''), ''n<sup>e</sup>'' is the time spent on sub-multiplications, and ''c'' is the time spent on additions and multiplication by small constants.<ref name="Knuth, p. 296">Knuth, p. 296</ref> The [[Karatsuba algorithm]] is a special case of Toom–Cook, where the number is split into two smaller ones. It reduces 4 multiplications to 3 and so operates at Θ(''n''<sup>log(3)/log(2)</sup>), which is about Θ(''n''<sup>1.585</sup>). Ordinary long multiplication is equivalent to Toom-1, with complexity Θ(''n''<sup>2</sup>).
 
Although the exponent ''e'' can be set arbitrarily close to 1 by increasing ''k'', the function ''c'' unfortunately grows very rapidly.<ref name="Knuth, p. 296"/><ref>Crandall & Pomerance, p. 474</ref> The growth rate for mixed-level Toom-Cook schemes was still an open research problem in 2005.<ref>Crandall & Pomerance, p. 536</ref> An implementation described by [[Donald Knuth]] achieves the time complexity Θ(''n''&nbsp;2<sup>√(2&nbsp;log&nbsp;''n'')</sup>&nbsp;log&nbsp;''n'').<ref>Knuth, p. 302</ref>
 
Due to its overhead, Toom–Cook is slower than long multiplication with small numbers, and it is therefore typically used for intermediate-size multiplications, before the asymptotically faster [[Schönhage–Strassen algorithm]] (with complexity Θ(''n''&nbsp;log&nbsp;''n''&nbsp;log&nbsp;log&nbsp;''n'')) becomes practical.
 
Toom first described this algorithm in 1963, and Cook published an improved algorithm in his PhD thesis in 1966.<ref>[http://cr.yp.to/bib/1966/cook.html Positive Results], chapter III of Stephen A. Cook: ''On the Minimum Computation Time of Functions''.</ref>
 
==Details==
This section discusses exactly how to perform Toom-''k'' for any given value of ''k'', and is a simplification of a description of Toom–Cook polynomial multiplication described by Marco Bodrato.<ref name="Bodrato2007">Marco Bodrato. Towards Optimal Toom–Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0. In ''WAIFI'07 proceedings'', volume 4547 of LNCS, pages 116&ndash;133. June 21&ndash;22, 2007. [http://bodrato.it/papers/#WAIFI2007 author website]</ref> The algorithm has five main steps:
# [[Toom–Cook multiplication#Splitting|Splitting]]
# [[Toom–Cook multiplication#Evaluation|Evaluation]]
# [[Toom–Cook multiplication#Pointwise multiplication|Pointwise multiplication]]
# [[Toom–Cook multiplication#Interpolation|Interpolation]]
# [[Toom–Cook multiplication#Recomposition|Recomposition]]
 
In a typical large integer implementation, each integer is represented as a sequence of digits in [[positional notation]], with the base or radix set to some (typically large) value ''b''; for this example we use ''b'' = 10000, so that each digit corresponds to a group of four decimal digits (in a computer implementation, ''b'' would typically be a power of 2 instead). Say the two integers being multiplied are:
 
{|
|''m'' || = ||12||3456||7890||1234||5678||9012
|-
|''n'' || =
|align=right|9||8765||4321||9876||5432||1098.
|}
 
These are much smaller than would normally be processed with Toom–Cook (grade-school multiplication would be faster) but they will serve to illustrate the algorithm.
 
=== Splitting ===
The first step is to select the base ''B'' = ''b''<sup>''i''</sup>, such that the number of digits of both ''m'' and ''n'' in base ''B'' is at most ''k'' (e.g., 3 in Toom-3). A typical choice for ''i'' is given by:
 
:<math>i = \max\{{\lfloor}{\lfloor}\log_b m{\rfloor}/k{\rfloor}, {\lfloor}{\lfloor}\log_b n{\rfloor}/k{\rfloor}\} + 1.</math>
 
In our example we'll be doing Toom-3, so we choose ''B'' = ''b''<sup>2</sup> = 10<sup>8</sup>. We then separate ''m'' and ''n'' into their base ''B'' digits ''m''<sub>''i''</sub>, ''n''<sub>''i''</sub>:
 
:<math>
\begin{align}
m_2 & {} = 123456 \\
m_1 & {} = 78901234 \\
m_0 & {} = 56789012 \\
n_2 & {} = 98765 \\
n_1 & {} = 43219876 \\
n_0 & {} = 54321098 \\
\end{align}
</math>
 
We then use these digits as coefficients in degree ''k''&minus;1 polynomials ''p'' and ''q'', with the property that ''p''(''B'') = ''m'' and ''q''(''B'') = ''n'':
 
:<math>p(x) = m_2x^2 + m_1x + m_0 = 123456x^2 + 78901234x + 56789012 \, </math>
:<math>q(x) = n_2x^2 + n_1x + n_0 =  98765x^2 + 43219876x + 54321098 \, </math>
 
The purpose of defining these polynomials is that if we can compute their product ''r''(''x'')&nbsp;=&nbsp;''p''(''x'')''q''(''x''), our answer will be ''r''(''B'')&nbsp;=&nbsp;''m''&times;''n''.
 
In the case where the numbers being multiplied are of different sizes, it's useful to use different values of ''k'' for ''m'' and ''n'', which we'll call ''k''<sub>''m''</sub> and ''k''<sub>''n''</sub>. For example, the algorithm "Toom-2.5" refers to Toom&ndash;Cook with ''k''<sub>''m''</sub> = 3 and ''k''<sub>''n''</sub> = 2. In this case the ''i'' in ''B'' = ''b''<sup>''i''</sup> is typically chosen by:
 
:<math>i = \max\{{\lfloor}{\lceil}\log_b m{\rceil}/k_m{\rfloor}, {\lfloor}{\lceil}\log_b n{\rceil}/k_n{\rfloor}\}.</math>
 
=== Evaluation ===
The Toom–Cook approach to computing the polynomial product ''p''(''x'')''q''(''x'') is a commonly used one. Note that a polynomial of degree ''d'' is uniquely determined by ''d''&nbsp;+&nbsp;1 points (for example, a line - polynomial of degree one is specified by two points). The idea is to evaluate ''p(·)'' and ''q(·)'' at various points. Then multiply their values at these points to get points on the product polynomial. Finally interpolate to find its coefficients.
 
Since deg(''pq'') = deg(''p'') + deg(''q''), we will need deg(''p'')&nbsp;+&nbsp;deg(''q'')&nbsp;+&nbsp;1 = ''k''<sub>''m''</sub>&nbsp;+&nbsp;''k''<sub>''n''</sub>&nbsp;&minus;&nbsp;1 points to determine the final result. Call this ''d''. In the case of Toom-3, ''d'' = 5. The algorithm will work no matter what points are chosen (with a few small exceptions, see matrix invertibility requirement in [[Toom–Cook multiplication#Interpolation|Interpolation]]), but in the interest of simplifying the algorithm it's better to choose small integer values like 0, 1, &minus;1, and &minus;2.
 
One unusual point value that is frequently used is infinity, written ∞ or 1/0. To "evaluate" a polynomial ''p'' at infinity actually means to take the limit of ''p''(''x'')/''x''<sup>deg ''p''</sup> as ''x'' goes to infinity. Consequently, ''p''(∞) is always the value of its highest-degree coefficient (in the example above coefficient m<sub>2</sub>).
 
In our Toom-3 example, we will use the points 0, 1, &minus;1, &minus;2, and ∞. These choices simplify evaluation, producing the formulas:
 
:<math>
\begin{align}
p(0) & {} = m_0 + m_1(0) + m_2(0)^2 = m_0 \\
p(1) & {} = m_0 + m_1(1) + m_2(1)^2 = m_0 + m_1 + m_2 \\
p(-1) & {} = m_0 + m_1(-1) + m_2(-1)^2 = m_0 - m_1 + m_2 \\
p(-2) & {} = m_0 + m_1(-2) + m_2(-2)^2 = m_0 - 2m_1 + 4m_2 \\
p(\infty) & {} = m_2
\end{align}
</math>
 
and analogously for ''q''. In our example, the values we get are:
 
{|
|''p''(0) || = || ''m''<sub>0</sub> || = || 56789012 || = || 56789012
|-
|''p''(1) || = || ''m''<sub>0</sub> + ''m''<sub>1</sub> + ''m''<sub>2</sub> || = || 56789012 + 78901234 + 123456 || = || 135813702
|-
|''p''(&minus;1) || = || ''m''<sub>0</sub> &minus; ''m''<sub>1</sub> + ''m''<sub>2</sub> || = || 56789012 &minus; 78901234 + 123456 || = || &minus;21988766
|-
|''p''(&minus;2) || = || ''m''<sub>0</sub> &minus; 2''m''<sub>1</sub> + 4''m''<sub>2</sub> || = || 56789012 &minus; 2&times;78901234 + 4&times;123456 || = || &minus;100519632
|-
|''p''(∞) || = || ''m''<sub>2</sub> || = || 123456 || = || 123456
|-
|''q''(0) || = || ''n''<sub>0</sub> || = || 54321098 || = || 54321098
|-
|''q''(1) || = || ''n''<sub>0</sub> + ''n''<sub>1</sub> + ''n''<sub>2</sub> || = || 54321098 + 43219876 + 98765 || = || 97639739
|-
|''q''(&minus;1) || = || ''n''<sub>0</sub> &minus; ''n''<sub>1</sub> + ''n''<sub>2</sub> || = || 54321098 &minus; 43219876 + 98765 || = || 11199987
|-
|''q''(&minus;2) || = || ''n''<sub>0</sub> &minus; 2''n''<sub>1</sub> + 4''n''<sub>2</sub> || = || 54321098 &minus; 2&times;43219876 + 4&times;98765 || = || &minus;31723594
|-
|''q''(∞) || = || ''n''<sub>2</sub> || = || 98765 || = || 98765.
|}
 
As shown, these values may be negative.
 
For the purpose of later explanation, it will be useful to view this evaluation process as a matrix-vector multiplication, where each row of the matrix contains powers of one of the evaluation points, and the vector contains the coefficients of the polynomial:
 
: <math>
\left(\begin{matrix}p(0) \\ p(1) \\ p(-1) \\ p(-2) \\ p(\infty)\end{matrix}\right) =
\left(\begin{matrix}
0^0 & 0^1 & 0^2 \\
1^0 & 1^1 & 1^2 \\
(-1)^0 & (-1)^1 & (-1)^2 \\
(-2)^0 & (-2)^1 & (-2)^2 \\
0 & 0 & 1
\end{matrix}\right)
\left(\begin{matrix}m_0 \\ m_1 \\ m_2\end{matrix}\right) =
\left(\begin{matrix}
1 &  0 & 0 \\
1 &  1 & 1 \\
1 & -1 & 1 \\
1 & -2 & 4 \\
0 &  0 & 1
\end{matrix}\right)
\left(\begin{matrix}m_0 \\ m_1 \\ m_2\end{matrix}\right).
</math>
 
The dimensions of the matrix are ''d'' by ''k''<sub>''m''</sub> for ''p'' and ''d'' by ''k''<sub>''n''</sub> for ''q''. The row for infinity is always all zero except for a 1 in the last column.
 
==== Faster evaluation ====
Multipoint evaluation can be obtained faster than with the above formulas. The number of elementary operations (addition/subtraction) can be reduced. The sequence given by Bodrato<ref name="Bodrato2007"/> for Toom-3, executed here over the first operand (polynomial ''p'') of the running example is the following:
 
{|
|''p''<sub>0</sub> || ← || ''m''<sub>0</sub> + ''m''<sub>2</sub> || = || 56789012 + 123456 || = || 56912468
|-
|''p''(0) || = || ''m''<sub>0</sub> || = || 56789012 || = || 56789012
|-
|''p''(1) || = || ''p''<sub>0</sub> + ''m''<sub>1</sub> || = || 56912468 + 78901234 || = || 135813702
|-
|''p''(&minus;1) || = || ''p''<sub>0</sub> &minus; ''m''<sub>1</sub> || = || 56912468 &minus; 78901234 || = || &minus;21988766
|-
|''p''(&minus;2) || = || (''p''(&minus;1) + ''m''<sub>2</sub>)&times;2 &minus; ''m''<sub>0</sub> || = || (&minus; 21988766 + 123456 )&times;2 &minus; 56789012 || = || &minus; 100519632
|-
|''p''(∞) || = || ''m''<sub>2</sub> || = || 123456 || = || 123456.
|}
 
This sequence requires five addition/subtraction operations, one less than the straightforward evaluation. Moreover the multiplication by 4 in the calculation of ''p''(&minus;2) was saved.
 
=== Pointwise multiplication ===
Unlike multiplying the polynomials ''p''(·) and ''q''(·), multiplying the evaluated values ''p''(''a'') and ''q''(''a'') just involves multiplying integers &mdash; a smaller instance of the original problem. We recursively invoke our multiplication procedure to multiply each pair of evaluated points. In practical implementations, as the operands become smaller, the algorithm will switch to the [[Multiplication algorithm#Long multiplication|Schoolbook long multiplication]]. Letting ''r'' be the product polynomial, in our example we have:
 
{|
|''r''(0) || = || ''p''(0)''q''(0) || = || 56789012 &times; 54321098 || = || 3084841486175176
|-
|''r''(1) || = || ''p''(1)''q''(1) || = || 135813702 &times; 97639739 || = || 13260814415903778
|-
|''r''(&minus;1) || = || ''p''(&minus;1)''q''(&minus;1) || = || &minus;21988766 &times; 11199987 || = || &minus;246273893346042
|-
|''r''(&minus;2) || = || ''p''(&minus;2)''q''(&minus;2) || = || &minus;100519632 &times; &minus;31723594 || = || 3188843994597408
|-
|''r''(∞) || = || ''p''(∞)''q''(∞) || = || 123456 &times; 98765 || = || 12193131840.
|}
 
As shown, these can also be negative. For large enough numbers, this is the most expensive step, the only step that is not linear in the sizes of ''m'' and ''n''.
 
=== Interpolation ===
This is the most complex step, the reverse of the evaluation step: given our ''d'' points on the product polynomial ''r''(·), we need to determine its coefficients. In other words, we want to solve this matrix equation for the vector on the right-hand side:
 
: <math>
\begin{align}
\left(\begin{matrix}r(0) \\ r(1) \\ r(-1) \\ r(-2) \\ r(\infty)\end{matrix}\right) & {} =
\left(\begin{matrix}
0^0 & 0^1 & 0^2 & 0^3 & 0^4 \\
1^0 & 1^1 & 1^2 & 1^3 & 1^4 \\
(-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
\end{matrix}\right)
\left(\begin{matrix}r_0 \\ r_1 \\ r_2 \\ r_3 \\ r_4\end{matrix}\right) \\
& {} =
\left(\begin{matrix}
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
\end{matrix}\right)
\left(\begin{matrix}r_0 \\ r_1 \\ r_2 \\ r_3 \\ r_4\end{matrix}\right).
\end{align}
</math>
 
This matrix is constructed the same way as the one in the evaluation step, except that it's ''d''&times;''d''. We could solve this equation with a technique like [[Gaussian elimination]], but this is too expensive. Instead, we use the fact that, provided the evaluation points were chosen suitably, this matrix is invertible, and so:
 
: <math>
\begin{align}
\left(\begin{matrix}r_0 \\ r_1 \\ r_2 \\ r_3 \\ r_4\end{matrix}\right) & {} =
\left(\begin{matrix}
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
\end{matrix}\right)^{-1}
\left(\begin{matrix}r(0) \\ r(1) \\ r(-1) \\ r(-2) \\ r(\infty)\end{matrix}\right) \\
&  {} =
\left(\begin{matrix}
  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
\end{matrix}\right)
\left(\begin{matrix}r(0) \\ r(1) \\ r(-1) \\ r(-2) \\ r(\infty)\end{matrix}\right).
\end{align}
</math>
 
All that remains is to compute this matrix-vector product. Although the matrix contains fractions, the resulting coefficients will be integers &mdash; so this can all be done with integer arithmetic, just additions, subtractions, and multiplication/division by small constants. A difficult design challenge in Toom–Cook is to find an efficient sequence of operations to compute this product; one sequence given by Bodrato<ref name="Bodrato2007" /> for Toom-3 is the following, executed here over the running example:
 
{|
|''r''<sub>0</sub> || ← || ''r''(0) || = || 3084841486175176
|-
|''r''<sub>4</sub> || ← || ''r''(∞) || = || 12193131840
|-
|''r''<sub>3</sub>  || ← ||  (''r''(&minus;2) &minus; ''r''(1))/3 || = || (3188843994597408 &minus; 13260814415903778)/3
|-
| || || || = || &minus;3357323473768790
|-
|''r''<sub>1</sub>  || ← ||  (''r''(1) &minus; ''r''(&minus;1))/2 || = || (13260814415903778 &minus; (&minus;246273893346042))/2
|-
| || || || = || 6753544154624910
|-
|''r''<sub>2</sub>  || ← ||  ''r''(&minus;1) &minus; ''r''(0) || = || &minus;246273893346042 &minus; 3084841486175176
|-
| || || || = || &minus;3331115379521218
|-
|''r''<sub>3</sub>  || ← ||  (''r''<sub>2</sub> &minus; ''r''<sub>3</sub>)/2&nbsp;+ 2''r''(∞) || = || (&minus;3331115379521218 &minus; (&minus;3357323473768790))/2&nbsp;+ 2&times;12193131840 
|-
| || || || = || 13128433387466
|-
|''r''<sub>2</sub>  || ← ||  ''r''<sub>2</sub> + ''r''<sub>1</sub> &minus; ''r''<sub>4</sub> || = || &minus;3331115379521218 + 6753544154624910 &minus; 12193131840 
|-
| || || || = || 3422416581971852
|-
|''r''<sub>1</sub>  || ← ||  ''r''<sub>1</sub> &minus; ''r''<sub>3</sub> || = || 6753544154624910 &minus; 13128433387466 
|-
| || || || = || 6740415721237444.
|}
 
We now know our product polynomial ''r'':
 
: <math>
\begin{align}
r(x) & {} = 3084841486175176 \\
    & {} \quad + 6740415721237444x \\
    & {} \quad + 3422416581971852x^2 \\
    & {} \quad + 13128433387466x^3 \\
    & {} \quad + 12193131840x^4.
\end{align}
</math>
 
If we were using different ''k''<sub>''m''</sub>, ''k''<sub>''n''</sub>, or evaluation points, the matrix and so our interpolation strategy would change; but it does not depend on the inputs and so can be hard-coded for any given set of parameters.
 
=== Recomposition ===
 
Finally, we evaluate r(B) to obtain our final answer. This is straightforward since B is a power of ''b'' and so the multiplications by powers of B are all shifts by a whole number of digits in base ''b''. In the running example b = 10<sup>4</sup> and B = b<sup>2</sup> = 10<sup>8</sup>.
 
{|
|  ||  ||    ||    ||    ||    ||    ||    ||3084||8414||8617||5176
|-
|  ||  ||    ||    ||    ||    ||6740||4157||2123||7444||    ||
|-
|  ||  ||    ||    ||3422||4165||8197||1852||    ||    ||    ||
|-
|  || 
|align=right|  13||1284||3338||7466||    ||    ||    ||    ||    ||
|-
| + ||121||9313||1840||    ||    ||    ||    ||    ||    ||    ||
|-
|colspan=100|<hr>
|-
|  ||121||9326||3124||6761||1632||4937||6009||5208||5858||8617||5176
|}
 
And this is in fact the product of 1234567890123456789012 and 987654321987654321098.
 
==Interpolation matrices for various ''k''==
 
Here we give common interpolation matrices for a few different common small values of ''k''<sub>''m''</sub> and ''k''<sub>''n''</sub>.
 
=== Toom-1 ===
Toom-1 (''k''<sub>''m''</sub> = ''k''<sub>''n''</sub> = 1) requires 1 evaluation point, here chosen to be 0. It degenerates to long multiplication, with an interpolation matrix of the identity matrix:
 
: <math>\left(\begin{matrix}1\end{matrix}\right)^{-1} =
\left(\begin{matrix}1\end{matrix}\right).</math>
 
=== Toom-1.5 ===
Toom-1.5 (''k''<sub>''m''</sub> = 2, ''k''<sub>''n''</sub> = 1) requires 2 evaluation points, here chosen to be 0 and ∞. Its interpolation matrix is then the identity matrix:
 
: <math>\left(\begin{matrix}1 & 0 \\ 0 & 1\end{matrix}\right)^{-1} =
\left(\begin{matrix}1 & 0 \\ 0 & 1\end{matrix}\right).</math>
 
=== Toom-2 ===
Toom-2 (''k''<sub>''m''</sub> = 2, ''k''<sub>''n''</sub> = 2) requires 3 evaluation points, here chosen to be 0, 1, and ∞. It is the same as [[Karatsuba multiplication]], with an interpolation matrix of:
 
: <math>\left(\begin{matrix}
1 & 0 & 0 \\
1 & 1 & 1 \\
0 & 0 & 1
\end{matrix}\right)^{-1} =
\left(\begin{matrix}
1 & 0 & 0 \\
-1 & 1 & -1 \\
0 & 0 & 1
\end{matrix}\right).</math>
 
=== Toom-2.5 ===
Toom-2.5 (''k''<sub>''m''</sub> = 3, ''k''<sub>''n''</sub> = 2) requires 4 evaluation points, here chosen to be 0, 1, -1, and ∞. It then has an interpolation matrix of:
 
: <math>\left(\begin{matrix}
1 &  0 & 0 &  0 \\
1 &  1 & 1 &  1 \\
1 & -1 & 1 & -1 \\
0 &  0 & 0 &  1
\end{matrix}\right)^{-1} =
\left(\begin{matrix}
1 & 0 & 0 & 0 \\
0 & 1/2 & -1/2 & -1 \\
-1 & 1/2 & 1/2 & 0 \\
0 & 0 & 0 & 1
\end{matrix}\right).</math>
 
==Notes==
<references/>
 
==References==
* D. Knuth. ''[[The Art of Computer Programming]]'', Volume 2. Third Edition, Addison-Wesley, 1997. Section 4.3.3.A: Digital methods, pg.294.
* R. Crandall & C. Pomerance. ''Prime Numbers – A Computational Perspective''. Second Edition, Springer, 2005. Section 9.5.1: Karatsuba and Toom–Cook methods, pg.473.
* M. Bodrato. ''[http://bodrato.it/toom-cook/ Toward Optimal Toom–Cook Multiplication...]''. In WAIFI'07, Springer, 2007.
 
== External links ==
* [http://gmplib.org/manual/Toom-3_002dWay-Multiplication.html Toom-Cook 3-Way Multiplication from GMP Documentations]
 
{{Number-theoretic algorithms}}
 
{{DEFAULTSORT:Toom-Cook multiplication}}
[[Category:Computer arithmetic algorithms]]
[[Category:Multiplication]]

Revision as of 20:29, 29 August 2013

Toom–Cook, sometimes known as Toom-3, named after Andrei Toom and Stephen Cook, is a multiplication algorithm, a method of multiplying two large integers.

Given two large integers, a and b, Toom–Cook splits up a and b into k smaller parts each of length l, and performs operations on the parts. As k grows, one may combine many of the multiplication sub-operations, thus reducing the overall complexity of the algorithm. The multiplication sub-operations can then be computed recursively using Toom–Cook multiplication again, and so on. Although the terms "Toom-3" and "Toom–Cook" are sometimes incorrectly used interchangeably, Toom-3 is only a single instance of the Toom–Cook algorithm, where k = 3.

Toom-3 reduces 9 multiplications to 5, and runs in Θ(nlog(5)/log(3)), about Θ(n1.465). In general, Toom-k runs in Θ(c(kne), where e = log(2k − 1) / log(k), ne is the time spent on sub-multiplications, and c is the time spent on additions and multiplication by small constants.[1] The Karatsuba algorithm is a special case of Toom–Cook, where the number is split into two smaller ones. It reduces 4 multiplications to 3 and so operates at Θ(nlog(3)/log(2)), which is about Θ(n1.585). Ordinary long multiplication is equivalent to Toom-1, with complexity Θ(n2).

Although the exponent e can be set arbitrarily close to 1 by increasing k, the function c unfortunately grows very rapidly.[1][2] The growth rate for mixed-level Toom-Cook schemes was still an open research problem in 2005.[3] An implementation described by Donald Knuth achieves the time complexity Θ(n 2√(2 log n) log n).[4]

Due to its overhead, Toom–Cook is slower than long multiplication with small numbers, and it is therefore typically used for intermediate-size multiplications, before the asymptotically faster Schönhage–Strassen algorithm (with complexity Θ(n log n log log n)) becomes practical.

Toom first described this algorithm in 1963, and Cook published an improved algorithm in his PhD thesis in 1966.[5]

Details

This section discusses exactly how to perform Toom-k for any given value of k, and is a simplification of a description of Toom–Cook polynomial multiplication described by Marco Bodrato.[6] The algorithm has five main steps:

  1. Splitting
  2. Evaluation
  3. Pointwise multiplication
  4. Interpolation
  5. Recomposition

In a typical large integer implementation, each integer is represented as a sequence of digits in positional notation, with the base or radix set to some (typically large) value b; for this example we use b = 10000, so that each digit corresponds to a group of four decimal digits (in a computer implementation, b would typically be a power of 2 instead). Say the two integers being multiplied are:

m = 12 3456 7890 1234 5678 9012
n = 9 8765 4321 9876 5432 1098.

These are much smaller than would normally be processed with Toom–Cook (grade-school multiplication would be faster) but they will serve to illustrate the algorithm.

Splitting

The first step is to select the base B = bi, such that the number of digits of both m and n in base B is at most k (e.g., 3 in Toom-3). A typical choice for i is given by:

i=max{logbm/k,logbn/k}+1.

In our example we'll be doing Toom-3, so we choose B = b2 = 108. We then separate m and n into their base B digits mi, ni:

m2=123456m1=78901234m0=56789012n2=98765n1=43219876n0=54321098

We then use these digits as coefficients in degree k−1 polynomials p and q, with the property that p(B) = m and q(B) = n:

p(x)=m2x2+m1x+m0=123456x2+78901234x+56789012
q(x)=n2x2+n1x+n0=98765x2+43219876x+54321098

The purpose of defining these polynomials is that if we can compute their product r(x) = p(x)q(x), our answer will be r(B) = m×n.

In the case where the numbers being multiplied are of different sizes, it's useful to use different values of k for m and n, which we'll call km and kn. For example, the algorithm "Toom-2.5" refers to Toom–Cook with km = 3 and kn = 2. In this case the i in B = bi is typically chosen by:

i=max{logbm/km,logbn/kn}.

Evaluation

The Toom–Cook approach to computing the polynomial product p(x)q(x) is a commonly used one. Note that a polynomial of degree d is uniquely determined by d + 1 points (for example, a line - polynomial of degree one is specified by two points). The idea is to evaluate p(·) and q(·) at various points. Then multiply their values at these points to get points on the product polynomial. Finally interpolate to find its coefficients.

Since deg(pq) = deg(p) + deg(q), we will need deg(p) + deg(q) + 1 = km + kn − 1 points to determine the final result. Call this d. In the case of Toom-3, d = 5. The algorithm will work no matter what points are chosen (with a few small exceptions, see matrix invertibility requirement in Interpolation), but in the interest of simplifying the algorithm it's better to choose small integer values like 0, 1, −1, and −2.

One unusual point value that is frequently used is infinity, written ∞ or 1/0. To "evaluate" a polynomial p at infinity actually means to take the limit of p(x)/xdeg p as x goes to infinity. Consequently, p(∞) is always the value of its highest-degree coefficient (in the example above coefficient m2).

In our Toom-3 example, we will use the points 0, 1, −1, −2, and ∞. These choices simplify evaluation, producing the formulas:

p(0)=m0+m1(0)+m2(0)2=m0p(1)=m0+m1(1)+m2(1)2=m0+m1+m2p(1)=m0+m1(1)+m2(1)2=m0m1+m2p(2)=m0+m1(2)+m2(2)2=m02m1+4m2p()=m2

and analogously for q. In our example, the values we get are:

p(0) = m0 = 56789012 = 56789012
p(1) = m0 + m1 + m2 = 56789012 + 78901234 + 123456 = 135813702
p(−1) = m0m1 + m2 = 56789012 − 78901234 + 123456 = −21988766
p(−2) = m0 − 2m1 + 4m2 = 56789012 − 2×78901234 + 4×123456 = −100519632
p(∞) = m2 = 123456 = 123456
q(0) = n0 = 54321098 = 54321098
q(1) = n0 + n1 + n2 = 54321098 + 43219876 + 98765 = 97639739
q(−1) = n0n1 + n2 = 54321098 − 43219876 + 98765 = 11199987
q(−2) = n0 − 2n1 + 4n2 = 54321098 − 2×43219876 + 4×98765 = −31723594
q(∞) = n2 = 98765 = 98765.

As shown, these values may be negative.

For the purpose of later explanation, it will be useful to view this evaluation process as a matrix-vector multiplication, where each row of the matrix contains powers of one of the evaluation points, and the vector contains the coefficients of the polynomial:

(p(0)p(1)p(1)p(2)p())=(000102101112(1)0(1)1(1)2(2)0(2)1(2)2001)(m0m1m2)=(100111111124001)(m0m1m2).

The dimensions of the matrix are d by km for p and d by kn for q. The row for infinity is always all zero except for a 1 in the last column.

Faster evaluation

Multipoint evaluation can be obtained faster than with the above formulas. The number of elementary operations (addition/subtraction) can be reduced. The sequence given by Bodrato[6] for Toom-3, executed here over the first operand (polynomial p) of the running example is the following:

p0 m0 + m2 = 56789012 + 123456 = 56912468
p(0) = m0 = 56789012 = 56789012
p(1) = p0 + m1 = 56912468 + 78901234 = 135813702
p(−1) = p0m1 = 56912468 − 78901234 = −21988766
p(−2) = (p(−1) + m2)×2 − m0 = (− 21988766 + 123456 )×2 − 56789012 = − 100519632
p(∞) = m2 = 123456 = 123456.

This sequence requires five addition/subtraction operations, one less than the straightforward evaluation. Moreover the multiplication by 4 in the calculation of p(−2) was saved.

Pointwise multiplication

Unlike multiplying the polynomials p(·) and q(·), multiplying the evaluated values p(a) and q(a) just involves multiplying integers — a smaller instance of the original problem. We recursively invoke our multiplication procedure to multiply each pair of evaluated points. In practical implementations, as the operands become smaller, the algorithm will switch to the Schoolbook long multiplication. Letting r be the product polynomial, in our example we have:

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.

As shown, these can also be negative. For large enough numbers, this is the most expensive step, the only step that is not linear in the sizes of m and n.

Interpolation

This is the most complex step, the reverse of the evaluation step: given our d points on the product polynomial r(·), we need to determine its coefficients. In other words, we want to solve this matrix equation for the vector on the right-hand side:

(r(0)r(1)r(1)r(2)r())=(00010203041011121314(1)0(1)1(1)2(1)3(1)4(2)0(2)1(2)2(2)3(2)400001)(r0r1r2r3r4)=(10000111111111112481600001)(r0r1r2r3r4).

This matrix is constructed the same way as the one in the evaluation step, except that it's d×d. We could solve this equation with a technique like Gaussian elimination, but this is too expensive. Instead, we use the fact that, provided the evaluation points were chosen suitably, this matrix is invertible, and so:

(r0r1r2r3r4)=(10000111111111112481600001)1(r(0)r(1)r(1)r(2)r())=(100001/21/311/6211/21/2011/21/61/21/6200001)(r(0)r(1)r(1)r(2)r()).

All that remains is to compute this matrix-vector product. Although the matrix contains fractions, the resulting coefficients will be integers — so this can all be done with integer arithmetic, just additions, subtractions, and multiplication/division by small constants. A difficult design challenge in Toom–Cook is to find an efficient sequence of operations to compute this product; one sequence given by Bodrato[6] for Toom-3 is the following, executed here over the running 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 (r2r3)/2 + 2r(∞) = (−3331115379521218 − (−3357323473768790))/2 + 2×12193131840
= 13128433387466
r2 r2 + r1r4 = −3331115379521218 + 6753544154624910 − 12193131840
= 3422416581971852
r1 r1r3 = 6753544154624910 − 13128433387466
= 6740415721237444.

We now know our product polynomial r:

r(x)=3084841486175176+6740415721237444x+3422416581971852x2+13128433387466x3+12193131840x4.

If we were using different km, kn, or evaluation points, the matrix and so our interpolation strategy would change; but it does not depend on the inputs and so can be hard-coded for any given set of parameters.

Recomposition

Finally, we evaluate r(B) to obtain our final answer. This is straightforward since B is a power of b and so the multiplications by powers of B are all shifts by a whole number of digits in base b. In the running example b = 104 and B = b2 = 108.

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

And this is in fact the product of 1234567890123456789012 and 987654321987654321098.

Interpolation matrices for various k

Here we give common interpolation matrices for a few different common small values of km and kn.

Toom-1

Toom-1 (km = kn = 1) requires 1 evaluation point, here chosen to be 0. It degenerates to long multiplication, with an interpolation matrix of the identity matrix:

(1)1=(1).

Toom-1.5

Toom-1.5 (km = 2, kn = 1) requires 2 evaluation points, here chosen to be 0 and ∞. Its interpolation matrix is then the identity matrix:

(1001)1=(1001).

Toom-2

Toom-2 (km = 2, kn = 2) requires 3 evaluation points, here chosen to be 0, 1, and ∞. It is the same as Karatsuba multiplication, with an interpolation matrix of:

(100111001)1=(100111001).

Toom-2.5

Toom-2.5 (km = 3, kn = 2) requires 4 evaluation points, here chosen to be 0, 1, -1, and ∞. It then has an interpolation matrix of:

(1000111111110001)1=(100001/21/2111/21/200001).

Notes

  1. 1.0 1.1 Knuth, p. 296
  2. Crandall & Pomerance, p. 474
  3. Crandall & Pomerance, p. 536
  4. Knuth, p. 302
  5. Positive Results, chapter III of Stephen A. Cook: On the Minimum Computation Time of Functions.
  6. 6.0 6.1 6.2 Marco Bodrato. Towards Optimal Toom–Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0. In WAIFI'07 proceedings, volume 4547 of LNCS, pages 116–133. June 21–22, 2007. author website

References

  • D. Knuth. The Art of Computer Programming, Volume 2. Third Edition, Addison-Wesley, 1997. Section 4.3.3.A: Digital methods, pg.294.
  • R. Crandall & C. Pomerance. Prime Numbers – A Computational Perspective. Second Edition, Springer, 2005. Section 9.5.1: Karatsuba and Toom–Cook methods, pg.473.
  • M. Bodrato. Toward Optimal Toom–Cook Multiplication.... In WAIFI'07, Springer, 2007.

External links

Template:Number-theoretic algorithms