Analysis on Yu et al.’s dynamic algorithm for canonic DBC

Sookyung Eom, Hyang Sook Lee, Seongan Lim, Kyunghwan Song

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)31-40
Number of pages10
JournalDiscrete Applied Mathematics
Volume294
DOIs
StatePublished - 15 May 2021

Keywords

  • Double-base chain
  • Hamming weight
  • Scalar multiplication

Fingerprint

Dive into the research topics of 'Analysis on Yu et al.’s dynamic algorithm for canonic DBC'. Together they form a unique fingerprint.

Cite this