ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของคาราซูบา"

::::: x = x₁10^m+x₀

::::: y = y₁10^m+y₀

::::: xy = ( x₁10^m+x₀) (y₁10^m+y₀) <br />

::::: 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<br />

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

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

:::: T (n) = 3T (n/2) +O (n)<br />

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

: จาก T (n) = 3T (n/2) +O (n) เราสามารถใช้ [[:en:master theorem|master theorem]] ลดรูปจนได้ T (n) = O (n^{log 3/log 2}) ≈ '''O (n^1.58)'''<br />

1: //input x, y (n digit integers)

2: //output x*y

4: int karatsuba(int x, int 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: }

:::: 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 จำนวน<ref>http://www.ccas.ru/personal/karatsuba/divcen.htm</ref> (a + bx) (c + dx)

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

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