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

จากวิกิพีเดีย สารานุกรมเสรี

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

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

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

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

x = x110m+x0
y = y110m+y0

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

xy = ( x110m+x0) (y110m+y0)
xy = x1 y1102m+ (x1 y0+ x0 y1)10m+ x0 y0

กำหนดให้

A = x1y1
B = x0y0
C = (x1+x0)(y1+y0)

จะได้

xy = A102m+(C-A-B) 10m+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 (nlog 3/log 2) ≈ O (n1.58)

รหัสเทียม[แก้]

  1. //input x, y (n digit integers)
    
  2. //output x*y
    
  3.  
    
  4. def karatsuba(x, y) {
    
  5.     if(n = 1)
    
  6.         return x * y
    
  7.     else
    
  8.         //แบ่ง x, y เป็นครึ่งๆ
    
  9.         x = x1 * 10^(n/2) + x0
    
  10.         y = y1 * 10^(n/2) + y0
    
  11.         A = karatsuba(x1,y1)
    
  12.         B = karatsuba(x0,y0)
    
  13.         C = karatsuba(x1 + x0, y1 + y0)
    
  14.         D = C - A - B
    
  15.         return A * 10^n + D * 10^(n/2) + B
    
  16. }
    

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

Graphkaratsuba.gif

ตัวอย่าง[แก้]

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

5678 = 56×102 + 78
8765 = 87×102 + 65
5678×8765 = (56×102 + 78)(87×102 + 65)
= (56×87) 104 + ((56+78)(87+65) − (56×87) − (78×65)) 102 + (78×65)
= 4872×104 + 10426×102 + 5070
= 49767670
การคูณของพหุนาม 2 จำนวน[3] (a + bx) (c + dx)
(a + bx)(c + dx) = ac + ((a+b)(c+d) − ac − bd)x + bdx2
= ac + (ad+bc)x + bdx2

อ้างอิง[แก้]

  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

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