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

การคูณของทูม-คุก (อังกฤษ: 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

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

ในกรณีของการใช้เลขขนาดใหญ่ เราจะแทนจำนวนเหล่านี้เป็นบล็อกหรือช่วงย่อย ๆ โดยอาจจะใช้เลขฐานเข้ามาช่วยเพื่อให้ง่ายต่อการคำนวณโดยในตัวอย่างนี้จะ ให้ส่วยย่อย ๆ มีขนาด 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{aligned}m_{2}&{}=123456\\m_{1}&{}=78901234\\m_{0}&{}=56789012\\n_{2}&{}=98765\\n_{1}&{}=43219876\\n_{0}&{}=54321098\\\end{aligned}}$

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

$p(x)=m_{2}x^{2}+m_{1}x+m_{0}=123456x^{2}+78901234x+56789012\,$

$q(x)=n_{2}x^{2}+n_{1}x+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{aligned}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{aligned}}$

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

p (0)	=	m0	=	56789012	=	56789012
p (1)	=	m0 + m1 + m2	=	56789012 + 78901234 + 123456	=	135813702
p (−1)	=	m0 − m1 + 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)	=	n0 − n1 + 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)$

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

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

p0	←	m0 + m2	=	56789012 + 123456	=	56912468
p (0)	=	m0	=	56789012	=	56789012
p (1)	=	p0 + m1	=	56912468 + 78901234	=	135813702
p (−1)	=	p0 − m1	=	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{aligned}\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{aligned}}$

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

${\begin{aligned}\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{aligned}}$

จะเห็นได้ว่าหลังจากอินเวิร์ทแมกทริส์แล้วจะมีบางกรณีที่เป็นเศษส่วน ถ้าหากเราคำนวณโดยใช้คมพิวเตอร์จะปัดเศษที่เกิดจากการหารที่ไม่ลงตัวออกอัตโนมัติอยู่แล้ว ถัดมาเราต้องการหาค่าสัมประสิทธิ์หากเราทำการคูณแมกทริส์แบบปกติเลยนั้นจะเสียเวลาอย่างมาก ในการหาค่า $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	←	(r2 − r3)/2 + 2r (∞)	=	(−3331115379521218 − (−3357323473768790))/2 + 2×12193131840
			=	13128433387466
r2	←	r2 + r1 − r (∞)	=	−3331115379521218 + 6753544154624910 − 12193131840
			=	3422416581971852
r1	←	r1 − r3	=	6753544154624910 − 13128433387466
			=	6740415721237444

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

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

การประกอบค่า

สุดท้ายเราสามารถที่จะหาผลลัพธ์จากการคูณเลขขนาดใหญ่ 2 จำนวน จาก r (B) แทนค่า B ลงไป พนุนาม r ซึ่ง B คือฐานที่ได้หาจากขั้นตอนแรก ซึ่งทำโดยการ เลื่อนค่า ตามกำลังของเลขฐานแล้วเอาผลมารวมกันดังนี้ (b = 10⁴ and B = b² = 10⁸)

								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 ค่า (k_m = k_n = 1) มี 1 พจน์ เลือกค่า 0 นำไปแทน จะเป็นลักษณะการคูณแบบปกติ

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

ทูม-1.5

ทูม -1.5 คือการแบ่งค่าออกเป็น 2 ส่วนค่าหนึ่งและอีกค่าหนึ่ง 1 ส่วน (k_m = 2, k_n = 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 ส่วนทั้งสองจำนวน (k_m = 2, k_n = 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 ส่วน (k_m = 3, k_n = 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)$

อ้างอิง

• โดนัลด์ คนูธ 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.

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

• Toom-Cook 3-Way Multiplication from GMP Documentations