skip to main content
article
Free Access

More on computing roots of integers

Published:01 August 1975Publication History
Skip Abstract Section

Abstract

Recently John Fitch [FITC 74] gave an algorithm for computing [A1/n] where A and n are positive integers. His algorithm, based on the classical Newton method, has the virtue of not only being an extremely simple algorithm but it is also fast - both in practice and in theory. One can hardly hope to improve upon an algorithm with such virtues. In this note I will present and analyze the computing time of a variation of the algorithm presented by Fitch. The variation is superior to Fitch's version in the sense that in some cases the theoretical computing time of the new version is dominated by the theoretical computing time of Fitch's version. I do not know which algorithm is faster in practice. I doubt that there is any significant difference for most problems of interest. Certainly Fitch's version is easier to program.

References

  1. {AHU 74} Alfred V. Aho, John E. Hopcroft, and Jeffery D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley Publishing Co., Reading, Mass., 1974. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. {FITC 74} John Fitch, A Simple Method of Taking nth Roots of Integers, SIGSAM Bulletin, Vol. 8, No. 4 (Nov. 1974), p. 26. Google ScholarGoogle ScholarDigital LibraryDigital Library

Recommendations

Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Sign in

Full Access

  • Published in

    cover image ACM SIGSAM Bulletin
    ACM SIGSAM Bulletin  Volume 9, Issue 3
    August 1975
    32 pages
    ISSN:0163-5824
    DOI:10.1145/1088309
    Issue’s Table of Contents

    Copyright © 1975 Author

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    • Published: 1 August 1975

    Check for updates

    Qualifiers

    • article

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader