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.
- {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 ScholarDigital Library
- {FITC 74} John Fitch, A Simple Method of Taking nth Roots of Integers, SIGSAM Bulletin, Vol. 8, No. 4 (Nov. 1974), p. 26. Google ScholarDigital Library
Recommendations
Cloud Computing: Interview with Russ Daniels and Franco Travostino
Milojicić discusses cloud computing with Russ Daniels, Vice President and Chief Technology Officer of Hewlett-Packard’s cloud services strategy, and Franco Travostino, a distinguished architect at eBay.
Association for Computing Machinery (ACM) Annual Meeting interview: August 30, 1967
Computer Oral History CollectionThis was a panel discussion given at the annual meeting of the Association for Computing Machinery entitled "In the Beginning, Reminiscences of the Creators." Several individuals participated in this discussion: Issac Auerbach, Bruce Gilchrist, Sam ...
Leadership in Computing History: Arthur Norberg and the Charles Babbage Institute
This article describes the Charles Babbage Institute's leadership role in the computing history profession. Much of the article's focus is on Arthur Norberg, the Institute's director during most of its first quarter century, and on his role in shaping ...
Comments