เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
|
|
|
== ประวัติของคารัดรัตซูบะ ==
'''ขั้นตอนวิธีของคารัดรัตซูบะ''' ({{lang-en|Karatsuba algorithm}}) เป็น [[ขั้นตอนวิธี]] ที่ค้นพบโดย [[:en:Anatolii Alexeevitch Karatsuba|Anatolii Alexeevitch Karatsuba]]<ref>http://www.mi.ras.ru/~karatsuba/index_e.html</ref> ในปี ค.ศ. 1960 และตีพิมพ์ในปี ค.ศ. 1962<ref>A. Karatsuba and Yu. Ofman (1962). "Multiplication of Many-Digital Numbers by Automatic Computers". Proceedings of the USSR Academy of Sciences 145: 293–294</ref> เป็นขั้นตอนวิธีสำหรับ[[การคูณ]]เลข 2 จำนวนที่มีค่ามากๆ หรือการคูณกันของ[[พหุนาม]]โดยใช้[[ขั้นตอนวิธีแบบการแบ่งแยกและเอาชนะ]] ([[:en:Divide and conquer algorithm|Divide and conquer algorithm]])
== กระบวนการของขั้นตอนวิธีของคารัดรัตซูบะและการวิเคราะห์ประสิทธิภาพเชิงเวลา<ref>http://saahiihii.com/images/story/ENUBusiness1354DOCUMENT2.pdf</ref> ==
การคูณ เลข 2 จำนวน x, y ที่มีขนาด n หลัก เราสามารถเขียน x, y ใหม่ โดยใช้ จำนวน m โดยที่ m<n โดยที่เราจะเลือก m = n/2
:::::x = x<sub>1</sub>10<sup>m</sup>+x<sub>0</sub>
</source>
== กราฟเปรียบเทียบระหว่างการคูณธรรมดาและขั้นตอนวิธีการคูณแบบคารัดรัตซูบะ<ref>http://ozark.hendrix.edu/~burch/proj/karat/results.html</ref> ==
[[File:Graphkaratsuba.gif|center]]
== เพิ่มเติม ==
[http://www.cs.pitt.edu/~kirk/cs1501/animations/Karatsuba.html ทดลองขั้นตอนวิธีของคารัดรัตซูบะ]
[[หมวดหมู่:ขั้นตอนวิธี]]
|
