1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge: can you take the sqrt (n) using only one operation

  1. Apr 22, 2012 #1
    The best known algorithm ('Babylonian') to take the square root of a number requires 3 operations, less than Newton's. I suppose it's also the fastest. Is it so?
    Do you know a simpler or faster one?

    Can you find a method that requires only 1 operation?
     
    Last edited: Apr 22, 2012
  2. jcsd
  3. Apr 22, 2012 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yes: apply the square root operation.
     
  4. Apr 23, 2012 #3
    square root is the problem to be solved, can it also be the solution?


    P.S.: I apologize if I have been ambiguous: *(one of the 4 operations. +, -, x, : ). The algorithm should contain 1 op, but it can be iterated a few times, of course!
    to simplify discussion and use a pocket calculator, let's choose (n = x²) n with less than 21 digits:
    210.3456789², 987654.3012²... 597482²....etc
     
    Last edited: Apr 23, 2012
  5. Apr 23, 2012 #4
    Yes; if you already know the solution to be, say, r, then you can find said solution by just one division, n/r.
     
    Last edited: Apr 23, 2012
  6. Apr 23, 2012 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member



    So, we get to use "limit" as an operation too? What about "<" as well?


    I'm not just being snarky here -- it is provably impossible to obtain [itex]\sqrt{2}[/itex] using just those four operations along with any integers you want, so "limit" or some other related concept is rather important.

    Many algorithms for extracting roots rely on being able to tell whether one number is bigger than another, and so "<" is important.
     
  7. Apr 24, 2012 #6
    We are only trying to solve a practical problem: we are trying to apply our contemporary wisdom to see we if can do any better than the Babylonian method, if that is really the best algorithm. (I'll tackle this in a separate post). Our solution should be more convenient even using pencil and paper. Do you think it is possible?

    If n is not a square number ([itex]\sqrt{2}[/itex]...[itex]\sqrt{125348}[/itex]... etc), we have to stop sometime, somewhere, maybe after 1010 digits, but we must stop. Hope you agree. If a simple, convenient method requires '>','<' ,... or other, it is interesting to see it.
    I was only responding to your (jocular?) post #2, excluding the obvious sqrt, log, ln, etc. I hope that is clear.
    here: they decided to stop after 6 digits: 354.045, and it took them 5 rounds (iterations) = 15 (5*3 [+, :, :]) ops. to reach that result. Can you do any better?
    I suggested to stop at 10 places (9digits plus the point) so that non specialists (without a computer program), like myself, can follow or take part in the discussion with just a pocket calculator.

    If this is not clear I'll exemplify: my calculator says [itex]\sqrt{125348}[/itex] = 354.0451949 , the number is obviously truncated and I cannot know if it is rounded up or down and if it is correct to stop at 354.0451948.
    That is why I suggested to start with a number with finite number of decimals ( like [itex]\sqrt{125347.862}[/itex]) to know that exactly 354.045 is our goal.



    P.S. Moreover, if you start with a finite n you can find its root even when many digits are missing: [itex]\sqrt{623,470.122 xxx xxx x49}[/itex], we can find the root: x = 789.601243
     
    Last edited: Apr 24, 2012
  8. Apr 24, 2012 #7


    Your whole post is pretty confusing, making your nick paradoxical. You talked of calculating the square root of a number

    using "only one operation"...Did you mean using one operation several times, did you mean to use one unique

    operation once? It should be obvious that either possibility has a negative answer: no, it is not possible IN GENERAL to do that

    with only one operation, whatever "one operation" means to you.

    Now, it is possible to evaluate the square root of any number to any degree of wanted precision by elementary operations,

    namely +, -, *, /, and I don't know if this is the babylonian method.

    DonAntonio
     
  9. Apr 24, 2012 #8
    If you do not know it, probably that is the reason why you could not understand my post. I gave you a link, scroll up a little:
    In the OP (post #1), I noted that Babylonian algorithm requires 3 operations for each iteration, as surely by now you have found out. In the title, if you're referring to that, I could not possibly explain everything.

    I'm asking if you can find a simpler one (algorithm), one which requires less then 3 ops at each iteration. One op., of course, is the limit.
    EDIT: Such an algorithm is likely to be less powerful, to converge slower, but it would require less then 15 ops. (in the #Example quoted), I suppose anyone can do better than wiki . I'm sure you are able at least to make a first guess more accurate than x0= 600

    If you run the algorithm only once then you take directly sqrt(n), and you reach your goal with one operation.( 'ne plus ultra' !).


    Besides the OP, you probably missed also post #3:
    I hope it is clear, if it was not.


    P.S. A nick is a nick, what's in a name? that which we call a rose....
     
    Last edited: Apr 24, 2012
  10. Apr 24, 2012 #9


    I read only what you wrote in your first post, which is exactly the following:


    "The best known algorithm ('Babylonian') to take the square root of a number requires 3 operations, less than Newton's. I suppose it's also

    the fastest. Is it so? Do you know a simpler or faster one?

    Can you find a method that requires only 1 operation?"


    No iterations, no links, nothing. That's what confused me and, judging by the first responses at least, apparently also others.

    DonAntonio
     
  11. Apr 24, 2012 #10

    jgens

    User Avatar
    Gold Member

    No such algorithm exists. Fix the number 2 for example and try to approximate the √2 using only one operation from {+,-,×,/}. If we choose either + or -, then we can either add or subtract 2 (or multiples of 2) from itself repeatedly, so the result will be 2n where n an integer. If we choose either × or /, then we can either multiply or divide 2 (or powers of two) from itself repeatedly, so the result will be 2n where n an integer. But neither 2n nor 2n can approximate √2 to more than say one or two decimal places.
     
  12. Apr 24, 2012 #11
    Thanks jgens, that gives me a chance to compare methods and check if it is my terminology that generates misunderstanding:

    here is: B method, is this procedure an algorithm? (If it cannod described as an algorithm, I stand corrected and I apologize).
    This method requires 3 operations:

    (x + a : x) : 2
    ...1....2....3
    As wiki shows, the formula must be iterated 5 times and that adds up to 15 ops. (to find: sqrt{125348} = 354.045, 6-digit accuracy)

    There is another method : N[ewton]. It is equivalent to B, but (because of the way it is usually formulated), it requires 4 operations:
    (x * x + a) : 2 * x
    .. 1...2.....3....4
    (You can find out how many ops. are necessary to solve the problem, if N it is better than B)

    Now, why should all the objections apply only to a hypothetical method A that requires 2 operations?.
    If I am missing something and your objections are valid only for my hypothesis, please change n to 125347.862025 or any other n which you deem suitable, and let's change the title:
    Can you find the square root of 125347.862025 (x= 354.045) with less than 15 operations?

    Thanks for your help, jgens, I hope you'll give us the first concrete contribution: if you were in Alexandria or Miletus, or in the Middle Ages with quill and parchment :wink:, how would you find 354.045?
     
    Last edited: Apr 24, 2012
  13. Apr 24, 2012 #12


    Using the system my dad taught me and which he learnt when he was a kid, either from my grandpa or at school:

    subdive the given number in groups of 2, from right to left, before and after the decimal point:

    12´53´47.86´20´25

    The above 2-groups will be the ones "going down" after each step is finished.

    Begin with 12 at left: take the number whose square is closeset to 12 but less than or equal to it. In this case

    it is 3 and we write down aside.

    Square it and substract it from 12: we get 3 below 12 and we draw down the next pair, 53, thus getting 353.

    Double 3, getting 6 (of course, this is just the double method in some disguise which makes, perhaps, easier to carry on by hand)

    Find a digit x such that [itex]6x\cdot x[/itex] is as close as possible to 353 but no more than it: this digit is 5 and we

    write down aside at the right of the 3, so 65*5 = 325, and substract this from 352, getting 28, and now draw down the next pair 47...etc.

    As you can see, we need two operations for each digit in the answer: doubling the already found number and then multiplying, except

    for the first digit which only required squaring it.

    So in this case we need 12 - 1 = 11 operations.

    DonAntonio


    Pd Hmmm...perhaps the substractions must be counted also and thus I have more operations. A pity...
     
  14. Apr 24, 2012 #13

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Division by 2 is barely an operation. General division is more expensive than general multiplication, and much more than plain addition.

    I checked GMP source code -- for small square roots ([itex]N \in [0, 2^{64})[/itex]), they use start off with a table lookup (for very small numbers), and then use Newton's algorithm to approximate y ~ 1/√N, which has the advantage of requiring no general divisions:
    [tex]y \leftarrow (1/2) (N y^3 + y)[/tex]
    with the very last iteration mixing in an extra multiplication by N so the result is an approximation x ~ √N
    [tex]x \leftarrow (1/2) (y (Ny)^2 + (Ny)) [/tex]

    GMP is actually computing an integer square root with remainder. Once it has the approximation, it computes x^2, and then increments it along until it gets the exact value of [itex]\lfloor \sqrt{N} \rfloor[/itex] (this doesn't require general multiplication: [itex] (x+1)^2 = x^2 + (2x+1)[/itex]), and then obtains the remainder.

    I haven't worked out the exact details of what it's doing for larger square roots.
     
  15. Apr 25, 2012 #14
    That is true, but may lead to subjective evaluation: plain addition (n+n) is equivalent to division by 2 (n:2) but, arguably, easier. If we want to be more accurate we may count the micro-operations

    Doesn't that apply to Newton's algorithm?
     
  16. Apr 25, 2012 #15
    The sum of the first "n" odd numbers is n^2, conversely, when the sum matches the desired number it's the square root. To find the square root of 2 simply add pairs of zeros for the desired accuracy. I guess this is 2 addition operations and one compare.
     
  17. Apr 26, 2012 #16
    Sorry, jgens, I did not reply directly to your post because I thought I was using the term 'algorithm' in a wrong way. You used Hurkyl's example, so I thought you were referring to his post, (which I still do not understand). Probably, as I said, I am missing something, could you tell me what?
    The fact that Newton's algorithm (which uses only 3 different ops. +, x, :) is actually used (post #13) proves, I suppose a fortiori, that one can find a method using those four operations.

    Yours is sound reasoning, but it is founded on the assumption that any method must use B's (or N) logics (the weighted mean).
    You can't prove, by that, that no such algorithm exists.
    I do not believe anyone can prove that such method is impossible. As you know, proving that something is impossible is a tough job.
    (Which operation is suitable, seems obvious.)
    As I said in a previous edit, any schoolboy can do better than wiki and find the right x0, and that would mean only 4 iterations (that is 12 ops.)
    What is the best 'first-guess' you can make?
     
    Last edited: Apr 26, 2012
  18. Apr 26, 2012 #17
    I don't know if this is flawed but a pretty good read to go on.

    Given x, now you are asked to find √x. You then will know x's integral sup and inf values, supposing they are a, b then you will have [itex]a ≤ \sqrt{x} ≤ b[/itex]. You can then use [itex]c=\frac{a+b}{2}[/itex] for each iteration to approximate the result
    How many operations are needed depending upon how many decimal values you want to find .
     
  19. Apr 26, 2012 #18
    Here is how one takes the square root of 2 by using addition, the square root of 2 00 is 14 sums of the odd numbers 1+3+5+7+9+11+13+15+17+19+21+23+25+ 27=196
    square root of 2 00 00 1s 141 sums, 2 00 00 00 is 1414 sums, etc. Not to say it's efficient, but it will work with only addition.
     
  20. Apr 26, 2012 #19
    Conversely, one may start with n (=x²) and use only subtraction, if 215² = 46225:

    46225 -1, -3, -5.....etc. It would take (x =) 215 operations, using this elementary logics.

    But subtraction can be more efficient, as it allows to improve the basic, simple algorithm. Remember you have the right, following B (or N) scheme, ( see wiki-link above), to find a suitable x0, performing micro-operations in your mind. If you guess the first digit and the number of digits (4'62'25 [itex]\rightarrow[/itex] 2 | 0 | 0|), you may start subtracting 4 | 00 | 00 | : 46225 - 40000 = 6225, and then continue subtracting (200 x 2 +1) 401,...etc:

    (n² - 40000 = ) 6225 - 401, - 403, - 405....etc. That would take only 15 + 1 operations

    But, of course, it takes a more ingenious method, a more sophisticated logic to outwit Newton and Babylonian logics, weighted mean is simple but powerful.
     
    Last edited: Apr 27, 2012
  21. Apr 27, 2012 #20
    I am no expert here at all, but is there a reason why no one posted this algorithm: http://www.homeschoolmath.net/teaching/sqr-algorithm-why-works.php on square roots?? It appears to use the least amount of operations that the OP was asking for. It was used back in the days of elementary school of the old days before the calculator was around.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook