Chulalongkorn University Theses and Dissertations (Chula ETD)

อัลกอริทึมการลบและการหารสำหรับระบบจำนวนฐานคู่

Other Title (Parallel Title in Other Language of ETD)

Subtraction and division algorithm for double base number system

Year (A.D.)

2009

Document Type

Thesis

First Advisor

อรรถสิทธิ์ สุรฤกษ์

Faculty/College

Faculty of Engineering (คณะวิศวกรรมศาสตร์)

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

วิทยาศาสตร์คอมพิวเตอร์

DOI

10.58837/CHULA.THE.2009.1326

Abstract

ระบบจำนวนมีบทบาทสำคัญต่อความเร็วในการคำนวณทางเลขคณิตในระบบคอมพิวเตอร์ ดังนั้นจึงมีการออกแบบระบบจำนวนชนิดใหม่เป็นจำนวนมาก ซึ่งระบบจำนวนฐานคู่เป็นระบบจำนวนระบบหนึ่งที่ถูกคิดค้นขึ้นมาเพื่อเพิ่มประสิทธิภาพในการคำนวณ ระบบจำนวนฐานคู่เป็นระบบที่ใช้แสดงจำนวนเต็มบวก โดยใช้ฐานสองฐาน คือ 2 และ 3 จุดเด่นของระบบจำนวนนี้คือความซ้ำซ้อนสูง และการกระจายตัวสูง มีงานวิจัยหลายงานที่ได้นำเสนอเกี่ยวกับตัวปฏิบัติการพื้นฐานของระบบจำนวนนี้ ซึ่งได้นำเสนอกระบวนการบวก และกระบวนการคูณเท่านั้นงานวิจัยนี้จึงนำเสนออัลกอริทึมการลบ และอัลกอริทึมการหารสำหรับระบบจำนวนฐานคู่ที่มีการทำงานเชิงกำหนด เทคนิคการสลับบิตและการบวกถูกนำมาใช้ในอัลกอริทึมการลบ ซึ่งผลลัพธ์ของการลบจะอยู่ในรูปแบบแทนจำนวนในระบบจำนวนฐานคู่ กระบวนการลบมีความซับซ้อนเชิงเวลาไม่เกินเวลาโพลีโนเมียล ส่วนกระบวนการหารนั้นจะสร้างจากกระบวนการบวก กระบวนการคูณที่มีอยู่ก่อนแล้ว และกระบวนการลบที่สร้างขึ้นมาใหม่ พร้อมทั้งพิสูจน์ความถูกต้องของอัลกอริทึมทั้งสอง

Other Abstract (Other language abstract of ETD)

The number system plays an important role in computer arithmetic especially on the speed of computation. Several number systems have been introduced for that reason. A double base number system has been introduced for improving the performance of arithmetic. This system can represent only non-negative numbers by using two and three as the bases. The redundancy is the prominent point of this number system. Fundamental arithmetic operations such as addition and multiplication are the majority of research in this system. Our research is focused on an implementation for subtraction and division operations. The finite state algorithm is introduced for subtraction and division operations. One-complement technique and addition technique are applied to our algorithm to accomplish the subtraction. Theoretical results show that the proposed subtraction can be realized for double base number system. The time complexity of subtraction algorithm is polynomial on the size of the operands. For division, addition technique, multiplication technique and a new subtraction technique are applied into this algorithm to accomplish the division. The proof of algorithm is also provided in our research

Link to Full Text

Share

COinS