En hızlı Karekök tamsayı kısmını(n) şansı olur mu?

SORU

8 ŞUBAT 2011, Salı

En hızlı Karekök tamsayı kısmını(n) şansı olur mu?

Eğer n mükemmel bir kare ise, bildiğimiz gibi, daha sonra sqrt(n) bir tamsayı olmaz. Sadece tam sayı kısmını istiyorum beri, sqrt(n) arama süresi kesirli kısmı da hesaplamak için alır gibi bu kadar hızlı olmaz. ben böyle düşünüyorum.

Benim sorum ise şu :

Sadece tam sayı kısmını alabilir miyizKarekök(n)Karekök gerçek değeri(n) hesap etmeden? Algoritma sqrt(n) (<math.h> <cmath> tanımlanmış) daha hızlı olmalıdır?

Mümkünse, asm blok içinde kod da yazabilirsiniz.

CEVAP

8 ŞUBAT 2011, Salı

Fast Inverse Square Root hile denemek istiyorum.

Bir şekilde herhangi bir şube olmadan 1/sqrt(n) çok iyi bir yaklaşım elde etmek için, bit öldürmek değil, taşınabilir (32-bit ve 64-bit platformlar arasında özellikle) dayanıyor.

Bunu aldıktan sonra, sadece ters sonucu, tam sayı kısmını alır.

Bu konuda bir yuvarlak bir parça olduğundan daha hızlı hileler, elbette olabilir.

EDİThadi yap şunu!

İlk bir küçük Yardımcısı:

// 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);
}

Ana gövde sonra:

#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;
}

Ve sonuçları:

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

Beklendiği gibi buradaHızlıhesaplama çok daha iyi bir performans sergiliyorİnthesaplama.

Oh, ve bu arada, sqrt daha hızlı :)

Bunu Paylaş: