An Efficient Multicore Algorithm for Minimal Length Addition Chains
A minimal length addition chain for a positive integer m is a finite sequence of positive integers such that (1) the first and last elements in the sequence are 1 and m, respectively, (2) any element greater than 1 in the sequence is the addition of two earlier elements (not necessarily distinct), a...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-03-01
|
| Series: | Computers |
| Subjects: | |
| Online Access: | http://www.mdpi.com/2073-431X/8/1/23 |
| _version_ | 1798040743608057856 |
|---|---|
| author | Hazem M. Bahig Yasser Kotb |
| author_facet | Hazem M. Bahig Yasser Kotb |
| author_sort | Hazem M. Bahig |
| collection | DOAJ |
| description | A minimal length addition chain for a positive integer m is a finite sequence of positive integers such that (1) the first and last elements in the sequence are 1 and m, respectively, (2) any element greater than 1 in the sequence is the addition of two earlier elements (not necessarily distinct), and (3) the length of the sequence is minimal. Generating the minimal length addition chain for m is challenging due to the running time, which increases with the size of m and particularly with the number of 1s in the binary representation of m. In this paper, we introduce a new parallel algorithm to find the minimal length addition chain for m. The experimental studies on multicore systems show that the running time of the proposed algorithm is faster than the sequential algorithm. Moreover, the maximum speedup obtained by the proposed algorithm is 2.5 times the best known sequential algorithm. |
| first_indexed | 2024-04-11T22:11:47Z |
| format | Article |
| id | doaj.art-7b2d204bea9c4b8596f3137942d09ebc |
| institution | Directory Open Access Journal |
| issn | 2073-431X |
| language | English |
| last_indexed | 2024-04-11T22:11:47Z |
| publishDate | 2019-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Computers |
| spelling | doaj.art-7b2d204bea9c4b8596f3137942d09ebc2022-12-22T04:00:32ZengMDPI AGComputers2073-431X2019-03-01812310.3390/computers8010023computers8010023An Efficient Multicore Algorithm for Minimal Length Addition ChainsHazem M. Bahig0Yasser Kotb1College of Computer Science and Engineering, Hail University, Hail 81481, Kingdom of Saudi ArabiaComputer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, EgyptA minimal length addition chain for a positive integer m is a finite sequence of positive integers such that (1) the first and last elements in the sequence are 1 and m, respectively, (2) any element greater than 1 in the sequence is the addition of two earlier elements (not necessarily distinct), and (3) the length of the sequence is minimal. Generating the minimal length addition chain for m is challenging due to the running time, which increases with the size of m and particularly with the number of 1s in the binary representation of m. In this paper, we introduce a new parallel algorithm to find the minimal length addition chain for m. The experimental studies on multicore systems show that the running time of the proposed algorithm is faster than the sequential algorithm. Moreover, the maximum speedup obtained by the proposed algorithm is 2.5 times the best known sequential algorithm.http://www.mdpi.com/2073-431X/8/1/23addition chainminimal lengthparallel algorithmbranch-and-boundmulticorehigh performance computing |
| spellingShingle | Hazem M. Bahig Yasser Kotb An Efficient Multicore Algorithm for Minimal Length Addition Chains Computers addition chain minimal length parallel algorithm branch-and-bound multicore high performance computing |
| title | An Efficient Multicore Algorithm for Minimal Length Addition Chains |
| title_full | An Efficient Multicore Algorithm for Minimal Length Addition Chains |
| title_fullStr | An Efficient Multicore Algorithm for Minimal Length Addition Chains |
| title_full_unstemmed | An Efficient Multicore Algorithm for Minimal Length Addition Chains |
| title_short | An Efficient Multicore Algorithm for Minimal Length Addition Chains |
| title_sort | efficient multicore algorithm for minimal length addition chains |
| topic | addition chain minimal length parallel algorithm branch-and-bound multicore high performance computing |
| url | http://www.mdpi.com/2073-431X/8/1/23 |
| work_keys_str_mv | AT hazemmbahig anefficientmulticorealgorithmforminimallengthadditionchains AT yasserkotb anefficientmulticorealgorithmforminimallengthadditionchains AT hazemmbahig efficientmulticorealgorithmforminimallengthadditionchains AT yasserkotb efficientmulticorealgorithmforminimallengthadditionchains |