ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธีของคาราซูบา"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
Octahedron80 (คุย | ส่วนร่วม) ล ขั้นตอนวิธีของคะระสึบะ ถูกเปลี่ยนชื่อเป็น ขั้นตอนวิธีของคาราซูบา: Karatsuba เป็นชาวรัสเซีย... |
Octahedron80 (คุย | ส่วนร่วม) Karatsuba (Карацу́ба) เป็นชาวรัสเซีย ไม่ใช่ญี่ปุ่น |
||
บรรทัด 1:
'''ขั้นตอนวิธีของ
▲'''ขั้นตอนวิธีของคะระสึบะ''' ({{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]])
== กระบวนการของขั้นตอนวิธีของ
การคูณ เลข 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>
เส้น 48 ⟶ 47:
</source>
== กราฟเปรียบเทียบระหว่างการคูณธรรมดาและขั้นตอนวิธีการคูณแบบ
[[File:Graphkaratsuba.gif|center]]
เส้น 67 ⟶ 66:
== เพิ่มเติม ==
[http://www.cs.pitt.edu/~kirk/cs1501/animations/Karatsuba.html ทดลองขั้นตอนวิธีของ
[[หมวดหมู่:ขั้นตอนวิธี]]
| |||