Fastest way to get the integer part of sqrt(n)?

by

I would try the Fast Inverse Square Root trick.

It’s a way to get a very good approximation of 1/sqrt(n) without any branch, based on some bit-twiddling so not portable (notably between 32-bits and 64-bits platforms).

Once you get it, you just need to inverse the result, and takes the integer part.

There might be faster tricks, of course, since this one is a bit of a round about.

EDIT: let’s do it!

First a little helper:

// benchmark.h
#include <sys/time.h>

template <typename Func>
double benchmark(Func f, size_t iterations)
{
  f();

  timeval a, b;
  gettimeofday(&a, 0);
  for (; iterations --> 0;)
  {
    f();
  }
  gettimeofday(&b, 0);
  return (b.tv_sec * (unsigned int)1e6 + b.tv_usec) -
         (a.tv_sec * (unsigned int)1e6 + a.tv_usec);
}

Then the main body:

#include <iostream>

#include <cmath>

#include "benchmark.h"

class Sqrt
{
public:
  Sqrt(int n): _number(n) {}

  int operator()() const
  {
    double d = _number;
    return static_cast<int>(std::sqrt(d) + 0.5);
  }

private:
  int _number;
};

// http://www.codecodex.com/wiki/Calculate_an_integer_square_root
class IntSqrt
{
public:
  IntSqrt(int n): _number(n) {}

  int operator()() const 
  {
    int remainder = _number;
    if (remainder < 0) { return 0; }

    int place = 1 <<(sizeof(int)*8 -2);

    while (place > remainder) { place /= 4; }

    int root = 0;
    while (place)
    {
      if (remainder >= root + place)
      {
        remainder -= root + place;
        root += place*2;
      }
      root /= 2;
      place /= 4;
    }
    return root;
  }

private:
  int _number;
};

// http://en.wikipedia.org/wiki/Fast_inverse_square_root
class FastSqrt
{
public:
  FastSqrt(int n): _number(n) {}

  int operator()() const
  {
    float number = _number;

    float x2 = number * 0.5F;
    float y = number;
    long i = *(long*)&y;
    //i = (long)0x5fe6ec85e7de30da - (i >> 1);
    i = 0x5f3759df - (i >> 1);
    y = *(float*)&i;

    y = y * (1.5F - (x2*y*y));
    y = y * (1.5F - (x2*y*y)); // let's be precise

    return static_cast<int>(1/y + 0.5f);
  }

private:
  int _number;
};


int main(int argc, char* argv[])
{
  if (argc != 3) {
    std::cerr << "Usage: %prog integer iterations\n";
    return 1;
  }

  int n = atoi(argv[1]);
  int it = atoi(argv[2]);

  assert(Sqrt(n)() == IntSqrt(n)() &&
          Sqrt(n)() == FastSqrt(n)() && "Different Roots!");
  std::cout << "sqrt(" << n << ") = " << Sqrt(n)() << "\n";

  double time = benchmark(Sqrt(n), it);
  double intTime = benchmark(IntSqrt(n), it);
  double fastTime = benchmark(FastSqrt(n), it);

  std::cout << "Number iterations: " << it << "\n"
               "Sqrt computation : " << time << "\n"
               "Int computation  : " << intTime << "\n"
               "Fast computation : " << fastTime << "\n";

  return 0;
}

And the results:

sqrt(82) = 9
Number iterations: 4096
Sqrt computation : 56
Int computation  : 217
Fast computation : 119

// Note had to tweak the program here as Int here returns -1 :/
sqrt(2147483647) = 46341 // real answer sqrt(2 147 483 647) = 46 340.95
Number iterations: 4096
Sqrt computation : 57
Int computation  : 313
Fast computation : 119

Where as expected the Fast computation performs much better than the Int computation.

Oh, and by the way, sqrt is faster 🙂

More Related Contents:

  1. What is the efficient way to count set bits at a position or lower?
  2. Fastest way to determine if an integer is between two integers (inclusive) with known sets of values
  3. Creating all possible k combinations of n items in C++
  4. Finding all the subsets of a set
  5. Fast ceiling of an integer division in C / C++
  6. Most efficient/elegant way to clip a number?
  7. Generating m distinct random numbers in the range [0..n-1]
  8. Fastest algorithm for primality test [closed]
  9. Special simple random number generator
  10. sine wave that slowly ramps up frequency from f1 to f2 for a given time
  11. Efficiently getting all divisors of a given number
  12. Inverting a 4×4 matrix
  13. Is it possible to map string to int faster than using hashmap?
  14. Finding square root without using sqrt function?
  15. Absolute Distinct Numbers
  16. C++ throwing exception in recursive algorithm
  17. How to use Quick Sort to sort an array of strings
  18. mixing cout and printf for faster output
  19. What is the best way to evaluate mathematical expressions in C++?
  20. What’s faster, iterating an STL vector with vector::iterator or with at()?
  21. Why does GCC generate 15-20% faster code if I optimize for size instead of speed?
  22. How can I sort a std::map first by value, then by key?
  23. Fast Cross-Platform C/C++ Image Processing Libraries
  24. Why is std::unordered_map slow, and can I use it more effectively to alleviate that?
  25. Similar String algorithm
  26. How do I implement a Bézier curve in C++?
  27. Better shading on BW display while rendering filled surfaces
  28. Performance of qsort vs std::sort?
  29. Does auto deduce the type at compile time or runtime in C++ 11?
  30. Calculate mean and standard deviation from a vector of samples in C++ using Boost

Leave a Comment