tag:blogger.com,1999:blog-3722233.post116903194294484591..comments2023-09-28T12:45:24.391-05:00Comments on Computational Complexity: Computing Square RootsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-3722233.post-1171671047551345272007-02-16T18:10:00.000-06:002007-02-16T18:10:00.000-06:00Is it possible to download pages of square/square ...Is it possible to download pages of square/square roots and cube roots tables from the 'CRC' Mathematical Tables? Are they available on Google? I want my students to learn from them.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169872413744972102007-01-26T22:33:00.000-06:002007-01-26T22:33:00.000-06:00..and the BBC's take on it...and the <A HREF="http://www.bbc.co.uk/dna/h2g2/A827453" REL="nofollow">BBC's take</A> on it.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169480425698715052007-01-22T09:40:00.000-06:002007-01-22T09:40:00.000-06:00The technique isn't Newton's method. Newton's met...The technique isn't Newton's method. <BR/>Newton's method is slow by hand because of all those divisions by x_n; the method Lance links to (which my middle-school math teacher enjoyed showing when he could) is much better optimized for pencil-and-paper work. Check it out if you've never seen it.<BR/><BR/>Googling finds <A HREF="http://www.homeschoolmath.net/teaching/square-root-algorithm.php" REL="nofollow">another exposition</A> with a good discussion in the comments of when this method makes more sense and when Newton's method (apparently aka "the Babylonian method" when specialized to square roots) does.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169471266527976122007-01-22T07:07:00.000-06:002007-01-22T07:07:00.000-06:00Siva says,Teaching the long division or sqrt algor...Siva says,<BR/><BR/><I>Teaching the long division or sqrt algorithm is a great exercise in developing the notion of a correctness proof ..., and is probably a good topic for early high school, about 9th or 10th grade.</I><BR/><BR/>The sqrt algorithm is perhaps appropriate for 9th or 10th grade, but long division? Long division (and shift-and-add multiplication as well) should be taught much earlier and learned <B>by rote</B>. Let the correctness idea come later. The great benefit of this approach is that the student can do these operations quickly and without thinking. They can then use these skills (for example) in further mathematical discovery, such as prime factorizations of numbers.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169186294839819442007-01-18T23:58:00.000-06:002007-01-18T23:58:00.000-06:00In response to the comment I feel it's OK if chi...In response to the comment <I> <BR/>I feel it's OK if children don't remember the sqrt algorithm, but faced with a non-electronics situation, I'd hope that they have enough mathematical intuition to do a decent guess and verify...</I><BR/><BR/>steve fenner asks:<BR/><BR/><B><BR/>What do you think about other rote hand algorithms, such as long division and the usual shift-and-add method of multiplication? I ask because there are movements afoot to forgo teaching these in favor of developing the grade school student's "mathematical intuition." I think it's a terrible idea to do this.<BR/></B><BR/><BR/>As long as a student understands why she is doing what she is doing, any algorithm is fine -- in other words, if you're going to hand-execute an algorithm, you should at least have a good sense of the proof of correctness of the algorithm, at least intuitively. I think the correctness of the shift-and-add multiplication algorithm is relatively easy to see, for someone at the 4th -- 6th grade level. The correctness of long division (and of the sqrt algorithm) is a lot less obvious, and this is why I feel that recursive doubling or binary search or other forms of guess-and-verify are more reasonable, since the student has a better chance of internalizing the correctness argument with every execution. For the same reason, I think I like multiplying by appealing to the distributivity of multiplication over addition, as in 378 * 74 = (300 + 70 + 8) * (70 + 4) = 300*70 + 300*4 + 70*70 + 70*4 + 8*70 + 8*4 = whatever... while executing this, a student can mentally compute the area of a rectangle with 378 x 74 cells, which he slices as 300+70+8 in one direction, and dices as 70+4 in the other...<BR/><BR/>Teaching the long division or sqrt algorithm is a great exercise in developing the notion of a correctness proof (at least, an argument of correctness), and is probably a good topic for early high school, about 9th or 10th grade.<BR/><BR/>SivaD. Sivakumarhttps://www.blogger.com/profile/05750992965116762335noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169132934155633782007-01-18T09:08:00.001-06:002007-01-18T09:08:00.001-06:00After praying books.google.com god, we get:http://...After praying books.google.com god, we get:<BR/>http://books.google.com/books?id=peWHHhcyj_0C&dq=sqrt+algorithm+book&pg=RA3-PA123&ots=t00pZV_K94&sig=INctyYe1ZMfTTrHmTOa-fb-4ozA&prev=http://www.google.com/search%3Fhl%3Den%26q%3Dsqrt%2Balgorithm%2Bbook%26btnG%3DGoogle%2BSearch&sa=X&oi=print&ct=result&cd=2#PRA3-PA124,M1<BR/>which gives a description of sqrt algorithm -Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169132884387745332007-01-18T09:08:00.000-06:002007-01-18T09:08:00.000-06:00I agree with comment 9: Using Newton'smethod to c...I agree with comment 9: Using Newton's<BR/>method to compute square roots is fast<BR/>and easy. To find the square root<BR/>of a, make an inital guess x_1, and<BR/>use the iteration formula that x_{n+1}<BR/>is the average of x_n and a/x_n.<BR/>The number of significant digits doubles with each iteration.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169132419066065742007-01-18T09:00:00.000-06:002007-01-18T09:00:00.000-06:00I feel it's OK if children don't remember the sqrt...<I>I feel it's OK if children don't remember the sqrt algorithm, but faced with a non-electronics situation, I'd hope that they have enough mathematical intuition to do a decent guess and verify...</I><BR/><BR/>What do you think about other rote hand algorithms, such as long division and the usual shift-and-add method of multiplication? I ask because there are movements afoot to forgo teaching these in favor of developing the grade school student's "mathematical intuition." I think it's a terrible idea to do this.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169128360045553822007-01-18T07:52:00.000-06:002007-01-18T07:52:00.000-06:00It's just Newton's Method, dude...It's just Newton's Method, dude...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169124881729524292007-01-18T06:54:00.000-06:002007-01-18T06:54:00.000-06:00I learned the method from a 1928 Audels New Electr...I learned the method from a 1928 Audels New Electric Library book. This was a series of self sudy books to learn electronins (well, electricity) my father had. It was clear how to generalize the algo to nth roots. I've impressed many a junior engineer with the fact this algo even exists.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169083599774383572007-01-17T19:26:00.000-06:002007-01-17T19:26:00.000-06:00In India, we still dont use a calculator till we s...In India, we still dont use a calculator till we start BS as freshmen. In 11th and 12th, we use something called Clark's tables. Using logarithm tables to calculate roots, power, multiplication, etc.<BR/><BR/>A graphical calculator is unheard of !Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169067535249262802007-01-17T14:58:00.000-06:002007-01-17T14:58:00.000-06:00Uh, whatever happened to the most obvious guess-an...Uh, whatever happened to the most obvious guess-and-verify with a dash of binary search or interpolation search? I feel it's OK if children don't remember the sqrt algorithm, but faced with a non-electronics situation, I'd hope that they have enough mathematical intuition to do a decent guess and verify...D. Sivakumarhttps://www.blogger.com/profile/05750992965116762335noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169057074341066162007-01-17T12:04:00.000-06:002007-01-17T12:04:00.000-06:00I also learned this method, and it is definitely t...I also learned this method, and it is definitely the best if you don't have any electronics handy. About a decade ago, I taught a class using Abelson and Sussman's <I>Structure and Interpretation of Computer Programs</I> (the best programming book ever written, IMHO), and to test the use of lazy streams I implemented this method in Scheme (<A HREF="http://www.cse.sc.edu/~fenner/sqrt.scm" REL="nofollow">sqrt.scm</A> using <A HREF="http://www.cse.sc.edu/~fenner/stream.scm" REL="nofollow">stream.scm</A>). It originally ran under PC Scheme.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169051980379708612007-01-17T10:39:00.000-06:002007-01-17T10:39:00.000-06:00praying to the Google Gods.There is only one and i...<I> praying to the Google Gods.</I><BR/><BR/>There is only one and its a she:<BR/><BR/><A HREF="http://www.thechurchofgoogle.org/" REL="nofollow"> The Church of Google</A><BR/><BR/>Praise the Google!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169050660327715972007-01-17T10:17:00.000-06:002007-01-17T10:17:00.000-06:00When I saw the title of this post I was hoping to ...When I saw the title of this post I was hoping to read about a a breakthrough in the <A HREF="http://maven.smith.edu/~orourke/TOPP/P33.html#Problem.33" REL="nofollow">Sum of Square Roots</A> problem. Alas, it was not to be. So yes, to answer Kurt's question, there are still significant open problems.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169042368332285492007-01-17T07:59:00.000-06:002007-01-17T07:59:00.000-06:00But surely there are still some interesting theore...But surely there are still some interesting theoretical aspects to calculating roots, no? For example, what is the complexity of comparing two expressions involving sums of roots, etc.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1169035502604835472007-01-17T06:05:00.000-06:002007-01-17T06:05:00.000-06:00Sans computer, I often find myself using the manua...Sans computer, I often find myself using the manual method to calculate square roots (or any kind of root). It usually only takes a few iterations to have a fairly high degree of accuracy. Oftentimes it's faster than hunting around for a calculator or walking over to the PC.Anonymousnoreply@blogger.com