Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/32960
| Title: | การดำเนินการฟื้นฐานเลขคณิตสำหรับระบบจำนวนมอดุลาร์ซ้ำซ้อน |
| Other Titles: | Fundamental arithmetic operation in redundant modular number system |
| Authors: | สัพพชัย อยู่เย็น |
| Advisors: | อรรถสิทธิ์ สุรฤกษ์ |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์ |
| Advisor's Email: | Athasit.S@Chula.ac.th |
| Subjects: | ทฤษฎีจำนวนเลข จำนวนเชิงซ้อน อัลกอริทึม การแปลง (คณิตศาสตร์) Number theory Numbers, Complex Algorithms Transformations (Mathematics) |
| Issue Date: | 2551 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | ระบบจำนวนมอดุลาร์แบบพหุนามเหมาะสมสำหรับการคำนวณที่รวดเร็ว การดำเนินการพื้นฐานเลขคณิตสามารถดำเนินการโดยใช้รูปแบบความซ้ำซ้อนของพหุนามที่มีค่าเป็นศูนย์ แต่การบวกและการลบไม่สามารถรับประกันได้ว่าจะสิ้นสุดภายในเวลาคงที่ ความซับซ้อนเชิงเวลาได้รับการพิสูจน์ว่าแปรผันตรงตามจำนวนตัวเลข ในงานวิจัยนี้ เราได้เสนออัลกอริทึมใหม่สำหรับการบวก การลบ และการคูณ (อาจเรียกว่า การแปลงชุดตัวเลข) ซึ่งแนวคิดของเราสำหรับอัลกอริทึมนี้สนใจตัวทดทุกตัวที่เป็นไปได้ และระบุความสัมพันธ์ของตัวทดที่เป็นฟังก์ชันประกอบอย่างชัดเจน ผลลัพธ์ทางทฤษฎีแสดงให้เห็นว่าผลลัพธ์จากอัลกอริทึมของเราได้รูปแบบแทนจำนวนที่มีคุณสมบัติที่ต้องการ ความซับซ้อนเชิงเวลาในการคำนวณนั้นถูกแสดงให้เห็นว่าลดลง ซึ่งจะเป็นค่าคงที่เมื่อจำนวนหลักของรูปแบบแทนจำนวนเป็นค่าคงที่ |
| Other Abstract: | 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. |
| Description: | วิทยานิพนธ์ (วท.ม.)--จุฬาลงกรณ์มหาวิทยาลัย, 2551 |
| Degree Name: | วิทยาศาสตรมหาบัณฑิต |
| Degree Level: | ปริญญาโท |
| Degree Discipline: | วิทยาศาสตร์คอมพิวเตอร์ |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/32960 |
| URI: | http://doi.org/10.14457/CU.the.2008.650 |
| metadata.dc.identifier.DOI: | 10.14457/CU.the.2008.650 |
| Type: | Thesis |
| Appears in Collections: | Eng - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| sappachai_yu.pdf | 15.02 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.