I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?
[Math] Square root algorithm
algorithmscomputational-number-theoryna.numerical-analysis
algorithmscomputational-number-theoryna.numerical-analysis
I would like an efficient algorithm for square root of a positive integer. Is there a reference that compares various square root algorithms?
Best Answer
There are many algorithms that are suitable for different contexts. Asymptotically, a combination of Newton's method with FFT is the best known method according to R. P. Brent Multiple-precision zero-finding methods and the complexity of elementary function evaluation [Analytic computational complexity (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1975), 151–176; MR0423869]. However, for numbers with up to a million digits, Zimmerman's Karatsuba square root algorithm gives better results. For numbers up to 50 digits or so, a good implementation of the traditional schoolbook method is perhaps even better.