Chulalongkorn University Theses and Dissertations (Chula ETD)
การดำเนินการฟื้นฐานเลขคณิตสำหรับระบบจำนวนมอดุลาร์ซ้ำซ้อน
Other Title (Parallel Title in Other Language of ETD)
Fundamental arithmetic operation in redundant modular number system
Year (A.D.)
2008
Document Type
Thesis
First Advisor
อรรถสิทธิ์ สุรฤกษ์
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Degree Name
วิทยาศาสตรมหาบัณฑิต
Degree Level
ปริญญาโท
Degree Discipline
วิทยาศาสตร์คอมพิวเตอร์
DOI
10.58837/CHULA.THE.2008.1276
Abstract
ระบบจำนวนมอดุลาร์แบบพหุนามเหมาะสมสำหรับการคำนวณที่รวดเร็ว การดำเนินการพื้นฐานเลขคณิตสามารถดำเนินการโดยใช้รูปแบบความซ้ำซ้อนของพหุนามที่มีค่าเป็นศูนย์ แต่การบวกและการลบไม่สามารถรับประกันได้ว่าจะสิ้นสุดภายในเวลาคงที่ ความซับซ้อนเชิงเวลาได้รับการพิสูจน์ว่าแปรผันตรงตามจำนวนตัวเลข ในงานวิจัยนี้ เราได้เสนออัลกอริทึมใหม่สำหรับการบวก การลบ และการคูณ (อาจเรียกว่า การแปลงชุดตัวเลข) ซึ่งแนวคิดของเราสำหรับอัลกอริทึมนี้สนใจตัวทดทุกตัวที่เป็นไปได้ และระบุความสัมพันธ์ของตัวทดที่เป็นฟังก์ชันประกอบอย่างชัดเจน ผลลัพธ์ทางทฤษฎีแสดงให้เห็นว่าผลลัพธ์จากอัลกอริทึมของเราได้รูปแบบแทนจำนวนที่มีคุณสมบัติที่ต้องการ ความซับซ้อนเชิงเวลาในการคำนวณนั้นถูกแสดงให้เห็นว่าลดลง ซึ่งจะเป็นค่าคงที่เมื่อจำนวนหลักของรูปแบบแทนจำนวนเป็นค่าคงที่
Other Abstract (Other language abstract of ETD)
A polynomial modular number system is shown to be suitable for fast computation. Fundamental arithmetic operations can be performed using zero-polynomial redundant form. Unfortunately, addition and subtraction cannot be guaranteed to terminate within a constant time. Time complexity is proved to be linear on the number of digits. In this thesis, we propose a novel algorithm for addition, subtraction and multiplication (i.e., probably called a digit-set conversion) where our concept of the algorithm is to focus on all possible carries, and to describe their relationship which is expressed by a composite function. Theoretical result shows that the result obtained from our algorithm always satisfy the representation property. Computational time complexity is demonstrated to be decreased where the base of the system is fixed.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
อยู่เย็น, สัพพชัย, "การดำเนินการฟื้นฐานเลขคณิตสำหรับระบบจำนวนมอดุลาร์ซ้ำซ้อน" (2008). Chulalongkorn University Theses and Dissertations (Chula ETD). 67137.
https://digital.car.chula.ac.th/chulaetd/67137