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

ขั้นตอนวิธีของคาราซูบา (อังกฤษ: 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²

อ้างอิง

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

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

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