5 ms·

Nice! But even Newton's method works fine on a sheet of paper!

Turing_Machine 9y ago
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.
- Retric 9y ago
  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.
  - tpeo 9y ago
    Why would he do that, though? I do think it's neat, but I think most people would just memorize an algorithm instead. Were any memory tricks involved (e.g. pegs, palaces) or did he just go through a table of square roots every morning?
    - Retric 9y ago
      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.
      - jacobolus 9y ago
        Memorizing a log table is a heck of a lot better bang for the buck than memorizing square roots, cube roots, etc.
- e12e 9y ago
  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.
- btilly 9y ago
  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.
  - jacobolus 9y ago
    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].
    - btilly 9y ago
      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.
      - jacobolus 9y ago
        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.
- masswerk 9y ago
  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.)

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.

Retric 9y ago
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.
- tpeo 9y ago
  Why would he do that, though? I do think it's neat, but I think most people would just memorize an algorithm instead. Were any memory tricks involved (e.g. pegs, palaces) or did he just go through a table of square roots every morning?
  - Retric 9y ago
    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.
    - jacobolus 9y ago
      Memorizing a log table is a heck of a lot better bang for the buck than memorizing square roots, cube roots, etc.
e12e 9y ago
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.
btilly 9y ago
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.
- jacobolus 9y ago
  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].
  - btilly 9y ago
    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.
    - jacobolus 9y ago
      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.
masswerk 9y ago
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.)