Wikipedia:Reference desk/Archives/Mathematics/2019 December 17

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 17

History of exponentiation by squaring

When was exponentiation by squaring first published/adopted? The WP article gives a 1986 paper but that sounds rather late. My GScholar-fu found only noise (hard to find non-trivial keywords if the expression was not established at first).

(Why I am asking: I just read a 1992 PhD thesis in physics where the author reinvents it without citing anyone and as a consequence devotes six pages to what could have been a single sentence, so I am wondering whether it was really unknown at that time.) Tigraan^{Click here to contact me} 15:30, 17 December 2019 (UTC)

This paper says it's over 2,000 years old, and gives a pointer to Knuth (color me not surprised), which discusses some of the history:

Donald E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison-Wesley, Reading, Massachusetts, second edition, 1981.

–Deacon Vorbis (carbon • videos) 16:10, 17 December 2019 (UTC)

It doesn't surprise me much that this is ancient. It's not too hard to realise that if you want to compute x⁴, it's easier to compute x² and then square it again, than to compute all intermediate powers. A little bit of tinkering later leads to the complete method. So I suspect that this would have been invented, written down, forgotten, and reinvented many times.

This question has previously been asked on Math Overflow, where one of the answerers (Carlo Beenakker) quotes the passage from Knuth:

The method is quite ancient; it appeared before 200 B.C. in Pingala's Hindu classic Chandah-sutra [see B. Datta and A.N. Singh, History of Hindu Mathematics 1, 1935]; however, there seem to be no other references to this method outside of India during the next 1000 years. A clear discussion of how to compute 2ⁿ efficiently for arbitrary n was given by al-Uqlidisi of Damscus in 952 A.D.; see The Arithmetic of al-Uglidisi by A.S. Saidan (1975), p. 341-342, where the general ideas are illustrated for n = 51. See also al-Biruni's Chronology of Ancient Nations (1879), p. 132-136; this eleventh-century Arabic work had great influence.

More information about Pingala's method can be found in this paper (linked in the same answer). Double sharp (talk) 04:23, 18 December 2019 (UTC)