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

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

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

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

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

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

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

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

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

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

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

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

เราจำเป็นที่ต้องการหาพหุนาม r(x){\displaystyle r(x)} ที่เกิดจาก p(x)q(x){\displaystyle p(x)q(x)} ในขั้นตอนนี้เราจะทำการคูณ p{\displaystyle p} และ q{\displaystyle q} ในเลขที่แทนในแต่ละตัว เพื่อเอาไปใช้ในการคำนวณต่อ จะสังเกตได้ว่าในขั้นตอนนี้เกิดการคูณเกิดขึ้น ถ้าเลขของเรานั้นยังมีขนาดใหญ่เราจะไม่ทำการคูณแบบปกติ (Multiplication algorithm) จนกว่าจะมีค่าที่เล็กพอ ถ้าไม่ทำเช่นนั้น จะไม่มีประโยชน์เลยที่เราหาผลคูณโดยอัลกอลิทึมนี้ ดังนั้นเราจะใช้วิธีการเรียกซ้ำไปเข้าในอัลกอลิทึมนี้อีกเพื่อไปใช้กับผลคูณย่อยเหล่านี้

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

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

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

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

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

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

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

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

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

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