A square root algorithm faster than Newton's method for multiprecision numbers, using floating-point arithmetic
A square root algorithm faster than Newton's method for multiprecision numbers, using floating-point arithmetic
In this paper, an optimized version of classical Bombelli's algorithm for computing integer square roots is presented. In particular, floating-point arithmetic is used to compute the initial guess of each digit of the root, following similar ideas to those used in "The Art of Computer Programming" Vol. 2, p. 4.3.1 for division. A program with an implementation of the algorithm in Java is also presented, and its running time is compared with that of the algorithm provided by the Java standard library, which uses the Newton's method. From tests, the algorithm presented here turns out to be much faster.
28 pages
FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Computer Science - Mathematical Software, Data Structures and Algorithms (cs.DS), Mathematics - Numerical Analysis, Numerical Analysis (math.NA), Mathematical Software (cs.MS)
FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Computer Science - Mathematical Software, Data Structures and Algorithms (cs.DS), Mathematics - Numerical Analysis, Numerical Analysis (math.NA), Mathematical Software (cs.MS)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!