ดูต้นฉบับสำหรับ การคูณของทูม-คุก

{{เก็บกวาด}}
{{ลิงก์ไปภาษาอื่น}}

'''การคูณของทูม-คุก''' ({{langx|en|Toom–Cook multiplication}}) ตั้งชื่อตามผู้คิดค้นคือ [[:en:Andrei Toom|อังเดร ทูม]] และ [[:en:Stephen Cook|สตีเฟน คุก]] บางครั้งอัลกอลิทึมนี้จะถูกเรียกว่า '''ทูม - 3''' ซึ่งเป็นวิธีการ คูณเลขจำนวนเต็มขนาดใหญ่ 2 จำนวน

ถ้าเรามีเลขจำนวนเต็ม 2 จำนวนขนาดใหญ่ให้ชื่อว่า <math>a</math> กับ <math>b</math> และทั้งสองค่านี้จะถูกแบ่งเป็นส่วนย่อยๆจำนวน <math>k</math> ส่วน และความยาว <math>l</math> โดยอัลกอลิทึมของ '''ทูม - 3''' เสนอว่าให้แบ่งจำนวนเหล่านี้เป็นส่วนย่อยจำนวน 3 ส่วน <math>(k=3)</math> เพื่อให้ความซับซ้อนของวิธีนี้ลดลง แต่ในความจริงแล้วเราสามารถที่จะแบ่งจำนวนนี้ได้มากกว่า 3 ส่วน แต่ความซับซ้อนของอัลกอลิทึมก็จะเพิ่มขึ้นเช่นกัน

อัลกอลิทึม'''ทูม - 3''' นี้ จะช่วยลดการคูณเลขจากการคูณเลขแบบปกติจำนวน 9 ครั้งเหลือเพียง 5 ครั้งเท่านั้น ทำให้เวลาลดลงจาก <math>\Theta (n^{\frac{\log (9)}{\log (3)}}) </math> มีค่าประมาณ <math>\Theta (n^2)</math> เหลือเพียง <math>\Theta (n^{\frac{\log (5)}{\log (3)}})</math> มีค่าประมาณ <math>\Theta (n^{1.465})</math> ซึ่งกระบวนการนี้หาได้จากวิธีการคำนวณ '''ทูม - k''' คือ <math> \Theta (c(k) n^{e})</math> เมื่อ <math>e = \frac{\log (2k-1)}{\log (k)}</math> โดยส่วนของ <math>n^{e}</math> คือเวลาของการคูณส่วนย่อยหรือส่วนของอัลกอลิทึมของทูม และ <math>c(k)</math> คือเวลาที่ใช้ไปกับการคูณจำนวนขนาดเล็กย่อยๆซึ่งเป็นกระบวนการในการทำอัลกอลิทึมนี้นั่นเอง ซึ่งหากเราใช้ '''ทูม - 3''' แล้วจะได้ <math>e = \frac{\log (2 \times 3-1)}{\log (3)}</math> และ <math>c (3) = 1</math> นั่นก็คือ <math>\Theta (n^{\frac{\log (5)}{\log (3)}})</math> หากเราสนใจอัลกอลิทึมของ คารัทซูบา คือกรณีพิเศษของทูมอัลกอลิทึม ที่แบ่งจำนวนเป็น 2 ส่วน<math>(k=2)</math> นั่นเอง จะทำให้ใช้เวลาเท่ากับ <math>\Theta(n^{\frac{\log (3)}{\log (2)}})</math> ซึ่งมีค่าประมาณ <math>\Theta (n1.585)</math> และถ้าเราสนใจการคูณแบบปกติทั่วไป คือกรณีของ '''ทูม - 1''' โดยเสียเวลาเท่ากับ <math>\Theta (n2)</math>
''
จะสังเกตได้ว่าถ้าเราเพิ่ม <math>k</math> ไปเรื่อยๆจะสามารถทำให้ค่า <math>e</math> เข้าใกล้ 1 ได้ซึ่งจะเป็นเวลาในอุดมคติมาก คือ <math>\Theta(n)</math> แต่ในความจริงแล้วมันจะทำให้ส่วนของค่า <math>c(k)</math> เพิ่มขึ้นจากที่เดิมเป็น 1 นั่นเอง จากข้อจำกัดนี้ทำให้ เราแบ่งเลขได้เพียงไม่กี่ส่วนเท่านั้น
การนำอัลกอลิทึมนี้ถูกจำกัดให้ใช้กับเลขนาด'''กลาง -ใหญ่'''เพราะถ้าเราไปใช้กับเลขนาดเล็กจะใช้เวลามากกว่าการคูณแบบปกติ และอัลกอลิทึมนี้ถูกแทนที่ด้วยอัลกอลิทึมที่เร็วกว่านั่นคือ [[ขั้นตอนวิธี Schonhage-Strassen|สตราเซน อัลกอลิทึม]] นั่นเอง

อังเดร ทูมได้เผยแพร่อัลกอลิทึมนี้ในปี 1963 หลังจากนั้น สตีเฟน คุก ได้มาปรับปรุงเพิ่มเติมในปี 1966<ref>[http://www.cs.toronto.edu/~sacook/ Stephen A. Cook thesis]</ref>

== รายระเอียดของกระบวนการ ==

ในกรณีของการใช้เลขขนาดใหญ่ เราจะแทนจำนวนเหล่านี้เป็นบล็อกหรือช่วงย่อย ๆ โดยอาจจะใช้เลขฐานเข้ามาช่วยเพื่อให้ง่ายต่อการคำนวณโดยในตัวอย่างนี้จะ ให้ส่วยย่อย ๆ มีขนาด 4 หลักหรือให้ตัวแปร <math>b</math> เป็นเลขฐานที่มีขนาด 10000 <math>(b = 10000)</math> จะทำให้เลขเป็นดังนี้

{|
| ''m'' || = || 12 || 3456 || 7890 || 1234 || 5678 || 9012
|-
| ''n'' || = 
| align = right|9 || 8765 || 4321 || 9876 || 5432 || 1098
|}

''จากตัวอย่างนี้ใช้เลขขนาดเล็กเพื่อง่ายต่อการทำความเข้าใจ เลขนี้ถือว่ามีขนาดเล็กมากในการใช้อัลกอลิทึมนี้ ดังนั้นหากเราใช้การคูณเลขแบบปกติจะมีความเร็วมากกว่า''

=== การแยกค่า ===
หลังจากที่เราแบ่งเลขเป็นส่วนย่อย ๆ แล้ว เราต้องมาหาฐานที่แท้จริงในการแบ่งเลขนี้ออกเป็นส่วน ๆ ของการใช้อัลกอลิทึม [[การคูณของทูม-คุก|ทูม - คุก]] นี้ ซึ่งก็คือเราต้องการแบ่งออกเป็น 3 ส่วนในแต่ละจำนวน ซึ่งหาค่าฐานได้จาก <math>B = b^i</math> โดย <math>B</math> จะเป็นฐานที่ใช้จริง ๆ ส่วน <math>b</math> คือฐานที่แบ่งไว่ในช่วงต้น และเราสามารถหาค่า <math>i</math> ได้จาก
: <math>i = \max\{{\lfloor}{\lceil}\log_b m{\rceil}/k{\rfloor}, {\lfloor}{\lceil}\log_b n{\rceil}/k{\rfloor}\}</math>
ในตัวอย่างนี้เราจะหาค่า <math>i</math> ได้เท่ากับ 6 ดังนั้นฐานที่ใช้จริงคือ <math>B = b^{\frac{6}{3}} = 10^8</math> ซึ่ง <math>b</math> คือ ที่แบ่งไว้ช่วงต้นคือ <math>10^4</math> จากนั้น ให้เราทำการแบ่งเลข 2 จำนวนนี้ใหม่เป็นเลขฐาน <math>10^8</math> จะได้จำนวนใหม่ดังนี้

: <math>
\begin{align}
m_2 & {} = 123456 \\
m_1 & {} = 78901234 \\
m_0 & {} = 56789012 \\
n_2 & {} = 98765 \\
n_1 & {} = 43219876 \\
n_0 & {} = 54321098 \\
\end{align}
</math>
จากนั้นเราใช้เลขเหล่าไปเป็นสัมประสิทธิ์ของสมการพนุนามกำลัง ''k-1'' เราใช้ [[การคูณของทูม-คุก|ทูม - คุก]] ที่ใช้ ''k = 3'' ดังนั้นจะเป็นสมการพหุนามกำลัง 2 โดยให้ '''p (B) = m''' และ '''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>
เหตุผลที่ต้องทำวิธีนี้คือ เราสามารถหาค่า ''r (x) = p (x) q (x)'' และ ''r (B) = m×n'' ซึ่งคือคำตอบนั่นเอง

ในกรณีที่ไม่แบ่งส่วนเป็นจำนวนเท่ากัน คือแบ่งเลขทั้ง 2 จำนวนให้จำนวนส่วนไม่เท่ากันเช่น แบ่งเป็น 3 ส่วน กับ 2 ส่วน ในกรณีนี้จะเรียกว่า '''Toom-2.5''' เวลาหาค่า ''i'' จะหาจาก

: <math>i = \max\{{\lfloor}{\lceil}\log_b m{\rceil}/k_m{\rfloor}, {\lfloor}{\lceil}\log_b n{\rceil}/k_n{\rfloor}\}</math>

โดยกรณีนี้ <math>k_m = 3</math> และ <math>k_n = 2</math> ตามจำนวนส่วนที่แบ่งและไปหา ฐานที่แท้จริงจาก <math>B = b^i</math>

=== การประเมินค่า ===
หลังจากที่เราจัดรูปเลขให้อยู่ในรูปของพหุนามเราต้องการหา '''r (x)''' ที่เป็นพหุนามที่เกิดจากการคูณกันของ '''p (x)''' และ '''q (x)''' โดบเราจะใช้วิธีการดังนี้
โดยปกติแล้วจำนวนพจน์ของพหุนามหาได้จาก '''เลขกำลังของพหุนาม +1 (บวกเพิ่มอีกหนึ่ง) ''' เช่น ''สมการพหุนามกำลัง 1 หรือสมการเส้นตรง จะมีจำนวนพจน์คือ 2'' และ '''กำลังของพหุนามที่เกิดจากพหุนามย่อยมาคูณกันหาได้จากกำลังของพนุนามย่อมบวกกัน''' เช่น ''พหุนามกำลัง 2 คูณกับ พหุนามกำลัง 2 จะได้ผลลัพธ์ของออกมาเปนพนุนามกำลัง 4 ซึ่งมีทั้งหมด 4+1 พจน์'' ดังนั้น '''หากเราต้องการสร้างพหุนาม r ที่มีทั้งหมด 5 พจน์ เราต้องการหาค่าทั้งหมด 5 ครั้ง'''เพื่อหาค่ามีแทนในแต่ละตัวประกอบในแต่ละพจน์ของมัน โดยเราใช้เลขอะไรก็ได้ แต่เพื่อความง่ายต่อการคำนวณเราจะใช้ 0, 1, -1, -2 และ ∞ ในกรณีหลังที่แทนด้วย ∞ จะให้ค่าที่ออกมาเป็นสัมประสิทธิ์ของพจน์ที่กำลังสูงสุดเสมอ เมื่อนำไปแทนจะได้ค่าดังนั้น
: <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>
เมื่อแทนค่าของตัวอย่างลงไป จะสังเกตได้ว่าบางค่าสามารถมค่าเป็นลบได้
{|
| ''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'' (−1) || = || ''m''<sub>0</sub> − ''m''<sub>1</sub> + ''m''<sub>2</sub> || = || 56789012 − 78901234 + 123456 || = || −21988766
|-
| ''p'' (−2) || = || ''m''<sub>0</sub> − 2''m''<sub>1</sub> + 4''m''<sub>2</sub> || = || 56789012 − 2×78901234 + 4×123456 || = || −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'' (−1) || = || ''n''<sub>0</sub> − ''n''<sub>1</sub> + ''n''<sub>2</sub> || = || 54321098 − 43219876 + 98765 || = || 11199987
|-
| ''q'' (−2) || = || ''n''<sub>0</sub> − 2''n''<sub>1</sub> + 4''n''<sub>2</sub> || = || 54321098 − 2×43219876 + 4×98765 || = || −31723594
|-
| ''q'' (∞) || = || ''n''<sub>2</sub> || = || 98765 || = || 98765
|}
เราสามารถนำเสนอการแทนค่าเหล่านนี้ในรูปแบบของแมกทริกส์ได้ซึ่งจะมีประโยชน์อย่างมากต่อการนำไปคำนวณต่อ
: <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>

=== การเพิ่มความเร็วในการคำนวณ ===

เราสามารถทำการคำนวณให้รวดเร็วมากยิ่งขึ้นได้โดยเรากำหนด '''p<sub>0</sub>''' ขึ้นมาใหม่เพราะในความจริงแล้วเลขจะใหญ่มากกว่านี้ และหากให้อัลกอลิทึมของ'''ทูม - คุก''' แล้วก็จะแทนค่าแบบนี้ทุกครั้งเพื่อความรวดเร็วในการคำนวณ และเหตุผลที่ทำไมไม่เลือกใช้ 2 แทน ∞ เพราะให่สังเกตการแทนค่า 2 ลงไป จำเป็นที่ต้องเกิดการคูณเกิดขึ้นทำให้เสียเวลาในช่วงนี้

{|
| ''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'' (−1) || = || ''p''<sub>0</sub> − ''m''<sub>1</sub> || = || 56912468 − 78901234 || = || −21988766
|-
| ''p'' (−2) || = || (''p'' (−1) + ''m''<sub>2</sub>) ×2 − ''m''<sub>0</sub> || = || (− 21988766 + 123456 ) ×2 − 56789012 || = || − 100519632
|-
| ''p'' (∞) || = || ''m''<sub>2</sub> || = || 123456 || = || 123456.
|}

=== การหาผลคูณของขั้นย่อย ===
เราจำเป็นที่ต้องการหาพหุนาม <math>r(x)</math> ที่เกิดจาก <math>p(x) q(x)</math> ในขั้นตอนนี้เราจะทำการคูณ <math>p</math> และ <math>q</math> ในเลขที่แทนในแต่ละตัว เพื่อเอาไปใช้ในการคำนวณต่อ จะสังเกตได้ว่าในขั้นตอนนี้เกิดการคูณเกิดขึ้น ถ้าเลขของเรานั้นยังมีขนาดใหญ่เราจะไม่ทำ[[การคูณแบบปกติ]] ([[:en:Multiplication algorithm|Multiplication algorithm]]) จนกว่าจะมีค่าที่เล็กพอ ถ้าไม่ทำเช่นนั้น จะไม่มีประโยชน์เลยที่เราหาผลคูณโดยอัลกอลิทึมนี้ ดังนั้นเราจะใช้วิธีการเรียกซ้ำไปเข้าในอัลกอลิทึมนี้อีกเพื่อไปใช้กับผลคูณย่อยเหล่านี้

{|
| ''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.
|}

''จะสังเกตได้ว่าขั้นตอนนี้เป็นขั้นตอนที่เสียเวลามากที่สุดเพราะต้องเสียเวลาไปกับการคูณแบบปกติหรือกับการเรียกซ้ำ''

=== การหาสัมประสิทธิ์ ===
จากขั้นตอนที่แล้วที่ได้ค่าของการแทนค่าในพนุนาม <math>r</math> มาแล้วหากเรามีใส่ในรูปของแมกทริกส์ ในขั้นตอนนี้เราต้องการที่จะหาค่าย้อนกลับไปเพื่อจะหาสัมประสิทธิ์ของพหุนาม <math>r</math> จะได้ดังนี้

: <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>

เราสามารถใช้วิธีต่าง ๆ มาเพื่อหา สัมประสิทธิ์เหล่านี้ เช่น วิธี[[การกำจัดของเกาเซียน]] ([[:en:Gaussian elimination|Gaussian elimination]]) แต่วิธีนี้จะเสียเวลาค่อนข้างสูงดังนั้นเราจะวิธีหาอินเวิร์ทแทนจะได้แมกทริกซ์ดังนี้

: <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>
จะเห็นได้ว่าหลังจากอินเวิร์ทแมกทริส์แล้วจะมีบางกรณีที่เป็นเศษส่วน ถ้าหากเราคำนวณโดยใช้คมพิวเตอร์จะปัดเศษที่เกิดจากการหารที่ไม่ลงตัวออกอัตโนมัติอยู่แล้ว ถัดมาเราต้องการหาค่าสัมประสิทธิ์หากเราทำการคูณแมกทริส์แบบปกติเลยนั้นจะเสียเวลาอย่างมาก ในการหาค่า <math>r_1 r_2 r_3</math> และเลขอาจคลาดเคลื่อนได้ ดังนั้น จึงไปใช้วิธีการของ '''โบดราโต''' ในการคำนวณช่วงนี้ โดยทำตามลำดับดังนี้

{|
| ''r''<sub>0</sub> || ← || ''r'' (0) || = || 3084841486175176
|-
| ''r''<sub>4</sub> || ← || ''r'' (∞) || = || 12193131840
|-
| ''r''<sub>3</sub> || ← || (''r'' (−2) − ''r'' (1))/3 || = || (3188843994597408 − 13260814415903778)/3
|-
| || || || = || −3357323473768790
|-
| ''r''<sub>1</sub> || ← || (''r'' (1) − ''r'' (−1))/2 || = || (13260814415903778 − (−246273893346042))/2
|-
| || || || = || 6753544154624910
|-
| ''r''<sub>2</sub> || ← || ''r'' (−1) − ''r'' (0) || = || −246273893346042 − 3084841486175176
|-
| || || || = || −3331115379521218
|-
| ''r''<sub>3</sub> || ← || (''r''<sub>2</sub> − ''r''<sub>3</sub>)/2&nbsp;+ 2''r'' (∞) || = || (−3331115379521218 − (−3357323473768790))/2&nbsp;+ 2×12193131840
|-
| || || || = || 13128433387466
|-
| ''r''<sub>2</sub> || ← || ''r''<sub>2</sub> + ''r''<sub>1</sub> − ''r'' (∞) || = || −3331115379521218 + 6753544154624910 − 12193131840
|-
| || || || = || 3422416581971852
|-
| ''r''<sub>1</sub> || ← || ''r''<sub>1</sub> − ''r''<sub>3</sub> || = || 6753544154624910 − 13128433387466
|-
| || || || = || 6740415721237444
|}

จะได้พนุนาม <math>r</math> ออกมาดังนี้ ถ้าหากเราใช้ การแบ่งส่วนในช่วงแรกในลักษณะที่จำนวนส่วนไม่เท่ากันแล้ว แมกทริกส์ที่ได้ออกมา ผลคูณในขั้นย่อยและวิธีการคำนวณจะต่างกันทำให้อาจไม่สามารถใช้วิธีที่กล่าวออกมาได้ และที่สำคัญที่สุด กระบวนการเหล่านี้ ไม่ขึ้นอยู่กับ ค่าที่ป้อนเข้ามา จึงอาจทำให้ยากต่อการกำหนดค่าต่าง ๆ
: <math>
\begin{align}
r(x) & {} = 3084841486175176 \\
     & {} \quad + 6740415721237444x \\
     & {} \quad + 3422416581971852x^2 \\
     & {} \quad + 13128433387466x^3 \\
     & {} \quad + 12193131840x^4
\end{align}
</math>

=== การประกอบค่า ===
สุดท้ายเราสามารถที่จะหาผลลัพธ์จากการคูณเลขขนาดใหญ่ 2 จำนวน จาก '''r (B) ''' แทนค่า ''B'' ลงไป พนุนาม ''r'' ซึ่ง ''B'' คือฐานที่ได้หาจากขั้นตอนแรก ซึ่งทำโดยการ เลื่อนค่า ตามกำลังของเลขฐานแล้วเอาผลมารวมกันดังนี้ (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
|}
ข้างบนคือคำตอบของการคูณกันของเลข ''1234567890123456789012'' กับ ''987654321987654321098''

== แมกทริส์ของการแบ่งส่วนต่าง ๆ ==
=== ทูม-1 ===
ทูม -1 คือการแบ่งค่าออกเป็น 1 ส่วนทั้ง 2 ค่า '' (k<sub>m</sub> = k<sub>n</sub> = 1) '' มี 1 พจน์ เลือกค่า 0 นำไปแทน จะเป็นลักษณะการคูณแบบปกติ
: <math>\left (\begin{matrix}1\end{matrix}\right) ^{-1} = 
\left (\begin{matrix}1\end{matrix}\right
)</math>

=== ทูม-1.5 ===
ทูม -1.5 คือการแบ่งค่าออกเป็น 2 ส่วนค่าหนึ่งและอีกค่าหนึ่ง 1 ส่วน ''(k<sub>m</sub> = 2, k<sub>n</sub> = 1)'' มี 2 พจน์ เลือกค่า 0 และ ∞ นำไปแทน
: <math>\left (\begin{matrix}1 & 0 \\ 0 & 1\end{matrix}\right) ^{-1} = 
\left (\begin{matrix}1 & 0 \\ 0 & 1\end{matrix}\right)</math>

=== ทูม-2 ===
ทูม - 2 คือการแบ่งค่าออกเป็น 2 ส่วนทั้งสองจำนวน ''(k<sub>m</sub> = 2, k<sub>n</sub> = 2)'' มี 3 พจน์ เลือกค่า 0, 1 และ ∞ นำไปแทน เป็น[[อัลกอลิทึมของคารัสสุบา]] ([[:en:Karatsuba multiplication|Karatsuba multiplication]])
: <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>

=== ทูม-2.5 ===
ทูม - 2.5 คือการแบ่งค่าออกเป็น 3 ส่วนและอีกค่าหนึ่งจำนวน 2 ส่วน ''(k<sub>m</sub> = 3, k<sub>n</sub> = 2)'' มี 4 พจน์ เลือกค่า 0, 1, -1 และ ∞ นำไปแทน
: <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>

== อ้างอิง ==
* [[โดนัลด์ คนูธ]] ''[[:en:The Art of Computer Programming|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.

== แหล่งข้อมูลอื่น ==
* [http://gmplib.org/manual/Toom-3_002dWay-Multiplication.html Toom-Cook 3-Way Multiplication from GMP Documentations]

== อ้างอิง ==
{{รายการอ้างอิง}}
[[หมวดหมู่:การคูณ]]
[[หมวดหมู่:ขั้นตอนวิธี]]