Fast exponentiation using the truncation operation

Nader H. Bshouty, Yishay Mansour, Baruch Schieber, Prasson Tiwari

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

Given an integer k, and an arbitrary integer greater than {Mathematical expression}, we prove a tight bound of {Mathematical expression} on the time required to compute {Mathematical expression} with operations {+, -, *, /, ⌊·⌋, ≤}, and constants {0, 1}. In contrast, when the floor operation is not available this computation requires Ω(k) time. Using the upper bound, we give an {Mathematical expression} time algorithm for computing ⌊log log a⌋, for all n-bit integers a. This upper bound matches the lower bound for computing this function given by Mansour, Schieber, and Tiwari. To the best of our knowledge these are the first non-constant tight bounds for computations involving the floor operation.

Original languageEnglish (US)
Pages (from-to)244-255
Number of pages12
JournalComputational Complexity
Volume2
Issue number3
DOIs
StatePublished - Sep 1 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics

Keywords

  • Subject classifications: 68Q40

Fingerprint Dive into the research topics of 'Fast exponentiation using the truncation operation'. Together they form a unique fingerprint.

Cite this