A Special Algorithm to Approximate the Square Root of Positive Integer

Authors: Hsian Ming Goo

Abstract:

The paper concerns a special approximate algorithm of the square root of the specific positive integer, which is built by the use of the property of positive integer solution of the Pell’s equation, together with using some elementary theorems of matrices, and then takes it to compare with general used the Newton’s method and give a practical numerical example and error analysis; it is unexpected to find its special property: the significant figure of the approximation value of the square root of positive integer will increase one digit by one. It is well useful in some occasions.

Keywords: Special approximate algorithm, square root, Pell’s equation, Newton’s method, error analysis.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1088180

References:

[1] F. Karakus¸, ”Using history of mathematics in mathematics teaching: Babylonian square root method,” Necatibey Faculty of Education Electronic Journal of Science and Mathematics Education, vol. 3, no. 1, pp. 195-206, Jun. 2009.
[2] H. Davenport, The higher arithmetic: an introduction to the theory of numbers. Cambridge, Cambridge University Press, UK, 2008, pp. 68- 101.
[3] R. Garver, ”A square root method and continued fractions,” Amer. Math. Monthly, vol. 39, no. 9, pp. 533-535, Nov. 1932.
[4] E. B. Escott, ”Rapid method for extracting a square root,” Amer. Math. Monthly, vol. 44, no. 10, pp. 644-646, Dec. 1937.
[5] G. M. Fichtenholz, Course of calculus, vol. 2, 8th ed. Beijing, Higher Education Press, 2006, pp. 320-321. (in Chinese)
[6] J. Eve, ”Starting approximations for the iterative calculation of square roots,” The Computer Journal, vol. 6, no. 3, pp. 274-276, Nov. 1963.
[7] E. W. Weisstein, ”Pell equation” from the MathWorld-a Wolfram web resource, Sep. 29, 2011, available at the site: http://mathworld.wolfram.com/PellEquation.html
[8] G. Strang, Linear algebra and its applications, 3rd ed. Toebben Drive, Independence, KY, Brooks Cole, USA, 2005.
[9] P. A. Samet, D. W. Honey, ”Calculation of a double-length square root from double-length number using single precision techniques,” The Computer Journal, vol. 15, no. 2, pp. 116, May 1972.
[10] I. Ninomiya, ”Best rational starting approximations and improved Newton iteration for the square root,” Math. Comp., vol. 24, No. 110, pp. 391-404, Apr. 1970.
[11] J. Dutka, ”The square root of 2 to 1,000,000 decimals,” Math. Comp., Vol. 25, No. 116, pp. 927-930, Oct. 1971.
[12] H. W. Lenstra, ”Solving the Pell equation,” Notices of the Amer. Math. Soc., vol. 49, no. 2, pp. 182-192, Feb. 2002.
[13] P. C. Hammer, ”Iterative procedures for taking roots based on square roots,” Math. Comp., vol. 9, no. 50, pp. 68, Apr. 1955.
[14] S. Giberson, J. O. Thomas, ”Extending Theon’s ladder to any square root,” College Math. J., vol.35, no. 3, pp. 222-226, May 2004.
[15] D. V. Anderson, ”Iterations for the square root,” Math. Gazette, vol. 80, no. 489, pp. 574-575, Nov. 1996.
[16] M. Planitz, ”A square root algorithm,” Math. Gazette, vol. 67, no. 440, pp. 101-105, Jun. 1983.
[17] A. McBride, ”Remarks on Pell’s equation and square root algorithms,” Math. Gazette, vol. 83, no. 496, pp. 47-52, Mar. 1999.
[18] S. Thomas, ”A fancy way obtain the binary digits of 759250125√2,” Amer. Math. Monthly, vol. 118, no. 7, pp. 644-646, August-September 2010.
[19] R. L. Graham, H. O. Pollak, ”Note on a nonlinear recurrence related to √2,” Math. Mag., vol. 43, no. 3, pp. 143-145, May 1970.
[20] A. A. Blank, Problems in calculus and analysis. London John Wiley., UK, 1966.