Быстрый целочисленный sqrt с использованием Math.Sqrt

Если я вас правильно понимаю, вам нужен целочисленный квадратный корень:

sqrt(0) == 0
sqrt(1) == 1
sqrt(2) == 1
sqrt(3) == 1
sqrt(4) == 2
sqrt(5) == 2
...
sqrt(48) == 6
sqrt(49) == 7
... 

Если это ваша задача и вы хотите получить детерменистический результат на разных платформах, придерживайтесь целочисленных значений, например O(log(n)) алгоритм временной сложности

  public static int IntSqrt(int n) {
    ArgumentOutOfRangeException.ThrowIfNegative(n);

    var c = 0;
    var d = 1 << 30; 
                         
    while (d > n) 
      d >>= 2;
    
    for (int x = n; d != 0; d >>= 2) 
      if (x >= c + d) {      
        x -= c + d;        
        c = (c >> 1) + d;  
      }
      else 
        c >>= 1;           
 
    return c; 
  } 

Скрипка

Подробности см. https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29

У меня есть дополнительная идея к ответу Дмитрия. Math.Sqrt быстро, поскольку вас беспокоит, может ли этот метод дать надежные результаты, вы можете выполнить проверку при первом запуске игры, а время, которое это займет, можно игнорировать. Если проверка не удалась, используйте вместо этого медленный метод или сообщите, что аппаратное обеспечение не поддерживается.

Вот метод проверки:

for (long expect = 0, min = 0, odd = 1; expect <= 46340; //sqrt(max-int)
    expect++, min += odd, odd += 2)
{
    var max = min + odd - 1;
    if ((int)Math.Sqrt(min) != expect || (int)Math.Sqrt(max) != expect)
        throw new NotSupportedException();
}

Говоря оптимистично, современные чипы должны быть способны выдавать правильные результаты для sqrt в диапазоне int.

Я думаю, вы можете быть уверены, что он не будет детерминированным на всех платформах, если есть такие, где программа или оборудование с плавающей запятой могут изменить режим округления по сравнению с обычными настройками.

Существует также более тревожная проблема, когда входное значение превышает 2^52, поэтому мантисса двойной плавающей точки не может точно представлять входное значение y. Для некоторых неудачных значений y округление до ближайшего приведет к ложному ответу на x, который не удовлетворяет x*x <= y. Они довольно редки. Я выбрал их и получил 1:10^8 в начале проблемы и 3:10^7 для чисел >2^63.

Я не обнаружил никаких сбоев для y < 10^11, но это капля в море по сравнению с общим диапазоном int64. Мне кажется, что вы можете безопасно использовать sqrt(y) при условии, что вы очистите результат, чтобы защититься от редких исключений, когда ошибка округления вызывает проблемы (и правила округления или защитные цифры могут немного отличаться в зависимости от некоторых более быстрых процессоров).

Уточнение, которое я предлагаю в целочисленной арифметике, должно быть быстрым, поскольку это всего лишь одно умножение проверки работоспособности и условного декремента. Это тестовый код, который я собрал, чтобы быстро просмотреть.

#include <iostream>
#include <math.h>
#include <inttypes.h>

unsigned int safesqrt(uint64_t y)
{
  // defined to *always* give a deterministic result such that x*x <= y
  // sqrt(y) becomes tricky when y exceeds the 53 bit mantissa of double FP 
  // ironically I think this is one example where x87 80 bit FP would win out!
  // Its 64 bit mantissa can exactly represent every possible integer input.
  // 
  // double results round high for a small fraction of values (approx 1 in 10^8 rising to 3 in 10^7)
  // edge values for y where the mantissa cannot represent the full precision and 
  // sqrt(x) returns a rounded to nearest integer value are the problem

  int x = (unsigned) sqrt((double)y);
  uint64_t x2;
  x2 = x;
  x2 *= x2;
  if (x2 > y) x--; // defend against fail high when y > 0x0010 0000 0000 0000, 2^52
  return x;
}

int main()
{
  uint64_t base, x2, y, z;
  double dx;
  unsigned x, nrx, nrx2, lastbadx = 0, badcount = 0;
  int i = 1;
  base = 1 ;
  base <<= 62;
  printf("base = %18I64x\n", base);
  printf("     N \t\t  y\t\t\t x^2  \t\t     x (double)     (int) x \t NR(x) \t Nr(NR(x))  bad\n");
  for (y = base; y<base+100000000000; y++)
  {
      dx = sqrt((double)y);
      x = (unsigned)(dx);
      x2 = (uint64_t)x;
      x2 *= x2;
      if (x2 > y)  // in an ideal world this shouldn't happen
      {
          nrx = (int)((y / x + x) / 2);
          nrx2 = (int)((y / nrx + nrx) / 2);  // check to see if NR converges or oscillates
          if (x != lastbadx)
          {
              printf(" %5u : %20I64u  %20I64u  %18.10gf  %10u %10u %10u", i++, y, x2, dx, x, nrx, nrx2);
              lastbadx = x;
              badcount++;
          }
          else
              badcount++;
      }
      else
      {
          if (badcount) printf(" [%i]\n", badcount);
          badcount = 0;
      }
  }
}

Я оставил его включенным на ночь, и он обнаружил около 1400 плохих случаев в блоке y>2^63. Кстати, всего за несколько минут я не обнаружил никаких ошибок в первых целочисленных значениях 10 ^ 11 (поэтому 10 ^ 12, 10 ^ 13 можно было бы легко проверить методом перебора). Это все еще капля в море по сравнению с полным динамическим диапазоном 10^19.

Вы также можете защититься от сбоя, проверив это x2+2*x+1 > y, но я думаю, что способ округления до ближайшего и аппаратного sqrt с последующим усечением до целого числа, шансы на то, что это когда-либо сработает, исчезающе малы.