จาก 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 }
A. Karatsuba and Yu. Ofman (1962). "Multiplication of Many-Digital Numbers by Automatic Computers". Proceedings of the USSR Academy of Sciences 145: 293–294
นตอนว, ของคาราซ, บา, งกฤษ, karatsuba, algorithm, เป, นตอนว, นพบโดย, anatolii, alexeevitch, karatsuba, ในป, 1960, และต, มพ, ในป, 1962, เป, นข, นตอนว, สำหร, บการค, ณเลข, จำนวนท, ามากๆ, หร, อการค, ณก, นของพห, นามโดยใช, นตอนว, แบ, งแยกและเอาชนะ, divide, conquer, a. khntxnwithikhxngkharasuba xngkvs Karatsuba algorithm epn khntxnwithi thikhnphbody Anatolii Alexeevitch Karatsuba 1 inpi kh s 1960 aelatiphimphinpi kh s 1962 2 epnkhntxnwithisahrbkarkhunelkh 2 canwnthimikhamak hruxkarkhunknkhxngphhunamodyichkhntxnwithiaebngaeykaelaexachna Divide and conquer algorithm khntxnwithikhxngkharasubaepnkarkhunaebberwodythimiprasiththiphaphechingewla time complexity epnsykrnoxihykhux O n1 58 mikhwamerwkwakhntxnwithikarkhunaebbthrrmda grade school multiplication sungmiprasiththiphaphechingewlaepn O n2 enuxha 1 krabwnkarkhxngkhntxnwithikhxngkharasubaaelakarwiekhraahprasiththiphaphechingewla 2 rhsethiym 3 krafepriybethiybrahwangkarkhunthrrmdaaelakhntxnwithikarkhunaebbkharasuba 4 twxyang 5 xangxing 6 aehlngkhxmulxunkrabwnkarkhxngkhntxnwithikhxngkharasubaaelakarwiekhraahprasiththiphaphechingewla aekikhkarkhun elkh 2 canwn x y thimikhnad n hlk erasamarthekhiyn x y ihm odyich canwn m odythi m lt n odythieracaeluxk m n 2 x x110m x0 dd dd dd dd y y110m y0 dd dd dd dd dngnn x khun y caidepn xy x110m x0 y110m y0 xy x1 y1102m x1 y0 x0 y1 10m x0 y0 dd dd dd dd kahndih A x1y1 B x0y0 C x1 x0 y1 y0 dd dd dd dd caid xy A102m C A B 10m B dd dd dd dd sungcaehnidwaekidkarkhunknaekh 3 khrng khux A B C ekidkarbwkkn 4 khrng lbkn 2 khrng odythikarbwk aelakarlbichewlakhngtwodyichewlaepnechingesndngnn prasiththiphaphechingewla khxngkhntxnwithikhxngkharasuba odythi n epncanwnhlkkhuxT n 3T n 2 O n dd dd dd odythi 3T n 2 macak 3 khuxkarthieraaebngaelwekidkarkhunkn 3 thi n 2 macakthieraaebngcanwnhlkkhxngkhxmulepnkhrunghnungcak T n 3T n 2 O n erasamarthich master theorem ldrupcnid T n O nlog 3 log 2 O n1 58 rhsethiym aekikh input x y n digit integers output x y def karatsuba x y if n 1 return x y else aebng x y epnkhrung 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 krafepriybethiybrahwangkarkhunthrrmdaaelakhntxnwithikarkhunaebbkharasuba aekikh twxyang aekikhkarkhunelkh 2 canwn 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 dd dd dd dd dd dd karkhunkhxngphhunam 2 canwn 3 a bx c dx a bx c dx ac a b c d ac bd x bdx2 ac ad bc x bdx2 dd dd dd dd dd dd xangxing aekikh http www mi ras ru karatsuba index e html A Karatsuba and Yu Ofman 1962 Multiplication of Many Digital Numbers by Automatic Computers Proceedings of the USSR Academy of Sciences 145 293 294 http www ccas ru personal karatsuba divcen htm http saahiihii com images story ENUBusiness1354DOCUMENT2 pdf http ozark hendrix edu burch proj karat results htmlaehlngkhxmulxun aekikhthdlxngkhntxnwithikhxngkharasubaekhathungcak https th wikipedia org w index php title khntxnwithikhxngkharasuba amp oldid 4860753, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
