การคูณของทูม-คุก

จากวิกิพีเดีย สารานุกรมเสรี

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

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

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

อังเดร ทูมได้เผยแพร่อัลกอลิทึมนี้ในปี 1963 หลังจากนั้น สตีเฟน คุก ได้มาปรับปรุงเพิ่มเติมในปี 1966[1]

รายระเอียดของกระบวนการ[แก้]

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

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

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

การแยกค่า[แก้]

หลังจากที่เราแบ่งเลขเป็นส่วนย่อยๆแล้ว เราต้องมาหาฐานที่แท้จริงในการแบ่งเลขนี้ออกเป็นส่วนๆของการใช้อัลกอลิทึม ทูม - คุก นี้ ซึ่งก็คือเราต้องการแบ่งออกเป็น 3 ส่วนในแต่ละจำนวน ซึ่งหาค่าฐานได้จาก B = b^i โดย B จะเป็นฐานที่ใช้จริงๆ ส่วน b คือฐานที่แบ่งไว่ในช่วงต้น และเราสามารถหาค่า i ได้จาก

i = \max\{{\lfloor}{\lceil}\log_b m{\rceil}/k{\rfloor}, {\lfloor}{\lceil}\log_b n{\rceil}/k{\rfloor}\}.

ในตัวอย่างนี้เราจะหาค่า i ได้เท่ากับ 6 ดังนั้นฐานที่ใช้จริงคือ B = b^{\frac{6}{3}} = 10^8 ซึ่ง b คือที่แบ่งไว้ช่วงต้นคือ 10^4 จากนั้น ให้เราทำการแบ่งเลข 2 จำนวนนี้ใหม่เป็นเลขฐาน 10^8 จะได้จำนวนใหม่ดังนี้


\begin{align}
m_2 & {} = 123456 \\
m_1 & {} = 78901234 \\
m_0 & {} = 56789012 \\
n_2 & {} = 98765 \\
n_1 & {} = 43219876 \\
n_0 & {} = 54321098 \\
\end{align}

จากนั้นเราใช้เลขเหล่าไปเป็นสัมประสิทธิ์ของสมการพนุนามกำลัง k-1 เราใช้ ทูม - คุก ที่ใช้ k = 3 ดังนั้นจะเป็นสมการพหุนามกำลัง 2 โดยให้ p (B) = m และ q (B) = n

p (x) = m_2x^2 + m_1x + m_0 = 123456x^2 + 78901234x + 56789012 \,
q (x) = n_2x^2 + n_1x + n_0 = 98765x^2 + 43219876x + 54321098 \,

เหตุผลที่ต้องทำวิธีนี้คือ เราสามารถหาค่า r (x) = p (x) q (x) และ r (B) = m×n ซึ่งคือคำตอบนั่นเอง

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

i = \max\{{\lfloor}{\lceil}\log_b m{\rceil}/k_m{\rfloor}, {\lfloor}{\lceil}\log_b n{\rceil}/k_n{\rfloor}\}.

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

การประเมินค่า[แก้]

หลังจากที่เราจัดรูปเลขให้อยู่ในรูปของพหุนามเราต้องการหา r (x) ที่เป็นพหุนามที่เกิดจากการคูณกันของ p (x) และ q (x) โดบเราจะใช้วิธีการดังนี้ โดยปกติแล้วจำนวนพจน์ของพหุนามหาได้จาก เลขกำลังของพหุนาม +1 (บวกเพิ่มอีกหนึ่ง) เช่น สมการพหุนามกำลัง 1 หรือสมการเส้นตรง จะมีจำนวนพจน์คือ 2 และ กำลังของพหุนามที่เกิดจากพหุนามย่อยมาคูณกันหาได้จากกำลังของพนุนามย่อมบวกกัน เช่น พหุนามกำลัง 2 คูณกับ พหุนามกำลัง 2 จะได้ผลลัพธ์ของออกมาเปนพนุนามกำลัง 4 ซึ่งมีทั้งหมด 4+1 พจน์ ดังนั้น หากเราต้องการสร้างพหุนาม r ที่มีทั้งหมด 5 พจน์ เราต้องการหาค่าทั้งหมด 5 ครั้งเพื่อหาค่ามีแทนในแต่ละตัวประกอบในแต่ละพจน์ของมัน โดยเราใช้เลขอะไรก็ได้ แต่เพื่อความง่ายต่อการคำนวณเราจะใช้ 0,1,-1,-2 และ ∞ ในกรณีหลังที่แทนด้วย ∞ จะให้ค่าที่ออกมาเป็นสัมประสิทธิ์ของพจน์ที่กำลังสูงสุดเสมอ เมื่อนำไปแทนจะได้ค่าดังนั้น


\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}

เมื่อแทนค่าของตัวอย่างลงไป จะสังเกตได้ว่าบางค่าสามารถมค่าเป็นลบได้

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.

เราสามารถนำเสนอการแทนค่าเหล่านนี้ในรูปแบบของแมกทริกส์ได้ซึ่งจะมีประโยชน์อย่างมากต่อการนำไปคำนวณต่อ


\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).


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

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

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.

การหาผลคูณของขั้นย่อย[แก้]

เราจำเป็นที่ต้องการหาพหุนาม r(x) ที่เกิดจาก p(x) q(x) ในขั้นตอนนี้เราจะทำการคูณ p และ q ในเลขที่แทนในแต่ละตัว เพื่อเอาไปใช้ในการคำนวณต่อ จะสังเกตได้ว่าในขั้นตอนนี้เกิดการคูณเกิดขึ้น ถ้าเลขของเรานั้นยังมีขนาดใหญ่เราจะไม่ทำการคูณแบบปกติ (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.

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

การหาสัมประสิทธิ์[แก้]

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


\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}

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


\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}

จะเห็นได้ว่าหลังจากอินเวิร์ทแมกทริส์แล้วจะมีบางกรณีที่เป็นเศษส่วน ถ้าหากเราคำนวณโดยใช้คมพิวเตอร์จะปัดเศษที่เกิดจากการหารที่ไม่ลงตัวออกอัตโนมัติอยู่แล้ว ถัดมาเราต้องการหาค่าสัมประสิทธิ์หากเราทำการคูณแมกทริส์แบบปกติเลยนั้นจะเสียเวลาอย่างมาก ในการหาค่า r_1 r_2 r_3 และเลขอาจคลาดเคลื่อนได้ ดังนั้น จึงไปใช้วิธีการของ โบดราโต ในการคำนวณช่วงนี้ โดยทำตามลำดับดังนี้

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 + r1r (∞) = −3331115379521218 + 6753544154624910 − 12193131840
= 3422416581971852
r1 r1r3 = 6753544154624910 − 13128433387466
= 6740415721237444.

จะได้พนุนาม r ออกมาดังนี้ ถ้าหากเราใช้ การแบ่งส่วนในช่วงแรกในลักษณะที่จำนวนส่วนไม่เท่ากันแล้ว แมกทริกส์ที่ได้ออกมา ผลคูณในขั้นย่อยและวิธีการคำนวณจะต่างกันทำให้อาจไม่สามารถใช้วิธีที่กล่าวออกมาได้ และที่สำคัญที่สุด กระบวนการเหล่านี้ ไม่ขึ้นอยู่กับ ค่าที่ป้อนเข้ามา จึงอาจทำให้ยากต่อการกำหนดค่าต่างๆ


\begin{align}
r(x) & {} = 3084841486175176 \\
     & {} \quad + 6740415721237444x \\
     & {} \quad + 3422416581971852x^2 \\
     & {} \quad + 13128433387466x^3 \\
     & {} \quad + 12193131840x^4.
\end{align}

การประกอบค่า[แก้]

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

ข้างบนคือคำตอบของการคูณกันของเลข 1234567890123456789012 กับ 987654321987654321098

แมกทริส์ของการแบ่งส่วนต่างๆ[แก้]

ทูม-1[แก้]

ทูม -1 คือการแบ่งค่าออกเป็น 1 ส่วนทั้ง 2 ค่า (km = kn = 1) มี 1 พจน์ เลือกค่า 0 นำไปแทน จะเป็นลักษณะการคูณแบบปกติ

\left (\begin{matrix}1\end{matrix}\right) ^{-1} = 
\left (\begin{matrix}1\end{matrix}\right).

ทูม-1.5[แก้]

ทูม -1.5 คือการแบ่งค่าออกเป็น 2 ส่วนค่าหนึ่งและอีกค่าหนึ่ง 1ส่วน (km = 2, kn = 1) มี 2 พจน์ เลือกค่า 0 และ ∞ นำไปแทน

\left (\begin{matrix}1 & 0 \\ 0 & 1\end{matrix}\right) ^{-1} = 
\left (\begin{matrix}1 & 0 \\ 0 & 1\end{matrix}\right).

ทูม-2[แก้]

ทูม - 2 คือการแบ่งค่าออกเป็น 2 ส่วนทั้งสองจำนวน (km = 2, kn = 2) มี 3 พจน์ เลือกค่า 0, 1 และ ∞ นำไปแทน เป็นอัลกอลิทึมของคารัสสุบา (Karatsuba multiplication)

\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).

ทูม-2.5[แก้]

ทูม - 2.5 คือการแบ่งค่าออกเป็น 3 ส่วนและอีกค่าหนึ่งจำนวน 2 ส่วน (km = 3, kn = 2) มี 4 พจน์ เลือกค่า 0, 1, -1 และ ∞ นำไปแทน

\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).

อ้างอิง[แก้]

แหล่งข้อมูลอื่น[แก้]

อ้างอิง[แก้]