کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6876167 | 690239 | 2014 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
k-Block parallel addition versus 1-block parallel addition in non-standard numeration systems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: k-Block parallel addition versus 1-block parallel addition in non-standard numeration systems k-Block parallel addition versus 1-block parallel addition in non-standard numeration systems](/preview/png/6876167.png)
چکیده انگلیسی
Parallel addition in integer base is used for speeding up multiplication and division algorithms. k-block parallel addition has been introduced by Kornerup in [14]: instead of manipulating single digits, one works with blocks of fixed length k. The aim of this paper is to investigate how such notion influences the relationship between the base and the cardinality of the alphabet allowing block parallel addition. In this paper, we mainly focus on a certain class of real bases - the so-called Parry numbers. We give lower bounds on the cardinality of alphabets of non-negative integer digits allowing block parallel addition. By considering quadratic Pisot bases, we are able to show that these bounds cannot be improved in general and we give explicit parallel algorithms for addition in these cases. We also consider the d-bonacci base, which satisfies the equation Xd=Xdâ1+Xdâ2+â¯+X+1. If in a base being a d-bonacci number 1-block parallel addition is possible on an alphabet A, then #A⩾d+1; on the other hand, there exists a kâN such that k-block parallel addition in this base is possible on the alphabet {0,1,2}, which cannot be reduced. In particular, addition in the Tribonacci base is 14-block parallel on alphabet {0,1,2}.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 543, 10 July 2014, Pages 52-67
Journal: Theoretical Computer Science - Volume 543, 10 July 2014, Pages 52-67
نویسندگان
Christiane Frougny, Pavel Heller, Edita Pelantová, Milena Svobodová,