TY - JOUR
T1 - Analysis on Yu et al.’s dynamic algorithm for canonic DBC
AU - Eom, Sookyung
AU - Lee, Hyang Sook
AU - Lim, Seongan
AU - Song, Kyunghwan
N1 - Funding Information:
We thanks the anonymous reviewers for their careful reading of our manuscript and their many insightful comments and suggestions. Sookyung Eom was supported by the National Research Foundation of Korea grant funded by the Korea Government (Nos. 2016R1C1B2013851 , 2018R1A2A1A05079095 , 2019R1C1C1002403 ). Hyang-Sook Lee was supported by the National Research Foundation of Korea grant funded by the Korea government (No. 2018R1A2A1A05079095 ). Seongan Lim was supported by Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Education (No. 2016R1D1A1B01008562 ). Kyunghwan Song was supported by the National Research Foundation of Korea funded by the Ministry of Education (No. 2020R1I1A1A01070546 ).
Publisher Copyright:
© 2021 Elsevier B.V.
PY - 2021/5/15
Y1 - 2021/5/15
N2 - Recently, Yu et al. presented an algorithm for a canonic DBC of a positive integer n by solving certain subproblems recursively and it requires O((logn)2loglogn) bit operations and O((logn)2) bits of memory. This is currently the most efficient recoding type algorithm for canonic DBCs when balanced computing power and memory are available. In this paper, we present a memory efficient algorithm to compute a nearly DBC from the idea of Yu et al. We present a simple overview of Yu et al.’s algorithm focusing on canonic DBC and refine Yu et al.’s proof for range of the leading term of canonic DBCs. By using the refined range, we suggest how to improve the efficiency of Yu et al.’s algorithm computationally and present an algorithm for nearly canonic DBC with memory requirement O(logn). We also present experimental comparison on the Hamming weights of Yu et al.’s algorithm, tree based algorithm, the classic greedy DBC algorithm, and our memory efficient algorithm.
AB - Recently, Yu et al. presented an algorithm for a canonic DBC of a positive integer n by solving certain subproblems recursively and it requires O((logn)2loglogn) bit operations and O((logn)2) bits of memory. This is currently the most efficient recoding type algorithm for canonic DBCs when balanced computing power and memory are available. In this paper, we present a memory efficient algorithm to compute a nearly DBC from the idea of Yu et al. We present a simple overview of Yu et al.’s algorithm focusing on canonic DBC and refine Yu et al.’s proof for range of the leading term of canonic DBCs. By using the refined range, we suggest how to improve the efficiency of Yu et al.’s algorithm computationally and present an algorithm for nearly canonic DBC with memory requirement O(logn). We also present experimental comparison on the Hamming weights of Yu et al.’s algorithm, tree based algorithm, the classic greedy DBC algorithm, and our memory efficient algorithm.
KW - Double-base chain
KW - Hamming weight
KW - Scalar multiplication
UR - http://www.scopus.com/inward/record.url?scp=85100671820&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2021.01.023
DO - 10.1016/j.dam.2021.01.023
M3 - Article
AN - SCOPUS:85100671820
VL - 294
SP - 31
EP - 40
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
ER -