206
Views
1
CrossRef citations to date
0
Altmetric
Section A

An algorithm to compute integer ηth roots using subtractions

, &
Pages 1629-1643 | Received 30 Jun 2010, Accepted 28 Sep 2010, Published online: 23 Mar 2011
 

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 O2), 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 2 x)/η is small, and FηRA presents a fair performance when η is small in comparison with log 2 x. An additional contribution is a short addition chain for the sequence {1η, 2η, …, y η} produced by ηRA.

2010 AMS Subject Classifications :

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.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.