Binary addition chain on EREW PRAM
Fathy, Khaled A.; Bahig, Hazem; Ragb, A. A.;
Abstract
An addition chain for a natural number x of n bits is a sequence of numbers a , a , ... , a , such that a = 1, a = x, and a = a + a with 0 ≤ i,j < k ≤ l. The addition chain problem is what is the minimal number of additions needed to compute x starting from 1? In this paper, we present a new parallel algorithm to generate a short addition chain for x. The algorithm has running time O(log n) using polynomial number processors under EREW PRAM (exclusive read exclusive write parallel random access machine). The algorithm is faster than previous algorithms and is based on binary method. © 2011 Springer-Verlag. 0 1 l 0 l k i j 2
Other data
| Title | Binary addition chain on EREW PRAM | Authors | Fathy, Khaled A.; Bahig, Hazem ; Ragb, A. A. | Keywords | Addition chain;binary method;EREW PRAM;parallel algorithm | Issue Date | 9-Nov-2011 | Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Start page | 321 | End page | 330 | ISBN | 9783642246685 | ISSN | 03029743 | DOI | 10.1007/978-3-642-24669-2_31 | Scopus ID | 2-s2.0-80455144541 |
Recommend this item
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.