Paper Info
Title
Binary addition chain on EREW PRAM
Abstract
An addition chain for a natural number x of n bits is a sequence of numbers a0, a1, ..., al, such that a0 = 1, al = x, and ak = ai+aj 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(log2 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.
Year
DOI
Venue
2011
10.1007/978-3-642-24669-2_31
ICA3PP (2)
Keywords
Field
DocType
n bit,binary addition chain,log2 n,short addition chain,addition chain,polynomial number processor,erew pram,natural number,previous algorithm,new parallel algorithm,addition chain problem,minimal number,parallel algorithm
Natural number,Parallel random-access machine,Polynomial,Computer science,Parallel algorithm,Parallel computing,Binary addition,Binary number,Addition chain
Conference
Volume
ISSN
Citations 
7017
0302-9743
0
PageRank 
References 
Authors
0.34
5
4
Name
Order
Citations
PageRank
Khaled A. Fathy100.34
Hazem M. Bahig2247.61
Hatem M. Bahig3237.53
A. A. Ragb400.34