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

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

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

อัลกอลิทึมทูม - 3 นี้ จะช่วยลดการคูณเลขจากการคูณเลขแบบปกติจำนวน 9 ครั้งเหลือเพียง 5 ครั้งเท่านั้น ทำให้เวลาลดลงจาก  มีค่าประมาณ  เหลือเพียง  มีค่าประมาณ  ซึ่งกระบวนการนี้หาได้จากวิธีการคำนวณ ทูม - k คือ  เมื่อ  โดยส่วนของ  คือเวลาของการคูณส่วนย่อยหรือส่วนของอัลกอลิทึมของทูม และ  คือเวลาที่ใช้ไปกับการคูณจำนวนขนาดเล็กย่อยๆซึ่งเป็นกระบวนการในการทำอัลกอลิทึมนี้นั่นเอง ซึ่งหากเราใช้ ทูม - 3 แล้วจะได้  และ  นั่นก็คือ  หากเราสนใจอัลกอลิทึมของ คารัทซูบา คือกรณีพิเศษของทูมอัลกอลิทึม ที่แบ่งจำนวนเป็น 2 ส่วน นั่นเอง จะทำให้ใช้เวลาเท่ากับ  ซึ่งมีค่าประมาณ  และถ้าเราสนใจการคูณแบบปกติทั่วไป คือกรณีของ ทูม - 1 โดยเสียเวลาเท่ากับ 
จะสังเกตได้ว่าถ้าเราเพิ่ม  ไปเรื่อยๆจะสามารถทำให้ค่า  เข้าใกล้ 1 ได้ซึ่งจะเป็นเวลาในอุดมคติมาก คือ  แต่ในความจริงแล้วมันจะทำให้ส่วนของค่า  เพิ่มขึ้นจากที่เดิมเป็น 1 นั่นเอง จากข้อจำกัดนี้ทำให้ เราแบ่งเลขได้เพียงไม่กี่ส่วนเท่านั้น
การนำอัลกอลิทึมนี้ถูกจำกัดให้ใช้กับเลขนาดกลาง -ใหญ่เพราะถ้าเราไปใช้กับเลขนาดเล็กจะใช้เวลามากกว่าการคูณแบบปกติ และอัลกอลิทึมนี้ถูกแทนที่ด้วยอัลกอลิทึมที่เร็วกว่านั่นคือ สตราเซน อัลกอลิทึม นั่นเอง

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

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

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

 m  =  12  3456  7890  1234  5678  9012 n  = 9  8765  4321  9876  5432  1098จากตัวอย่างนี้ใช้เลขขนาดเล็กเพื่อง่ายต่อการทำความเข้าใจ เลขนี้ถือว่ามีขนาดเล็กมากในการใช้อัลกอลิทึมนี้ ดังนั้นหากเราใช้การคูณเลขแบบปกติจะมีความเร็วมากกว่า การแยกค่า 
หลังจากที่เราแบ่งเลขเป็นส่วนย่อย ๆ แล้ว เราต้องมาหาฐานที่แท้จริงในการแบ่งเลขนี้ออกเป็นส่วน ๆ ของการใช้อัลกอลิทึม ทูม - คุก นี้ ซึ่งก็คือเราต้องการแบ่งออกเป็น 3 ส่วนในแต่ละจำนวน ซึ่งหาค่าฐานได้จาก  โดย  จะเป็นฐานที่ใช้จริง ๆ ส่วน  คือฐานที่แบ่งไว่ในช่วงต้น และเราสามารถหาค่า  ได้จาก

ในตัวอย่างนี้เราจะหาค่า  ได้เท่ากับ 6 ดังนั้นฐานที่ใช้จริงคือ  ซึ่ง  คือ ที่แบ่งไว้ช่วงต้นคือ  จากนั้น ให้เราทำการแบ่งเลข 2 จำนวนนี้ใหม่เป็นเลขฐาน  จะได้จำนวนใหม่ดังนี้


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



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

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



โดยกรณีนี้  และ  ตามจำนวนส่วนที่แบ่งและไปหา ฐานที่แท้จริงจาก 

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

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


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

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

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



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


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

 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

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


 การประกอบค่า 
สุดท้ายเราสามารถที่จะหาผลลัพธ์จากการคูณเลขขนาดใหญ่ 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 นำไปแทน จะเป็นลักษณะการคูณแบบปกติ


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


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


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


 อ้างอิง 
 โดนัลด์ คนูธ 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

 อ้างอิง 

หมวดหมู่:การคูณ
หมวดหมู่:ขั้นตอนวิธี