อัลกอริทึม Karatsubaเป็นอัลกอริทึมการคูณจำนวนเต็มที่ รวดเร็ว ค้นพบโดยAnatoly Karatsubaในปี 1960 และตีพิมพ์ในปี 1962 ^{[ 1 ] [ 2 ] [ 3 ]}เป็นอัลกอริทึมแบบแบ่งและพิชิต (divide-and-conquer)ที่ลดการคูณ จำนวน n หลักสองจำนวนให้เหลือการคูณจำนวน n /2 หลักสามครั้ง และโดยการทำซ้ำการลดนี้ จะเหลือ การคูณหลักเดียวเป็นอย่างมาก ดังนั้นจึงเร็วกว่าอั ลกอริทึม แบบดั้งเดิมซึ่งทำการคูณหลักเดียวในเชิงอะซิมโทติก ${\displaystyle n^{\log _{2}3}\approx n^{1.58}}$${\displaystyle n^{2}}$

อัลกอริทึม Karatsuba เป็นอัลกอริทึมการคูณตัวแรกที่เร็วกว่าอัลกอริทึมแบบกำลังสอง "ระดับประถมศึกษา" ในเชิงอะซิมโทติกอัลกอริทึม Toom–Cook (1963) เป็นการขยายวิธีการของ Karatsuba ที่เร็วกว่า และอัลกอริทึม Schönhage–Strassen (1971) นั้นเร็วกว่ามาก สำหรับค่า nที่มีขนาดใหญ่พอสมควร

ขั้นตอนมาตรฐานสำหรับการคูณจำนวนสอง จำนวนที่มี nหลัก ต้องใช้การดำเนินการพื้นฐานจำนวนหนึ่งซึ่งเป็นสัดส่วนกับหรือใน สัญกร ณ์บิ๊กโอแอนเดรย์ โคลโมโกโรฟตั้งข้อสันนิษฐานว่าอัลกอริทึมแบบดั้งเดิมนั้นเหมาะสมที่สุดในเชิงอะซิมโทติกซึ่งหมายความว่าอัลกอริทึมใดๆ สำหรับงานนั้นจะต้องใช้การดำเนินการพื้นฐานจำนวนหนึ่ง ${\displaystyle n^{2}\,\!}$${\displaystyle O(n^{2})\,\!}$${\displaystyle \โอเมก้า (n^{2})\,\!}$

ในปี 1960 โคลโมโกโรฟได้จัดสัมมนาเกี่ยวกับปัญหาทางคณิตศาสตร์ในด้านไซเบอร์เนติกส์ที่มหาวิทยาลัยแห่งรัฐมอสโกซึ่งเขาได้กล่าวถึงข้อสันนิษฐานและปัญหาอื่นๆ ในความซับซ้อนของการคำนวณภายในหนึ่งสัปดาห์ คาราซึบะซึ่งขณะนั้นเป็นนักศึกษาอายุ 23 ปี ได้ค้นพบอัลกอริทึมที่สามารถคูณเลขสองจำนวนที่มีn หลักได้ใน ขั้นตอนพื้นฐาน จึงเป็นการหักล้างข้อสันนิษฐานดังกล่าว โคลโมโกโรฟรู้สึกตื่นเต้นมากกับการค้นพบนี้ เขาได้แจ้งให้ทราบในการประชุมสัมมนาครั้งต่อไป ซึ่งต่อมาการสัมมนาก็ถูกยกเลิก โคลโมโกโรฟได้บรรยายเกี่ยวกับผลลัพธ์ของคาราซึบะในการประชุมต่างๆ ทั่วโลก (ดูตัวอย่างเช่น "รายงานการประชุมสภาคณิตศาสตร์นานาชาติ ปี 1962" หน้า 351–356 และ "การบรรยาย 6 ครั้งในการประชุมสภาคณิตศาสตร์นานาชาติที่สตอกโฮล์ม ปี 1962") และตีพิมพ์วิธีการดังกล่าวในปี 1962 ในรายงานการประชุมของสถาบันวิทยาศาสตร์แห่งสหภาพโซเวียต บทความดังกล่าวเขียนโดย Kolmogorov และมีผลลัพธ์สองประการเกี่ยวกับการคูณ ได้แก่ อัลกอริทึมของ Karatsuba และผลลัพธ์แยกต่างหากโดยYuri Ofmanโดยระบุชื่อผู้เขียนว่า "A. Karatsuba และ Yu. Ofman" Karatsuba เพิ่งทราบเกี่ยวกับเอกสารนี้เมื่อเขาได้รับสำเนาจากสำนักพิมพ์^{[ 2 ]}${\displaystyle \โอเมก้า (n^{2})\,\!}$${\displaystyle O(n^{\log _{2}3})}$

หลักการพื้นฐานของอัลกอริทึมของคารัตสึบะคือการแบ่งและพิชิตโดยใช้สูตรที่ช่วยให้สามารถคำนวณผลคูณของจำนวนขนาดใหญ่สองจำนวนและใช้การคูณจำนวนขนาดเล็กสามจำนวน ซึ่งแต่ละจำนวนหลักประมาณครึ่งหนึ่งของจำนวนหลักแรกหรือ จำนวนหลักที่สอง บวกกับการบวกและการเลื่อนหลักบางส่วน ขั้นตอนพื้นฐานนี้แท้จริงแล้วเป็นการขยายความของอัลกอริทึมการคูณเชิงซ้อนที่คล้ายกันโดยที่หน่วยจินตภาพiถูกแทนที่ด้วยกำลังของฐาน${\displaystyle x}$${\displaystyle y}$${\displaystyle x}$${\displaystyle y}$

ให้และแทนด้วยสตริงที่มี n หลัก ในฐานใดฐานหนึ่งสำหรับจำนวนเต็มบวกใดๆที่น้อยกว่าเราสามารถเขียนจำนวนทั้งสองที่กำหนดให้ดังนี้ ${\displaystyle x}$${\displaystyle y}$${\displaystyle n}$${\displaystyle B}$${\displaystyle m}$${\displaystyle n}$

${\displaystyle x=x_{1}B^{m}+x_{0},}$

${\displaystyle y=y_{1}B^{m}+y_{0},}$

โดยที่และมีค่าน้อยกว่าผลคูณคือ ${\displaystyle x_{0}}$${\displaystyle y_{0}}$${\displaystyle B^{m}}$

${\displaystyle {\begin{aligned}xy&=(x_{1}B^{m}+x_{0})(y_{1}B^{m}+y_{0})\\&=x_{1}y_{1}B^{2m}+(x_{1}y_{0}+x_{0}y_{1})B^{m}+x_{0}y_{0}\\&=z_{2}B^{2m}+z_{1}B^{m}+z_{0},\\\end{aligned}}}$

ที่ไหน

${\displaystyle z_{2}=x_{1}y_{1},}$

${\displaystyle z_{1}=x_{1}y_{0}+x_{0}y_{1},}$

${\displaystyle z_{0}=x_{0}y_{0}.}$

สูตรเหล่านี้ต้องใช้การคูณสี่ครั้งและเป็นที่รู้จักของชาร์ลส์ แบ็บเบจ^{[ 4 ]}คาราตสึบะสังเกตว่าสามารถคำนวณได้ด้วยการคูณเพียงสามครั้ง โดยแลกกับการบวกเพิ่มเติมอีกเล็กน้อย ด้วยและเช่นเดียวกับก่อนหน้านี้ และสังเกตได้ว่า ${\displaystyle xy}$${\displaystyle z_{0}}$${\displaystyle z_{2}}$${\displaystyle z_{3}=(x_{1}+x_{0})(y_{1}+y_{0}),}$

${\displaystyle {\begin{alignedat}{2}z_{1}&=x_{1}y_{0}+x_{0}y_{1}\\&=x_{1}y_{0}+x_{0}y_{1}+x_{1}y_{1}+x_{0}y_{0}&&-x_{1}y_{ 1}-x_{0}y_{0}\\&=(x_{1}+x_{0})(y_{1}+y_{0})&&-x_{1}y_{1}-x_{0}y_{0}\\&=z_{3}-z_{2}-z_{0}.\\\end{alignedat}}}$

ดังนั้นจึงต้องใช้การคูณเพียงสามครั้งในการคำนวณและด้วยเหตุนี้${\displaystyle z_{0},z_{1}}$${\displaystyle z_{2},}$${\displaystyle xy.}$

รูปแบบอื่นใช้แทนด้วย: ${\displaystyle z_{4}=(x_{1}-x_{0})(y_{1}-y_{0})}$

${\displaystyle {\begin{aligned}z_{1}&={\phantom {x_{1}y_{1}+x_{0}y_{0}-(x_{1}y_{1}-x_{0}y_{0}+{}}}x_{1}y_{0}+x_{0}y_{1}\\&=x_{1}y_{1}+x_{0}y_{0}-{\phantom {(}}x_{1}y_{1}-x_{0}y_{0}+x_{1}y_{0}+x_{0}y_{1}\\&=x_{1}y_{1}+x_{0}y_{0}-(x_{1}y_{1}+x_{0}y_{0}-x_{1}y_{0}-x_{0}y_{1})\\&=x_{1}y_{1}+x_{0}y_{0}-(x_{1}-x_{0})(y_{1}-y_{0})\\&=z_{2}+z_{0}-z_{4}.\\\end{aligned}}}$

ในการคำนวณผลคูณของ 12345 และ 6789 โดยที่B = 10 ให้เลือกm = 3 เราใช้ การเลื่อนบิตไปทางขวา m ครั้งเพื่อแยกตัวดำเนินการอินพุตโดยใช้ฐานที่ได้ ( B ^m = 1000 ) ดังนี้:

12345 = 12 · 1000 + 345

6789 = 6 · 1000 + 789

มีการใช้การคูณเพียงสามครั้ง ซึ่งดำเนินการกับจำนวนเต็มที่เล็กกว่า เพื่อคำนวณผลลัพธ์บางส่วนสามอย่าง:

z ₂ = 12 × 6 = 72

z ₀ = 345 × 789 = 272205

z ₁ = ( 12 + 345 ) × ( 6 + 789 ) − z ₂ − z ₀ = 357 × 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

เราได้ผลลัพธ์โดยการบวกผลลัพธ์ย่อยทั้งสามนี้เข้าด้วยกัน โดยปรับค่าให้เหมาะสม (แล้วจึงนำตัวทดมาพิจารณาโดยการแยกส่วนอินพุตทั้งสามนี้ในฐาน1000เช่นเดียวกับตัวดำเนินการอินพุต):

ผลลัพธ์ = z ₂ · ( B ^m ) ² + z ₁ · ( B ^m ) ¹ + z ₀ · ( B ^m ) ⁰ , ie

ผลลัพธ์ = 72 · 1000 ² + 11538 · 1000 + 272205 = 83810205

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

ถ้าnมีค่าตั้งแต่สี่ขึ้นไป การคูณทั้งสามครั้งในขั้นตอนพื้นฐานของ Karatsuba จะเกี่ยวข้องกับตัวถูกดำเนินการที่มีจำนวนหลักน้อยกว่าnหลัก ดังนั้น ผลคูณเหล่านั้นจึงสามารถคำนวณได้โดย การเรียก ซ้ำของอัลกอริทึม Karatsuba การเรียกซ้ำนี้สามารถทำได้เรื่อยๆ จนกว่าตัวเลขจะมีขนาดเล็กมากจนสามารถ (หรือต้อง) คำนวณได้โดยตรง

ตัวอย่างเช่นในคอมพิวเตอร์ที่มีตัวคูณ ขนาด 32 บิต x 32 บิตเต็มรูป _{แบบ เราสามารถเลือก} B = ^2³¹และเก็บแต่ละหลักเป็นคำไบนารี 32 บิตแยกกันได้ จากนั้นผลรวม_{x₁ +} x₀และy₁ + y₀จะ_ไม่จำเป็นต้องใช้คำไบนารีเพิ่มเติมสำหรับเก็บหลักทด (เช่นเดียวกับตัวบวกแบบ carry-save ) และสามารถใช้การเรียกซ้ำแบบ Karatsuba ได้จนกว่าตัวเลขที่จะคูณจะมีเพียงหลัก เดียว

ขั้นตอนพื้นฐานของ Karatsuba ใช้ได้กับฐานB ใดๆ และm ใดๆ แต่ขั้นตอนวิธีแบบเรียกซ้ำจะมีประสิทธิภาพมากที่สุดเมื่อmเท่ากับn /2 โดยปัดขึ้น โดยเฉพาะอย่างยิ่ง ถ้าnคือ^2k สำหรับจำนวนเต็ม kบางตัวและการเรียกซ้ำจะหยุดก็ต่อเมื่อnเป็น 1 เท่านั้น จำนวนการคูณเลขหลักเดียวคือ 3k ^ซึ่งก็คือnc โดย^ที่ c = log _2/3

เนื่องจากเราสามารถขยายอินพุตใดๆ ที่มีเลขโดดศูนย์จนกระทั่งความยาวเป็นกำลังของสองได้ ดังนั้น จำนวนการคูณพื้นฐานสำหรับn ใดๆ จึงมีค่า ไม่ เกิน${\displaystyle 3^{\lceil \log _{2}n\rceil }\leq 3n^{\log _{2}3}\,\!}$

เนื่องจากการบวก การลบ และการเลื่อนหลัก (การคูณด้วยกำลังของB ) ในขั้นตอนพื้นฐานของ Karatsuba ใช้เวลาแปรผันตรงกับnดังนั้นต้นทุนจึงน้อยมากเมื่อnเพิ่มขึ้น กล่าวคือ ถ้าT ( n ) แทนจำนวนการดำเนินการพื้นฐานทั้งหมดที่อัลกอริทึมดำเนินการเมื่อคูณตัวเลขสอง จำนวนที่มี nหลักแล้ว

${\displaystyle T(n)=3T(\lceil n/2\rceil )+cn+d}$

สำหรับค่าคงที่cและd บางค่า สำหรับ ความสัมพันธ์เวียนเกิดนี้ทฤษฎีบทหลักสำหรับความสัมพันธ์เวียนเกิดแบบแบ่งและพิชิตจะให้ขอบเขตเชิงอะซิมโทติก ${\displaystyle T(n)=\Theta (n^{\log _{2}3})\,\!}$

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

นี่คือรหัสเทียมสำหรับอัลกอริทึมนี้ โดยใช้ตัวเลขที่แสดงในฐานสิบ สำหรับการแสดงเลขฐานสองของจำนวนเต็ม ก็เพียงพอที่จะตั้งค่า BASE เป็นตัวเลขอื่น ซึ่งโดยปกติจะเป็นกำลังของ 2 ตามขนาดของคำเครื่องที่คอมพิวเตอร์สามารถคูณได้^{[ 5 ]}

ฐานคงที่= 10/* คำนวณขนาดของ num ในฐาน ตัวอย่างเช่น 12345 มีขนาด 5 ในฐาน 10 และขนาด 2 ในฐาน 1024 */ ฟังก์ชันsize_in_base ( num ) string_num = num . toString () return string_num . length ()/* แยกตัวเลขออกเป็นส่วนหลักต่ำ "d" และส่วนหลักสูง ตัวอย่างเช่น split_at(12345, 3) จะแยกส่วนหลักสุดท้าย 3 หลักออกมา คือ หลักสูง = 12 หลักต่ำ = 345 */ function split_at ( num , d ) hi = num / ( BASE ^ d ) low = num % ( BASE ^ d ) /* เศษเหลือจากการหาร */ return hi , lowฟังก์ชันkaratsuba ( num1 , num2 ) ถ้า( num1 < BASE หรือnum2 < BASE ) คืนค่าnum1 × num2 /* กลับไปใช้การคูณแบบดั้งเดิม */ /* คำนวณขนาดของตัวเลข */ m = max ( size_in_base ( num1 ), size_in_base ( num2 )) m2 = floor ( m / 2 ) /* m2 = ceil (m / 2) ก็ใช้ได้เช่นกัน */ /* แยกตัวเลขลำดับหลักตรงกลาง */ high1 , low1 = split_at ( num1 , m2 ) high2 , low2 = split_at ( num2 , m2 ) /* เรียกฟังก์ชันแบบเรียกซ้ำ 3 ครั้งกับตัวเลขที่มีขนาดประมาณครึ่งหนึ่ง */ */ z0 = คารัทสึบะ( low1 , low2 ) z3 = คารัทสึบะ( low1 + high1 , low2 + high2 ) z2 = คารัทสึบะ( high1 , high2 ) กลับ( z2 × BASE ^ ( m2 × 2 )) + (( z3 - z2 - z0 ) × BASE ^ m2 ) + z0

ปัญหาที่เกิดขึ้นกับการใช้งานรูปแบบนี้คือ ปัจจัยแต่ละตัวและของอาจต้องการจำนวนหลักมากกว่า1 ในการแสดงผล และตัวมันเองอาจเกิดการโอเวอร์โฟลว์ (ให้ผลลัพธ์ในช่วงที่กำหนด) ความจำเป็นในการใช้ตัวคูณที่มีบิตพิเศษหนึ่งบิตนี้สามารถหลีกเลี่ยงได้โดยใช้รูปแบบทางเลือกที่กล่าวถึงข้างต้น: ${\displaystyle (x_{1}+x_{0})}$${\displaystyle (y_{1}+y_{0})}$${\displaystyle z_{3}}$m2${\displaystyle z_{3}}$${\displaystyle B^{m}\leq z_{3}<2B^{m}}$

${\displaystyle z_{1}=z_{2}+z_{0}-(x_{1}-x_{0})(y_{1}-y_{0}).}$

การคำนวณจะให้ผลลัพธ์ในช่วงวิธีนี้ยังต้องการบิตเพิ่มเติมอีกหนึ่งบิตเพื่อเข้ารหัสเครื่องหมายของตัวเลขที่อาจเป็นลบ แต่สามารถจัดการได้โดยการคำนวณค่าสัมบูรณ์ด้วยตัวคูณที่มีความกว้างคงที่ คำนวณเครื่องหมายของแยกต่างหาก และสุดท้ายก็ทำการบวก ${\displaystyle z_{4}=(x_{1}-x_{0})(y_{1}-y_{0})}$${\displaystyle -B^{m}<z_{4}<B^{m}}$${\displaystyle \left|z_{4}\right|=\left|x_{1}-x_{0}\right|\left|y_{1}-y_{0}\right|}$${\displaystyle z_{4}}$

${\displaystyle z_{1}=z_{2}+z_{0}\pm \left|z_{4}\right|.}$

• บีเวอร์, โจนาธาน. "อัลกอริทึมของคาราสึบะสำหรับการคูณพหุนาม" . มหาวิทยาลัยพิตต์สเบิร์ก – CS1501 .
• เบิร์นสไตน์, แดเนียล เจ. (11 สิงหาคม 2544). "การคูณเลขหลายหลักสำหรับนักคณิตศาสตร์" (PDF) . cr.yp.to. สืบค้นเมื่อ6 ตุลาคม 2568.ครอบคลุมKaratsuba และอัลกอริทึมการคูณอื่นๆ อีกมากมาย
• ไวส์สไตน์, เอริค ดับเบิลยู. "การคูณคาราสึบะ" . MathWorld .
• เทคนิคการคูณของคารัตสึบะ สรุปใน 1 นาทีบน YouTube
• นักเรียนชาวรัสเซียคิดค้นวิธีการคูณที่เร็วกว่าเดิมบน YouTube