รายระเอียดของกระบวนการ ของ การคูณของทูม-คุก

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

m=1234567890123456789012
n=987654321987654321098.

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

การแยกค่า

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

i = max { ⌊ ⌈ log b ⁡ m ⌉ / k ⌋ , ⌊ ⌈ log b ⁡ n ⌉ / k ⌋ } . {\displaystyle i=\max\{{\lfloor }{\lceil }\log _{b}m{\rceil }/k{\rfloor },{\lfloor }{\lceil }\log _{b}n{\rceil }/k{\rfloor }\}.}

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

m 2 = 123456 m 1 = 78901234 m 0 = 56789012 n 2 = 98765 n 1 = 43219876 n 0 = 54321098 {\displaystyle {\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 = 123456 x 2 + 78901234 x + 56789012 {\displaystyle 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 = 98765 x 2 + 43219876 x + 54321098 {\displaystyle 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 { ⌊ ⌈ log b ⁡ m ⌉ / k m ⌋ , ⌊ ⌈ log b ⁡ n ⌉ / k n ⌋ } . {\displaystyle i=\max\{{\lfloor }{\lceil }\log _{b}m{\rceil }/k_{m}{\rfloor },{\lfloor }{\lceil }\log _{b}n{\rceil }/k_{n}{\rfloor }\}.}

โดยกรณีนี้ k m = 3 {\displaystyle k_{m}=3} และ k n = 2 {\displaystyle k_{n}=2} ตามจำนวนส่วนที่แบ่งและไปหา ฐานที่แท้จริงจาก B = b i {\displaystyle B=b^{i}}

การประเมินค่า

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

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 − 2 m 1 + 4 m 2 p ( ∞ ) = m 2 {\displaystyle {\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.

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

( p ( 0 ) p ( 1 ) p ( − 1 ) p ( − 2 ) p ( ∞ ) ) = ( 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 ) ( m 0 m 1 m 2 ) = ( 1 0 0 1 1 1 1 − 1 1 1 − 2 4 0 0 1 ) ( m 0 m 1 m 2 ) . {\displaystyle \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)=p0 − m1=56912468 − 78901234=−21988766
p (−2)=(p (−1) + m2) ×2 − m0=(− 21988766 + 123456 ) ×2 − 56789012=− 100519632
p (∞)=m2=123456=123456.

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

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

( r ( 0 ) r ( 1 ) r ( − 1 ) r ( − 2 ) r ( ∞ ) ) = ( 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 ) ( r 0 r 1 r 2 r 3 r 4 ) = ( 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 ) ( r 0 r 1 r 2 r 3 r 4 ) . {\displaystyle {\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) แต่วิธีนี้จะเสียเวลาค่อนข้างสูงดังนั้นเราจะวิธีหาอินเวิร์ทแทนจะได้แมกทริกซ์ดังนี้

( r 0 r 1 r 2 r 3 r 4 ) = ( 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 ) − 1 ( r ( 0 ) r ( 1 ) r ( − 1 ) r ( − 2 ) r ( ∞ ) ) = ( 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 ) ( r ( 0 ) r ( 1 ) r ( − 1 ) r ( − 2 ) r ( ∞ ) ) . {\displaystyle {\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 {\displaystyle 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 {\displaystyle r} ออกมาดังนี้ ถ้าหากเราใช้ การแบ่งส่วนในช่วงแรกในลักษณะที่จำนวนส่วนไม่เท่ากันแล้ว แมกทริกส์ที่ได้ออกมา ผลคูณในขั้นย่อยและวิธีการคำนวณจะต่างกันทำให้อาจไม่สามารถใช้วิธีที่กล่าวออกมาได้ และที่สำคัญที่สุด กระบวนการเหล่านี้ ไม่ขึ้นอยู่กับ ค่าที่ป้อนเข้ามา จึงอาจทำให้ยากต่อการกำหนดค่าต่างๆ

r ( x ) = 3084841486175176 + 6740415721237444 x + 3422416581971852 x 2 + 13128433387466 x 3 + 12193131840 x 4 . {\displaystyle {\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 = 104 and B = b2 = 108)

3084841486175176
6740415721237444
3422416581971852
13128433387466
+12193131840
1219326312467611632493760095208585886175176

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

ใกล้เคียง

การคูณ การคูณของทูม-คุก การคูณลูกโซ่ของเมทริกซ์ การคัดเลือกโดยธรรมชาติ การค้าประเวณี การคัดแยกผู้ป่วย การคุมกำเนิด การควบคุมอารมณ์ตนเอง การค้าประเวณีเด็ก การบูรณะจิตรกรรมฝาผนังโบสถ์น้อยซิสทีน