Even rough interpolation converges pretty fast for plain vanilla square roots, especially if you don't need an answer accurate to more than a few decimals. Newton-Raphson or more sophisticated methods can be a big win for more complicated functions, of course.
Estimate sqrt(17):
Clearly it has to be between 4 and 5.
Try 4.5. Result: 20.25
Try 4.2. Result: 17.64
Try 4.1. Result: 16.81
Try 4.15. Result: 17.01. Probably good enough for most practical purposes.
An engineer friend memorized the first 4 digits of all square roots from 1 to 100 which you can quickly turn into a great approximation. AKA sqrt(1730) is between 4.123 * 10 and 4.242 * 10. Even better 30 is low so it's between 41.23 and (4.242+4.123) / 2 * 10 = 41.825.
In this case the value is sanity checking a calculator / program.
I assume because he regularly worked with formulas involving squares and square roots. This is a guy who did long division in his head on long car rides to stay awake. He also memorized the square and cube of every number from 1 to 100.
His justification for starting was trying to keep track of the order of magnitude of everything he calculated to catch fat finger mistakes. And a sanity check. However, you need a few digits on the front of a number before you can really safely keep track of exponents that way.
Actually, it's clearly much closer to 4 than 5 - So I'd probably start at 4.1 or 4.2.
There are 12 numbers from 4.0 through 5.0 inclusive - in steps of 0.1, and there are 10 integer numbers from 16 through 25 inclusive - clearly there's an uneven, but still somewhat smooth mapping from one through the other via the square function (or root function, for that matter). It's easy to see (note that python rounds down up to .5 inclusive):
for i in range(40, 51):
n=i/10.0
print(n, round(n**2))
4.0 16
4.1 17
4.2 18
4.3 18
4.4 19
4.5 20
4.6 21
4.7 22
4.8 23
4.9 24
5.0 25
Now, for a computer algorithm, the couple of extra steps by using binary search doesn't really matter, but I find that when doing math by hand, it can be a great benefit to avail oneself of intuition, to be able to skip a few steps - especially when working in this manner where you "check your guess" at every step - so you won't risk a wrong answer, the only risk is wasted work.
This is indeed a bit different when approximating a more complicated function, eg one that doesn't monotonically increase/decrease.
I'd tackle this in my head by realizing the answer is close to 4, and the derivative of sqrt near 16 is about 1/(2 sqrt(16)) = 1/8 which is not far from 1/10. So always round up.
So 4^2 = 16 is under by 1, add 0.1. 4.1^2 = 16.81 is off by around .2, add 0.02. 4.12^2 = 16.9744 so add .003. You're basically adding a digit at a time without needing division.
I like doing this kind of estimation via binary logs expressed in base 12.
17 is a bit over 5·5·2/3, which is a bit under 2^(1.4 + 1.4 + 1 – 1.7) = 2^4.1 [base 12], now to take the square root we get 2^2.06 ~ 4·35/34 [base 10], but we want something a bit higher, so for a round number to cancel the 4 we can guess 4·33/32 = 33/8 [base 10].
Base 12 is more efficient for arithmetic, but I never really mastered it. And converting back and forth seems to me to be more trouble than it is worth.
It’s only the binary logs that need to be base 12. This is the approximations inherent in the 12-step-per-octave equal-tempered Western music scale. Memorizing just two facts gets you a long way:
3 ~ 2^(19/12) -> lg 3 ~ 1;7 or to be more precise 1;703
5 ~ 2^(7/3) = 2^(28/12) -> lg 5 ~ 2;4 or to be more precise 2;3a4
This makes 2^0;7 just about exactly a “perfect fifth” 3/2 (off by about .1%), and 2^0;4 almost a “major third” 5/4 (off by .8%).
If you step up a scale by 2^(1/12) or in log scale 0;1 increments, you can find close fractional approximations to most of the steps. Then I happen to also know that 0;06 is ~lg 35/34, but that one obviously isn’t nearly as important or easy to work with.
Mind that there is no need for estimates and backtracking when doing it in binary!
Since the term q for solving the remainder r for any step as in the binomial r = x2 - 4p2 - q(4p + q) is either 1 or 0 in a base-2 system, evaluating the "fit" becomes merely a matter of testing a boolean value. (Therefor we can go for a straight-forward algorithm. No need for interpolations, here.)
There are many methods for calculating square roots [1]. The article explain the Digit-by-Digit with Decimal (base 10) method, I believe, and explains it quite well.
The babylonian method is, imo, easier to remember and perform than the "lost art" presented here:
Start with a ball park estimate of the root of x, then take an average of (estimate + x / the estimate). That's your new estimate. Rinse and repeat until convergence to an acceptable degree.
The biggest drawback if doing this by hand is the division problem can be a pain.
I see the attraction and "purity" of the proposed lost art.
I had always thought of this as Newton's Method too, but that's because I was simply misremembering the fullness of Newton's Method [1]. I'm grateful for the education.
It is equivalent when applied to the function f(a) = a^(1/2) - x. Also, one needs to divide by 2 since if a is the square root of x, then a+x/a = a + a = 2a.
n-th roots are not quite as nice, but still work fairly simply:
((n-1) a + x/a^(n-1) )/n
You can see that the fixed point (a = nth root of x) works out as it should.
Division is much harder than multiplication. Even for computers. It's easier to just square your estimate and see how close it is. Then increase or decrease it proportional to how much closer you are getting.
I did. (as a millenial)
I didn't even study a subject connected to mathematics. I came across it and thought it was neat, so i learned it... but forgot it.
I graduated college a year ago and I'm not sure if I've ever in my life been asked to manually compute a square root (except for a perfect square integer).
Same here. And I distinctly remember asking a math teacher in middle school if a number was a perfect square and we manually ended up checking and incrementing numbers until we decided that the number was not. It makes me think that this was possibly not such a common task to assign in school?
Depends on your course load. My EE courses forced you to do this (and then forced you to do it in hardware... on a crappy chip that I swear lacked an overflow bit, but my memory is fuzzy).
I never formally learned any algorithm for performing square roots in either high school or college. In the few cases that I've needed one, I've simply binary searched out the answer to the required precision, and called it a day.
If you perform the algorithm described in the article in base 2 rather than base 10, you'll get binary search. Instead of (10 A) do (2 A), etc. Each step is easier (no guessing and checking), but there are more steps because each step gives you one bit rather than one decimal digit.
It's awesome to see how binary representation of numbers often leads to a convergence between operations and algorithms conceived in terms of arithmetic and those conceived in terms of logic.
Nope. In fact, I distinctly remember one of my earlier frustrations of high school was asking the teacher how to do square roots. She said "with a calculator." "Yeah yeah, but how to do you do them by hand?" "You don't, you just need to use the calculator."
I've never heard of anyone below the age of 30 learning in school how to do them manually.
Definitely not (and I went to college when I was one of the few students who arrived with his own computer). Our chemistry teacher spent one class showing us how to use Newton's approximation, and most students found it a complete waste of time, given that everybody had a pocket calculator of some kind.
(Of course, I learned how to calculate square roots on paper before I went to college, but only because I asked my father to show me how.)
Been a long time since I saw this. Reminds of School math. Nowadays sqrt is just a calculator button press away and so I have all but forgotten how to do this. This refreshed my memory.
I cant help but chuckle at the exact definition being thrown at me. I guess that by definition this is a lost art. I still think it's a bit over the top though.
I hear what your saying, taken individually you'd think a "lost art" would literally be an art no one remembers how to do. But like a lot of compound words and phrases in English, its actual meaning as used is different. In my experience, its pretty much always used in the sense of the article.
(SNL had a whole bit on this back in the 90's: "a chickpea is neither a chick nor a pea, discuss")
My mother taught it me when I was 12. Normally it is presented like a division. At 17, I have coded it in turbo pascal with arrays of digits. If I remember well, I had found a way to apply the same method for cubic roots.
Interesting. I was always taught to simply reduce the square roots as much as possible (ie sqrt(8) = 2*sqrt(2)) and leave the square roots, as it's often more precise than an arbitrary number of decimals.
I was wondering that too, the best I could come up with is that the unused part of the rectangle represents the remainder we haven't "pulled down" yet, so in the first iteration, 0.17
I don't think its important to the calculation though
I believe it's just a visual aid that can help you understand how each digit is converging on the true square root. If you're not one for visual analogies, then it probably just feels like a distraction.
This is part of an excursus trying to explain, how basic math was implemented on the DEC PDP-1, namely in Spacewar!, the first digital video game (1961/62). The excursus starts at http://www.masswerk.at/spacewar/inside/insidespacewar-pt6-gr... (there's a tab on the bottom right for an instruction list of the PDP-1, mind that the PDP-1 uses 1's-complement for negative numbers).
However, the correct Portuguese for "cube roots" is "raízes cúbicas", not "raios cubicos"(—edited with thanks to JetSpiegel for the correction!). I've thought that Feynman may have been better at speaking Portuguese than at spelling it, or that most of Surely You're Joking may have been transcribed from tapes by Ralph Leighton, who probably didn't speak Portuguese.)
Edit: Also, I was partly inspired to learn Portuguese by Richard Feynman. I didn't imagine that that would lead to complaining about his spelling. :-)
It's actually "raízes cúbicas", "raiz" is female.
I'm impressed to see "multiplicação" correctly written in an English language page, usually everyone ignores tildes and ç, but they are important.
Oh gosh, thanks for the correction. I searched for what I thought it was and found lots of native speakers using the form that matched my intuition—but that didn't make it correct. :-)
fwiw, I learned to compute square roots in school in the 80s (I think it was the estimation method, which I was extremely bad at).
Calculators of any kind were forbidden at school, which sucked, if you had one of those cool Casio watch calculators. Shorts were also forbidden, because suffering is good for you, apparently.
I've never had to do it since, of course. Though I do now wear shorts on occasion.
In my college professor offered passing grade immediately to someone who could manually calculate root.Nobody knew,although everyone learned it in high school.It's amazing how much people today depend on computer.In some sense all that automation makes us stupid.
This seems like a really hard way to calculate square roots. Why not just use bracketing?
1. Pick a number HI whose square is obviously higher than N.
2. Pick a number LO whose square is obviously lower than N.
3. Choose a number MED which is roughly (HI+LO)/2.
4. If MED * MED > N, replace HI with MED, else replace LO with MED.
5. Go to 3.
6. MED converges to your answer.
Doesn't converge quite as fast maybe, but a million times easier to grok. I got to where the author got, ~87.8, in 8 iterations even with terrible initial HI and LO guesses (100 and 50 respectively).
> Doesn't converge quite as fast maybe, but a million times easier to grok.
What didn't you understand about manually calculating square roots? Because
your method requires tons of troublesome multiplication of numbers that get
longer with each step.
I think faster convergence is the answer. Also, I like the geometric argument in the post. But you're right, bracketing is pretty obvious, and it's the way I approximate square roots in my head.
What's lost about it? When I first came to the US aged 12 I was confronted with an entrance exam for the school we had chosen.
The math part had this weird American division symbol I had never seen before, and the closest thing I had seen was square root. Which I found a bit ambitious, but I went ahead and did the square roots.
They accepted me despite the fact that I couldn't do division, but put me in the "remedial math" class. Got out of it when I did the in-class "calculator exercises" (weird concept, that) in my head, faster than anyone with the calculator.
just to add to the conversation ... once one learns algebra and expresses a number as polynomial of 10, one can just derive the usual manual algorithm for any integer root ... though it gets tedious very quickly with hisgher roots ... in addition to methods using Taylor expansion and such ... maybe this is a reason why there is no need to teach it ... apart from the practical reason of a calculator can do it much quicker ...
I actually studied how to resolve square roots by hand in school. It looked like solving a division with some different rules. I honestly don't remember the process but can definitely get my math homeworks and find them (yes I still have them!). I'm 28 years old, so it's not that far come on :P
71 comments
[ 0.20 ms ] story [ 134 ms ] threadEstimate sqrt(17):
Clearly it has to be between 4 and 5.
Try 4.5. Result: 20.25 Try 4.2. Result: 17.64 Try 4.1. Result: 16.81 Try 4.15. Result: 17.01. Probably good enough for most practical purposes.
In this case the value is sanity checking a calculator / program.
Were any memory tricks involved (e.g. pegs, palaces) or did he just go through a table of square roots every morning?
His justification for starting was trying to keep track of the order of magnitude of everything he calculated to catch fat finger mistakes. And a sanity check. However, you need a few digits on the front of a number before you can really safely keep track of exponents that way.
There are 12 numbers from 4.0 through 5.0 inclusive - in steps of 0.1, and there are 10 integer numbers from 16 through 25 inclusive - clearly there's an uneven, but still somewhat smooth mapping from one through the other via the square function (or root function, for that matter). It's easy to see (note that python rounds down up to .5 inclusive):
Now, for a computer algorithm, the couple of extra steps by using binary search doesn't really matter, but I find that when doing math by hand, it can be a great benefit to avail oneself of intuition, to be able to skip a few steps - especially when working in this manner where you "check your guess" at every step - so you won't risk a wrong answer, the only risk is wasted work.This is indeed a bit different when approximating a more complicated function, eg one that doesn't monotonically increase/decrease.
So 4^2 = 16 is under by 1, add 0.1. 4.1^2 = 16.81 is off by around .2, add 0.02. 4.12^2 = 16.9744 so add .003. You're basically adding a digit at a time without needing division.
17 is a bit over 5·5·2/3, which is a bit under 2^(1.4 + 1.4 + 1 – 1.7) = 2^4.1 [base 12], now to take the square root we get 2^2.06 ~ 4·35/34 [base 10], but we want something a bit higher, so for a round number to cancel the 4 we can guess 4·33/32 = 33/8 [base 10].
3 ~ 2^(19/12) -> lg 3 ~ 1;7 or to be more precise 1;703
5 ~ 2^(7/3) = 2^(28/12) -> lg 5 ~ 2;4 or to be more precise 2;3a4
This makes 2^0;7 just about exactly a “perfect fifth” 3/2 (off by about .1%), and 2^0;4 almost a “major third” 5/4 (off by .8%).
If you step up a scale by 2^(1/12) or in log scale 0;1 increments, you can find close fractional approximations to most of the steps. Then I happen to also know that 0;06 is ~lg 35/34, but that one obviously isn’t nearly as important or easy to work with.
Since the term q for solving the remainder r for any step as in the binomial r = x2 - 4p2 - q(4p + q) is either 1 or 0 in a base-2 system, evaluating the "fit" becomes merely a matter of testing a boolean value. (Therefor we can go for a straight-forward algorithm. No need for interpolations, here.)
[1] [ https://en.wikipedia.org/wiki/Methods_of_computing_square_ro... ]
Start with a ball park estimate of the root of x, then take an average of (estimate + x / the estimate). That's your new estimate. Rinse and repeat until convergence to an acceptable degree.
The biggest drawback if doing this by hand is the division problem can be a pain.
I see the attraction and "purity" of the proposed lost art.
https://en.wikipedia.org/wiki/Newton%27s_method
n-th roots are not quite as nice, but still work fairly simply: ((n-1) a + x/a^(n-1) )/n
You can see that the fixed point (a = nth root of x) works out as it should.
https://en.wikipedia.org/wiki/Binary_search_algorithm
rather than representing numbers or performing arithmetic in base 2.
sqrt(7720.17)
first guess 50:
2500
Go up
second guess 100:
10000
too high go down
third guess 75
5625
too low go up
fourth guess 86 (for ease of calculation)
6400 480 + 480 36
7396
too low go up: 93
8529
too high go down: 90
8100
too high go down: 88
7744
Etc.
It's not a great method, but it's what first came to mind. I do it sometimes in my head for a quick estimate.
7720 in binary is 1111000101000. This is 13 bits. Square root is at most half as long, so first guess is 10000000 in binary, or 128.
Square that, realize that it's too high, set the highest bit to 0 and next bit to 1.
Square 1000000 binary or 64, realize that it's too low. Keep the top bit, raise the next bit.
Square 1100000 binary or 96, too high, drop that bit back to zero, raise the next bit.
Square 1010000 binary or 80, too low, raise the next bit.
Square 1011000 binary or 88, too high, drop this bit and raise the next one.
Square 1010100 binary or 84, too low, raise the next bit.
Square 1010110 binary or 86, too low, raise the next bit.
Got 1010111 binary or 87.
I've never heard of anyone below the age of 30 learning in school how to do them manually.
nyah!
(Of course, I learned how to calculate square roots on paper before I went to college, but only because I asked my father to show me how.)
"https://www.merriam-webster.com/dictionary/lost%20art"
(SNL had a whole bit on this back in the 90's: "a chickpea is neither a chick nor a pea, discuss")
This describes how to find the side length of the square, who's area is smaller than the rectangle.
I don't think its important to the calculation though
This is part of an excursus trying to explain, how basic math was implemented on the DEC PDP-1, namely in Spacewar!, the first digital video game (1961/62). The excursus starts at http://www.masswerk.at/spacewar/inside/insidespacewar-pt6-gr... (there's a tab on the bottom right for an instruction list of the PDP-1, mind that the PDP-1 uses 1's-complement for negative numbers).
http://www.ee.ryerson.ca/~elf/abacus/feynman.html
However, the correct Portuguese for "cube roots" is "raízes cúbicas", not "raios cubicos"(—edited with thanks to JetSpiegel for the correction!). I've thought that Feynman may have been better at speaking Portuguese than at spelling it, or that most of Surely You're Joking may have been transcribed from tapes by Ralph Leighton, who probably didn't speak Portuguese.)
Edit: Also, I was partly inspired to learn Portuguese by Richard Feynman. I didn't imagine that that would lead to complaining about his spelling. :-)
That's because in Dutch we just call it 'root' (wortel).
I really wish teachers used more graphic forms in math because it helps to understand what kind of problems it can solve.
I am asking because in France we have the official term racine carrée (square root), abbreviated to racine (root) when the "square" is implied.
Calculators of any kind were forbidden at school, which sucked, if you had one of those cool Casio watch calculators. Shorts were also forbidden, because suffering is good for you, apparently.
I've never had to do it since, of course. Though I do now wear shorts on occasion.
FWIW, I did too in the 90s/00s, though I confess I don't remember the method now. I think it was Newton-Rhaphson.
What didn't you understand about manually calculating square roots? Because your method requires tons of troublesome multiplication of numbers that get longer with each step.
Why would you be both insulting and wrong in the same post?
Or did you think that multiplication somehow isn't manual?
Next time work on phrasing your comment a bit better. It makes the world a better place.
The math part had this weird American division symbol I had never seen before, and the closest thing I had seen was square root. Which I found a bit ambitious, but I went ahead and did the square roots.
They accepted me despite the fact that I couldn't do division, but put me in the "remedial math" class. Got out of it when I did the in-class "calculator exercises" (weird concept, that) in my head, faster than anyone with the calculator.