ขั้นตอนวิธีของคาราซูบา

ขั้นตอนวิธีของคาราซูบา (อังกฤษ: Karatsuba algorithm) เป็น ขั้นตอนวิธี ที่ค้นพบโดย Anatolii Alexeevitch Karatsuba ในปี ค.ศ. 1960 และตีพิมพ์ในปี ค.ศ. 1962 เป็นขั้นตอนวิธีสำหรับการคูณเลข 2 จำนวนที่มีค่ามากๆ หรือการคูณกันของพหุนามโดยใช้ขั้นตอนวิธีแบ่งแยกและเอาชนะ (Divide and conquer algorithm)

ขั้นตอนวิธีของคาราซูบาเป็นการคูณแบบเร็วโดยที่มีประสิทธิภาพเชิงเวลา (time complexity) เป็นสัญกรณ์โอใหญ่คือ O(n^1.58) มีความเร็วกว่าขั้นตอนวิธีการคูณแบบธรรมดา (grade-school multiplication) ซึ่งมีประสิทธิภาพเชิงเวลาเป็น O(n²)

กระบวนการของขั้นตอนวิธีของคาราซูบาและการวิเคราะห์ประสิทธิภาพเชิงเวลา

การคูณ เลข 2 จำนวน x, y ที่มีขนาด n หลัก เราสามารถเขียน x, y ใหม่ โดยใช้ จำนวน m โดยที่ m<n โดยที่เราจะเลือก m = n/2

x = x₁10^m+x₀

y = y₁10^m+y₀

ดังนั้น x คูณ y จะได้เป็น

xy = ( x₁10^m+x₀) (y₁10^m+y₀)

xy = x₁ y₁10^2m+ (x₁ y₀+ x₀ y₁)10^m+ x₀ y₀

กำหนดให้

A = x₁y₁

B = x₀y₀

C = (x₁+x₀)(y₁+y₀)

จะได้

xy = A10^2m+(C-A-B) 10^m+B

ซึ่งจะเห็นได้ว่าเกิดการคูณกันแค่ 3 ครั้ง คือ A, B, C เกิดการบวกกัน 4 ครั้ง ลบกัน 2 ครั้ง โดยที่การบวก และการลบใช้เวลาคงตัวโดยใช้เวลาเป็นเชิงเส้น

ดังนั้น ประสิทธิภาพเชิงเวลา ของขั้นตอนวิธีของคาราซูบา โดยที่ n เป็นจำนวนหลักคือ

T (n) = 3T (n/2) +O (n)

โดยที่ 3T (n/2) มาจาก 3 คือการที่เราแบ่งแล้วเกิดการคูณกัน 3 ที n/2 มาจากที่เราแบ่งจำนวนหลักของข้อมูลเป็นครึ่งหนึ่ง

จาก T (n) = 3T (n/2) +O (n) เราสามารถใช้ master theorem ลดรูปจนได้ T (n) = O (n^{log 3/log 2}) ≈ O (n^1.58)

รหัสเทียม

//input x, y (n digit integers) //output x*y  def karatsuba(x, y) {  if(n = 1)  return x * y  else  //แบ่ง x, y เป็นครึ่งๆ  x = x1 * 10^(n/2) + x0  y = y1 * 10^(n/2) + y0  A = karatsuba(x1,y1)  B = karatsuba(x0,y0)  C = karatsuba(x1 + x0, y1 + y0)  D = C - A - B  return A * 10^n + D * 10^(n/2) + B } 

กราฟเปรียบเทียบระหว่างการคูณธรรมดาและขั้นตอนวิธีการคูณแบบคาราซูบา

ตัวอย่าง

การคูณเลข 2 จำนวน 5678×8765

5678 = 56×10² + 78

8765 = 87×10² + 65

5678×8765 = (56×10² + 78)(87×10² + 65)

= (56×87) 10⁴ + ((56+78)(87+65) − (56×87) − (78×65)) 10² + (78×65)

= 4872×10⁴ + 10426×10² + 5070

= 49767670

การคูณของพหุนาม 2 จำนวน (a + bx) (c + dx)

(a + bx)(c + dx) = ac + ((a+b)(c+d) − ac − bd)x + bdx²

= ac + (ad+bc)x + bdx²

อ้างอิง

1. http://www.mi.ras.ru/~karatsuba/index_e.html
2. A. Karatsuba and Yu. Ofman (1962). "Multiplication of Many-Digital Numbers by Automatic Computers". Proceedings of the USSR Academy of Sciences 145: 293–294
3. http://www.ccas.ru/personal/karatsuba/divcen.htm

• http://saahiihii.com/images/story/ENUBusiness1354DOCUMENT2.pdf
• http://ozark.hendrix.edu/~burch/proj/karat/results.html 2011-07-22 ที่ เวย์แบ็กแมชชีน

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

• ทดลองขั้นตอนวิธีของคาราซูบา