O(1) time c++ solution inspired by Q_rsqrt


  • 16
    D
    class Solution {
    public:
        bool isPerfectSquare(int num) {
            if (num < 0) return false;
            int root = floorSqrt(num);
            return root * root == num;
        }
    
        int32_t floorSqrt(int32_t x) {
            double y=x; int64_t i=0x5fe6eb50c7b537a9;
            y = *(double*)&(i = i-(*(int64_t*)&y)/2);
            y = y * (3 - x * y * y) * 0.5;
            y = y * (3 - x * y * y) * 0.5;
            i = x * y + 1; return i - (i * i > x);
        }
    };

  • 0

    Very nice. I'm not really familiar with it and wasn't sure about accuracy, but I tested this with all inputs from 1 to INT_MAX and it got all of them correct.


  • 0
    D

    Yes, it just works. The idea came from Fast Inverse Square Root.


  • 1

    how did you find the value 'i' ?


  • 4
    4

    I am very interested to see how you will come to 0x5fe6eb50c7b537a9 during an interview.


  • 3
    4

    From https://en.wikipedia.org/wiki/Fast_inverse_square_root

    The following code is the fast inverse square root implementation from Quake III Arena, stripped of C preprocessor directives, but including the exact original comment text:

     ...
     i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
     ...

  • 0
    U

    @dploop

    Thanks above:

    The following code is the fast inverse square root implementation from Quake III Arena, stripped of C preprocessor directives, but including the exact original comment text:[5]

    float Q_rsqrt( float number )
    {
    long i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;                       // evil floating point bit level hacking
    i  = 0x5f3759df - ( i >> 1 );               // what the fuck? 
    y  = * ( float * ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
    

    // y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

    return y;
    

    }


Log in to reply
 

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