3-4 short lines, Integer Newton, Every Language


  • 125

    Quite a few people used Newton already, but I didn't see someone make it this short. Same solution in every language. Explanation under the solutions.

    C++ and C

        long r = x;
        while (r*r > x)
            r = (r + x/r) / 2;
        return r;
    

    Python

        r = x
        while r*r > x:
            r = (r + x/r) / 2
        return r
    

    Ruby

        r = x
        r = (r + x/r) / 2 while r*r > x
        r
    

    Java and C#

        long r = x;
        while (r*r > x)
            r = (r + x/r) / 2;
        return (int) r;
    

    JavaScript

        r = x;
        while (r*r > x)
            r = ((r + x/r) / 2) | 0;
        return r;
    

    Explanation

    Apparently, using only integer division for the Newton method works. And I guessed that if I start at x, the root candidate will decrease monotonically and never get too small.

    The above solutions all got accepted, and in C++ I also verified it locally on my PC for all possible inputs (0 to 2147483647):

    #include <iostream>
    #include <climits>
    using namespace std;
    
    int mySqrt(int x) {
        long long r = x;
        while (r*r > x)
            r = (r + x/r) / 2;
        return r;
    }
    
    int main() {
        for (long long x=0; x<=INT_MAX; ++x) {
            long long r = mySqrt(x);
            if (r<0 || r*r > x || (r+1)*(r+1) <= x)
                cout << "false: " << x << " " << r << endl;
            if (x % 10000000 == 0)
                cout << x << endl;
        }
        cout << "all checked" << endl;
    }

  • 4
    F

    only Stefan!!! (Please provide more information - at least 30 characters)


  • 0
    L

    You are gift of god Stefan


  • 0
    W

    what if x = 1<< 31? x*x will overflow


  • 1

    @winstonchi x is an int, which can't be 1<<31 (unless you mean to enter that expression, i.e., get a negative number... but then that's a different issue). Also, nowhere do I use x*x.


  • 0
    B

    So elegant! Thanks! I did a small tweak to use the condition 0'<'r<=x/2, but the cases 0 and 1 need to be picked up first..... Don't know if this can make the code faster......

    int mySqrt(int x) {
        if(x<2) return x;
    
        long r = x/2;  
        while (r*r > x)
              r = (r + x/r) / 2;
        return r;
    }

  • 1
    Q

    Better set starting point as r = (x+1) / 2, since all nonnegative integers x satisfies sqrt(x) <= (x+1) / 2. actually got (x+1)/2 if manually do the first iteration starting with r = x.


  • 0
    Q
    This post is deleted!

  • 0

    @qeatzy I know, but I prefer the simpler code without that duplication. And like you said, I also get there immediately anyway.


  • 0
    A

    Why use long to represent r? Am I missing something? Thanks.


  • 0

    What is the time complexity of newton method? log(n)?


  • 2

    @yu6 I'm not sure. I did a little experiment, testing 2, 4, 16, 256, 65536, etc (always squaring). The number of iterations almost doubled from one case to the next and the runtime almost increased by factor 8. So looks like it's around O(log(n)3), where one log(n) comes from the number of iterations and log(n)2 comes from the multiplications and divisions.


  • 0
    Z

    Why wouldn't the "root candidate" get too small?


  • 0

    What if the question is to get a float result instead of int?


  • 0
    Y

    @StefanPochmann You can simply prove it: while r * r > x, => x/r < r, so (r + x / r ) / 2 - r = (x / r - r) / 2 < 0; thus when r * r > x holds, the root candidate will always decrease monotonically.


  • 0

    @ye20 I don't find that convincing. We're dealing with integers and integer operations here, and I don't see you caring about rounding.


  • 0

    Newton's method fails to converge to root for bad start point. How to choose an appropriate start point and make sure the algorithm works?


  • 0

    @toinfinity said in 3-4 short lines, Integer Newton, Every Language:

    Newton's method fails to converge to root for bad start point.

    For example?


  • 0

    @StefanPochmann Newton's method does need an appropriate start point (https://en.wikipedia.org/wiki/Newton's_method#Bad_starting_points) because it converges only in some ϵ-neighbourhood of a root. I don't find counter example for this problem, maybe all start point of x is good, but we should prove it before we use it.


  • 2

    @toinfinity I'd say the verification at the end of my post where I check all possible inputs is proof, no?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.