An algorithm to compute integer ηth roots using subtractions

Abstract

This work presents two algorithms based on a finite-difference method to calculate the integer ηth root y of an integer number x. The algorithm ηRA uses only additions and subtractions to calculate y. The algorithm is extremely simple and takes time and space O(η) to calculate the ηth root. The algorithm FηRA divides x in group of digits to calculate y; it has a temporal and spatial complexity of and O(η²), respectively. The set of operations of FηRA also includes multiplications and divisions. The algorithms were compared theoretically and empirically against binary search and a numerical method that calculate y. Results show that ηRA has a good performance when the quotient (log ₂ x)/η is small, and FηRA presents a fair performance when η is small in comparison with log ₂ x. An additional contribution is a short addition chain for the sequence {1^η, 2^η, …, y ^η} produced by ηRA.

Keywords:

• integer ηth root
• algorithm
• addition chain

2010 AMS Subject Classifications :

• 49M15
• 49M25
• 65D15
• 65L12
• 68Q25

Acknowledgements

This research was partially funded by the following projects: CONACyT 58554-Cálculo de Covering Arrays, 51623-Fondo Mixto CONACyT y Gobierno del Estado de Tamaulipas.