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

ขั้นตอนวิธีของคาราซูบา ()  เป็น ขั้นตอนวิธี ที่ค้นพบโดย Anatolii Alexeevitch Karatsubahttp://www.mi.ras.ru/~karatsuba/index_e.html ในปี ค.ศ. 1960 และตีพิมพ์ในปี ค.ศ. 1962A. Karatsuba and Yu. Ofman (1962). "Multiplication of Many-Digital Numbers by Automatic Computers". Proceedings of the USSR Academy of Sciences 145: 293–294 เป็นขั้นตอนวิธีสำหรับการคูณเลข 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)

 รหัสเทียม 
//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
}

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

 ตัวอย่าง 
การคูณเลข 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 จำนวนhttp://www.ccas.ru/personal/karatsuba/divcen.htm (a + bx) (c + dx)
 (a + bx)(c + dx) = ac + ((a+b)(c+d) − ac − bd)x + bdx2
 = ac + (ad+bc)x + bdx2

 อ้างอิง 

 http://saahiihii.com/images/story/ENUBusiness1354DOCUMENT2.pdf
 http://ozark.hendrix.edu/~burch/proj/karat/results.html 

 แหล่งข้อมูลอื่น 
 ทดลองขั้นตอนวิธีของคาราซูบา

หมวดหมู่:ขั้นตอนวิธีเลขคณิตของคอมพิวเตอร์
หมวดหมู่:การคูณ