Если вам нужна скорость, учитывая, что ваши целые числа имеют конечный размер, я подозреваю, что самый быстрый способ будет включать (а) разделение параметров по размеру (например, на категории по наибольшему набору битов), а затем проверку значения по массиву идеальных квадратов в пределах этого диапазона.

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

А потом я вспомнил, что в исходном коде Quake кружилась эта функция:

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 ); // wtf?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

  #ifndef Q3_VM
  #ifdef __linux__
    assert( !isnan(y) ); // bk010122 - FPE?
  #endif
  #endif
  return y;
}

Что в основном вычисляет квадратный корень, используя функцию приближения Ньютона (не могу вспомнить точное имя).

Он должен быть удобен в использовании и может быть даже быстрее, это из одной из феноменальных игр программного обеспечения id!

Он написан на C++, но не должно быть слишком сложно повторно использовать тот же метод в Java, как только вы поймете идею:

Первоначально я нашел его по адресу: http://www.codemaestro.com/reviews/9

Метод Ньютона, объясненный в википедии: http://en.wikipedia.org/wiki/Newton%27s_method

Вы можете перейти по ссылке, чтобы получить более подробное объяснение того, как это работает, но если вам все равно, то это примерно то, что я помню из блога и из курса численного анализа:

• * (long*) &y - это, по сути, функция быстрого преобразования в длинные, поэтому целочисленные операции могут применяться к необработанным байтам.
• строка 0x5f3759df - (i >> 1); - это предварительно рассчитанное начальное значение для функции аппроксимации.
• * (float*) &i преобразует значение обратно в число с плавающей запятой.
• строка y = y * ( threehalfs - ( x2 * y * y ) ) в основном повторяет значение функции снова.

Функция приближения дает более точные значения, чем больше вы повторяете функцию по результату. В случае Quake одна итерация «достаточно хороша», но если бы она не была для вас ... тогда вы могли бы добавить столько итераций, сколько вам нужно.

Это должно быть быстрее, потому что оно сокращает количество операций деления, выполняемых при наивном извлечении квадратного корня, до простого деления на 2 (фактически операция умножения * 0.5F) и заменяет его несколькими фиксированными операциями умножения.

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

(n+1)^2 = n^2 + 2n + 1
(n-1)^2 = n^2 - 2n + 1

Итак, рассчитав n^2, можно получить следующие варианты:

• n^2 = target: готово, верните истину
• n^2 + 2n + 1 > target > n^2: вы близки, но это не идеально: return false
• n^2 - 2n + 1 < target < n^2: то же самое
• target < n^2 - 2n + 1: двоичное прерывание на нижнем n
• target > n^2 + 2n + 1: двоичное прерывание на более высоком n

(Извините, здесь используется n в качестве вашего текущего предположения и target в качестве параметра. Приносим извинения за путаницу!)

Не знаю, будет ли это быстрее или нет, но попробовать стоит.

Обновлено: двоичный чоп не должен принимать весь диапазон целых чисел, либо (2^x)^2 = 2^(2x), поэтому, как только вы найдете верхний установленный бит в своей цели (что можно сделать с помощью хитрого трюка; я точно забыл, как ) вы можете быстро получить ряд возможных ответов. Имейте в виду, что наивная двоичная отбивка по-прежнему займет всего 31 или 32 итерации.

Я не уверен, будет ли это быстрее или даже точнее, но вы могли бы использовать алгоритм Магический квадратный корень Джона Кармака, чтобы быстрее вычислить квадратный корень. Вероятно, вы могли бы легко проверить это для всех возможных 32-битных целых чисел и убедиться, что вы действительно получили правильные результаты, поскольку это всего лишь приближение. Однако теперь, когда я думаю об этом, использование двойников также приближается, поэтому я не уверен, как это повлияет на игру.

Не знаю, какова самая быстрая, но самый простой - это извлечь квадратный корень обычным способом, умножить результат на себя и посмотреть, соответствует ли он исходному значению.

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

Вам нужно будет провести сравнительный анализ. Лучший алгоритм будет зависеть от распределения ваших входных данных.

Ваш алгоритм может быть почти оптимальным, но вы можете сделать быструю проверку, чтобы исключить некоторые возможности, прежде чем вызывать процедуру извлечения квадратного корня. Например, посмотрите на последнюю цифру своего числа в шестнадцатеричном формате, выполнив побитовое «и». Идеальные квадраты могут оканчиваться только на 0, 1, 4 или 9 в базе 16, поэтому для 75% ваших входных данных (при условии, что они распределены равномерно) вы можете избежать вызова квадратного корня в обмен на очень быстрое вращение битов.

Кип протестировал следующий код, реализующий шестнадцатеричный трюк. При тестировании чисел от 1 до 100000000 этот код работал в два раза быстрее оригинала.

public final static boolean isPerfectSquare(long n)
{
    if (n < 0)
        return false;

    switch((int)(n & 0xF))
    {
    case 0: case 1: case 4: case 9:
        long tst = (long)Math.sqrt(n);
        return tst*tst == n;

    default:
        return false;
    }
}

Когда я тестировал аналогичный код на C++, он действительно работал медленнее, чем оригинал. Однако, когда я исключил оператор switch, шестнадцатеричный трюк снова сделал код вдвое быстрее.

int isPerfectSquare(int n)
{
    int h = n & 0xF;  // h is the last hex "digit"
    if (h > 9)
        return 0;
    // Use lazy evaluation to jump out of the if statement as soon as possible
    if (h != 2 && h != 3 && h != 5 && h != 6 && h != 7 && h != 8)
    {
        int t = (int) floor( sqrt((double) n) + 0.5 );
        return t*t == n;
    }
    return 0;
}

Исключение оператора switch мало повлияло на код C#.

Должно быть намного быстрее использовать Метод Ньютона для вычисления Целочисленный квадратный корень, затем возвести это число в квадрат и проверить, как вы это делаете в вашем текущем решении. Метод Ньютона является основой решения Кармака, упомянутого в некоторых других ответах. Вы сможете получить более быстрый ответ, поскольку вас интересует только целая часть корня, что позволит вам быстрее остановить алгоритм аппроксимации.

Еще одна оптимизация, которую вы можете попробовать: если Цифровой корень числа не заканчивается на 1, 4, 7 или 9 число нет - полный квадрат. Это можно использовать как быстрый способ устранить 60% ваших входных данных перед применением более медленного алгоритма извлечения квадратного корня.

Если скорость вызывает беспокойство, почему бы не разделить наиболее часто используемый набор входных данных и их значений в поисковую таблицу, а затем применить любой оптимизированный магический алгоритм, который вы придумали для исключительных случаев?

I want this function to work with all positive 64-bit signed integers

Math.sqrt() работает с двойными значениями в качестве входных параметров, поэтому вы не получите точных результатов для целых чисел больше 2 ^ 53.

Было отмечено, что последние цифры полного квадрата d могут принимать только определенные значения. Последние цифры d (в основании b) числа n совпадают с остатком, когда n делится на bd, т.е. в обозначении C n % pow(b, d).

Это можно обобщить на любой модуль m, т.е. n % m можно использовать для исключения некоторого процента чисел из точных квадратов. Модуль, который вы в настоящее время используете, равен 64, что позволяет 12, т.е. 19% остатков, как возможные квадраты. Немного написав код, я нашел модуль 110880, который допускает только 2016, т.е. 1,8% остатков как возможные квадраты. Таким образом, в зависимости от стоимости операции модуля (например, деления) и поиска в таблице по сравнению с квадратным корнем на вашем компьютере, использование этого модуля может быть быстрее.

Кстати, если в Java есть способ хранить упакованный массив битов для таблицы поиска, не используйте его. 110880 32-битных слов в наши дни не так много ОЗУ, и выборка машинного слова будет быстрее, чем выборка одного бита.

Для записи, другой подход - использовать разложение на простые числа. Если каждый множитель разложения четный, то число представляет собой полный квадрат. Итак, вам нужно посмотреть, можно ли разложить число как произведение квадратов простых чисел. Конечно, вам не нужно получать такое разложение, просто чтобы посмотреть, существует ли оно.

Сначала постройте таблицу квадратов простых чисел, меньших 2 ^ 32. Это намного меньше, чем таблица всех целых чисел до этого предела.

Тогда решение будет таким:

boolean isPerfectSquare(long number)
{
    if (number < 0) return false;
    if (number < 2) return true;

    for (int i = 0; ; i++)
    {
        long square = squareTable[i];
        if (square > number) return false;
        while (number % square == 0)
        {
            number /= square;
        }
        if (number == 1) return true;
    }
}

Я думаю, это немного загадочно. Что он делает, так это проверяет на каждом этапе, что квадрат простого числа делит входное число. Если это так, то он делит число на квадрат настолько долго, насколько это возможно, чтобы удалить этот квадрат из разложения на простые числа. Если в результате этого процесса мы пришли к 1, то входное число было разложением квадрата простых чисел. Если квадрат становится больше, чем само число, то этот квадрат или другие квадраты большего размера не могут его разделить, поэтому число не может быть разложением квадратов простых чисел.

Учитывая, что в настоящее время sqrt выполняется на оборудовании, и здесь необходимо вычислять простые числа, я думаю, что это решение намного медленнее. Но это должно дать лучшие результаты, чем решение с sqrt, которое не будет работать более 2 ^ 54, как говорит mrzl в своем ответе.

Для производительности очень часто приходится идти на компромиссы. Другие описали различные методы, однако вы отметили, что взлом Кармака был быстрее до определенных значений N. Затем вы должны проверить «n», и если оно меньше, чем это число N, используйте взлом Кармака, иначе используйте какой-либо другой описанный метод. в ответах здесь.

От двухступенчатой ​​части N следует избавиться с самого начала.

2-е изменение Магическое выражение для m ниже должно быть

m = N - (N & (N-1));

и не так, как написано

Конец 2-го редактирования

m = N & (N-1); // the lawest bit of N
N /= m;
byte = N & 0x0F;
if ((m % 2) || (byte !=1 && byte !=9))
  return false;

1-е редактирование:

Незначительное улучшение:

m = N & (N-1); // the lawest bit of N
N /= m;
if ((m % 2) || (N & 0x07 != 1))
  return false;

Конец 1-го редактирования

Теперь продолжайте как обычно. Таким образом, к тому времени, когда вы перейдете к части с плавающей запятой, вы уже избавитесь от всех чисел, у которых 2-степенная часть нечетна (примерно половина), и тогда вы будете учитывать только 1/8 оставшейся части. Т.е. вы запускаете часть с плавающей запятой на 6% чисел.

Это переработка десятичного в двоичный старый алгоритм калькулятора Марчанта (извините, у меня нет ссылки) в Ruby, адаптированный специально для этого вопроса:

def isexactsqrt(v)
    value = v.abs
    residue = value
    root = 0
    onebit = 1
    onebit <<= 8 while (onebit < residue)
    onebit >>= 2 while (onebit > residue)
    while (onebit > 0)
        x = root + onebit
        if (residue >= x) then
            residue -= x
            root = x + onebit
        end
        root >>= 1
        onebit >>= 2
    end
    return (residue == 0)
end

Вот пример чего-то похожего (пожалуйста, не голосуйте за стиль кодирования / запахи или неуклюжие O / O - это алгоритм, который имеет значение, а C++ не является моим родным языком). В этом случае мы ищем остаток == 0:

#include <iostream>  

using namespace std;  
typedef unsigned long long int llint;

class ISqrt {           // Integer Square Root
    llint value;        // Integer whose square root is required
    llint root;         // Result: floor(sqrt(value))
    llint residue;      // Result: value-root*root
    llint onebit, x;    // Working bit, working value

public:

    ISqrt(llint v = 2) {    // Constructor
        Root(v);            // Take the root 
    };

    llint Root(llint r) {   // Resets and calculates new square root
        value = r;          // Store input
        residue = value;    // Initialise for subtracting down
        root = 0;           // Clear root accumulator

        onebit = 1;                 // Calculate start value of counter
        onebit <<= (8*sizeof(llint)-2);         // Set up counter bit as greatest odd power of 2 
        while (onebit > residue) {onebit >>= 2; };  // Shift down until just < value

        while (onebit > 0) {
            x = root ^ onebit;          // Will check root+1bit (root bit corresponding to onebit is always zero)
            if (residue >= x) {         // Room to subtract?
                residue -= x;           // Yes - deduct from residue
                root = x + onebit;      // and step root
            };
            root >>= 1;
            onebit >>= 2;
        };
        return root;                    
    };
    llint Residue() {           // Returns residue from last calculation
        return residue;                 
    };
};

int main() {
    llint big, i, q, r, v, delta;
    big = 0; big = (big-1);         // Kludge for "big number"
    ISqrt b;                            // Make q sqrt generator
    for ( i = big; i > 0 ; i /= 7 ) {   // for several numbers
        q = b.Root(i);                  // Get the square root
        r = b.Residue();                // Get the residue
        v = q*q+r;                      // Recalc original value
        delta = v-i;                    // And diff, hopefully 0
        cout << i << ": " << q << " ++ " << r << " V: " << v << " Delta: " << delta << "\n";
    };
    return 0;
};

Я придумал метод, который работает на ~ 35% быстрее, чем ваш код 6bit + Carmack + sqrt, по крайней мере, с моим процессором (x86) и языком программирования (C / C++). Ваши результаты могут отличаться, особенно потому, что я не знаю, как отразится фактор Java.

Мой подход состоит из трех частей:

1. Во-первых, отфильтруйте очевидные ответы. Это включает отрицательные числа и последние 4 бита. (Я обнаружил, что просмотр последних шести не помог.) Я также отвечаю «да» на 0. (Читая приведенный ниже код, обратите внимание, что я ввел int64 x.)

   if ( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
       return false;
   if ( x == 0 )
       return true;

2. Затем проверьте, является ли это квадратом по модулю 255 = 3 * 5 * 17. Поскольку это произведение трех различных простых чисел, только около 1/8 остатков по модулю 255 являются квадратами. Однако, по моему опыту, вызов оператора по модулю (%) стоит дороже, чем получаемая выгода, поэтому я использую битовые трюки с 255 = 2 ^ 8-1 для вычисления остатка. (Хорошо это или плохо, но я не использую трюк чтения отдельных байтов из слова, а только побитовые сдвиги и и.)

   int64 y = x;
   y = (y & 4294967295LL) + (y >> 32); 
   y = (y & 65535) + (y >> 16);
   y = (y & 255) + ((y >> 8) & 255) + (y >> 16);
   // At this point, y is between 0 and 511.  More code can reduce it farther.
   

   Чтобы проверить, является ли остаток квадратом, я ищу ответ в предварительно вычисленной таблице.

   if ( bad255[y] )
       return false;
   // However, I just use a table of size 512
   

3. Наконец, попробуйте вычислить квадратный корень, используя метод, аналогичный Лемма Гензеля. (Я не думаю, что это применимо напрямую, но оно работает с некоторыми изменениями.) Перед тем, как сделать это, я делю все степени двойки с помощью двоичного поиска:

   if ((x & 4294967295LL) == 0)
       x >>= 32;
   if ((x & 65535) == 0)
       x >>= 16;
   if ((x & 255) == 0)
       x >>= 8;
   if ((x & 15) == 0)
       x >>= 4;
   if ((x & 3) == 0)
       x >>= 2;

   На этом этапе, чтобы наше число было квадратом, оно должно быть 1 по модулю 8.

   if ((x & 7) != 1)
       return false;

   Основная структура леммы Гензеля такова. (Примечание: непроверенный код; если он не работает, попробуйте t = 2 или 8.)

   int64 t = 4, r = 1;
   t <<= 1; r += ((x - r * r) & t) >> 1;
   t <<= 1; r += ((x - r * r) & t) >> 1;
   t <<= 1; r += ((x - r * r) & t) >> 1;
   // Repeat until t is 2^33 or so.  Use a loop if you want.

   Идея состоит в том, что на каждой итерации вы добавляете один бит к r, «текущему» квадратному корню из x; каждый квадратный корень является точным по модулю все большей и большей степени 2, а именно t / 2. В конце концов, r и t / 2-r будут квадратными корнями из x по модулю t / 2. (Обратите внимание, что если r является квадратным корнем из x, то также и -r. Это верно даже по модулю чисел, но будьте осторожны, по модулю некоторых чисел вещи могут иметь даже более двух квадратных корней; в частности, это включает степени двойки. ) Поскольку наш фактический квадратный корень меньше 2 ^ 32, в этот момент мы можем просто проверить, являются ли r или t / 2-r действительными квадратными корнями. В моем фактическом коде я использую следующий модифицированный цикл:

   int64 r, t, z;
   r = start[(x >> 3) & 1023];
   do {
       z = x - r * r;
       if ( z == 0 )
           return true;
       if ( z < 0 )
           return false;
       t = z & (-z);
       r += (z & t) >> 1;
       if ( r > (t >> 1) )
           r = t - r;
   } while( t <= (1LL << 33) );

   Ускорение здесь достигается тремя способами: предварительно вычисленное начальное значение (эквивалентное ~ 10 итерациям цикла), более ранний выход из цикла и пропуск некоторых значений t. В последней части я смотрю на z = r - x * x и устанавливаю t как наибольшую степень двойки, делящую z, с помощью небольшого трюка. Это позволяет мне пропустить значения t, которые в любом случае не повлияли бы на значение r. Предварительно вычисленное начальное значение в моем случае выбирает «наименьший положительный» квадратный корень по модулю 8192.

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

typedef signed long long int int64;

int start[1024] =
{1,3,1769,5,1937,1741,7,1451,479,157,9,91,945,659,1817,11,
1983,707,1321,1211,1071,13,1479,405,415,1501,1609,741,15,339,1703,203,
129,1411,873,1669,17,1715,1145,1835,351,1251,887,1573,975,19,1127,395,
1855,1981,425,453,1105,653,327,21,287,93,713,1691,1935,301,551,587,
257,1277,23,763,1903,1075,1799,1877,223,1437,1783,859,1201,621,25,779,
1727,573,471,1979,815,1293,825,363,159,1315,183,27,241,941,601,971,
385,131,919,901,273,435,647,1493,95,29,1417,805,719,1261,1177,1163,
1599,835,1367,315,1361,1933,1977,747,31,1373,1079,1637,1679,1581,1753,1355,
513,1539,1815,1531,1647,205,505,1109,33,1379,521,1627,1457,1901,1767,1547,
1471,1853,1833,1349,559,1523,967,1131,97,35,1975,795,497,1875,1191,1739,
641,1149,1385,133,529,845,1657,725,161,1309,375,37,463,1555,615,1931,
1343,445,937,1083,1617,883,185,1515,225,1443,1225,869,1423,1235,39,1973,
769,259,489,1797,1391,1485,1287,341,289,99,1271,1701,1713,915,537,1781,
1215,963,41,581,303,243,1337,1899,353,1245,329,1563,753,595,1113,1589,
897,1667,407,635,785,1971,135,43,417,1507,1929,731,207,275,1689,1397,
1087,1725,855,1851,1873,397,1607,1813,481,163,567,101,1167,45,1831,1205,
1025,1021,1303,1029,1135,1331,1017,427,545,1181,1033,933,1969,365,1255,1013,
959,317,1751,187,47,1037,455,1429,609,1571,1463,1765,1009,685,679,821,
1153,387,1897,1403,1041,691,1927,811,673,227,137,1499,49,1005,103,629,
831,1091,1449,1477,1967,1677,697,1045,737,1117,1737,667,911,1325,473,437,
1281,1795,1001,261,879,51,775,1195,801,1635,759,165,1871,1645,1049,245,
703,1597,553,955,209,1779,1849,661,865,291,841,997,1265,1965,1625,53,
1409,893,105,1925,1297,589,377,1579,929,1053,1655,1829,305,1811,1895,139,
575,189,343,709,1711,1139,1095,277,993,1699,55,1435,655,1491,1319,331,
1537,515,791,507,623,1229,1529,1963,1057,355,1545,603,1615,1171,743,523,
447,1219,1239,1723,465,499,57,107,1121,989,951,229,1521,851,167,715,
1665,1923,1687,1157,1553,1869,1415,1749,1185,1763,649,1061,561,531,409,907,
319,1469,1961,59,1455,141,1209,491,1249,419,1847,1893,399,211,985,1099,
1793,765,1513,1275,367,1587,263,1365,1313,925,247,1371,1359,109,1561,1291,
191,61,1065,1605,721,781,1735,875,1377,1827,1353,539,1777,429,1959,1483,
1921,643,617,389,1809,947,889,981,1441,483,1143,293,817,749,1383,1675,
63,1347,169,827,1199,1421,583,1259,1505,861,457,1125,143,1069,807,1867,
2047,2045,279,2043,111,307,2041,597,1569,1891,2039,1957,1103,1389,231,2037,
65,1341,727,837,977,2035,569,1643,1633,547,439,1307,2033,1709,345,1845,
1919,637,1175,379,2031,333,903,213,1697,797,1161,475,1073,2029,921,1653,
193,67,1623,1595,943,1395,1721,2027,1761,1955,1335,357,113,1747,1497,1461,
1791,771,2025,1285,145,973,249,171,1825,611,265,1189,847,1427,2023,1269,
321,1475,1577,69,1233,755,1223,1685,1889,733,1865,2021,1807,1107,1447,1077,
1663,1917,1129,1147,1775,1613,1401,555,1953,2019,631,1243,1329,787,871,885,
449,1213,681,1733,687,115,71,1301,2017,675,969,411,369,467,295,693,
1535,509,233,517,401,1843,1543,939,2015,669,1527,421,591,147,281,501,
577,195,215,699,1489,525,1081,917,1951,2013,73,1253,1551,173,857,309,
1407,899,663,1915,1519,1203,391,1323,1887,739,1673,2011,1585,493,1433,117,
705,1603,1111,965,431,1165,1863,533,1823,605,823,1179,625,813,2009,75,
1279,1789,1559,251,657,563,761,1707,1759,1949,777,347,335,1133,1511,267,
833,1085,2007,1467,1745,1805,711,149,1695,803,1719,485,1295,1453,935,459,
1151,381,1641,1413,1263,77,1913,2005,1631,541,119,1317,1841,1773,359,651,
961,323,1193,197,175,1651,441,235,1567,1885,1481,1947,881,2003,217,843,
1023,1027,745,1019,913,717,1031,1621,1503,867,1015,1115,79,1683,793,1035,
1089,1731,297,1861,2001,1011,1593,619,1439,477,585,283,1039,1363,1369,1227,
895,1661,151,645,1007,1357,121,1237,1375,1821,1911,549,1999,1043,1945,1419,
1217,957,599,571,81,371,1351,1003,1311,931,311,1381,1137,723,1575,1611,
767,253,1047,1787,1169,1997,1273,853,1247,413,1289,1883,177,403,999,1803,
1345,451,1495,1093,1839,269,199,1387,1183,1757,1207,1051,783,83,423,1995,
639,1155,1943,123,751,1459,1671,469,1119,995,393,219,1743,237,153,1909,
1473,1859,1705,1339,337,909,953,1771,1055,349,1993,613,1393,557,729,1717,
511,1533,1257,1541,1425,819,519,85,991,1693,503,1445,433,877,1305,1525,
1601,829,809,325,1583,1549,1991,1941,927,1059,1097,1819,527,1197,1881,1333,
383,125,361,891,495,179,633,299,863,285,1399,987,1487,1517,1639,1141,
1729,579,87,1989,593,1907,839,1557,799,1629,201,155,1649,1837,1063,949,
255,1283,535,773,1681,461,1785,683,735,1123,1801,677,689,1939,487,757,
1857,1987,983,443,1327,1267,313,1173,671,221,695,1509,271,1619,89,565,
127,1405,1431,1659,239,1101,1159,1067,607,1565,905,1755,1231,1299,665,373,
1985,701,1879,1221,849,627,1465,789,543,1187,1591,923,1905,979,1241,181};

bool bad255[512] =
{0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,
 1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,
 0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,1,
 1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,
 1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,
 1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,
 1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,
 1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
 0,0,1,1,0,1,1,1,1,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,
 1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,1,1,1,
 0,1,0,1,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,0,1,
 1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,
 1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,
 1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,
 1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,
 1,0,1,1,1,0,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,
 0,0};

inline bool square( int64 x ) {
    // Quickfail
    if ( x < 0 || (x&2) || ((x & 7) == 5) || ((x & 11) == 8) )
        return false;
    if ( x == 0 )
        return true;

    // Check mod 255 = 3 * 5 * 17, for fun
    int64 y = x;
    y = (y & 4294967295LL) + (y >> 32);
    y = (y & 65535) + (y >> 16);
    y = (y & 255) + ((y >> 8) & 255) + (y >> 16);
    if ( bad255[y] )
        return false;

    // Divide out powers of 4 using binary search
    if ((x & 4294967295LL) == 0)
        x >>= 32;
    if ((x & 65535) == 0)
        x >>= 16;
    if ((x & 255) == 0)
        x >>= 8;
    if ((x & 15) == 0)
        x >>= 4;
    if ((x & 3) == 0)
        x >>= 2;

    if ((x & 7) != 1)
        return false;

    // Compute sqrt using something like Hensel's lemma
    int64 r, t, z;
    r = start[(x >> 3) & 1023];
    do {
        z = x - r * r;
        if ( z == 0 )
            return true;
        if ( z < 0 )
            return false;
        t = z & (-z);
        r += (z & t) >> 1;
        if ( r > (t  >> 1) )
            r = t - r;
    } while( t <= (1LL << 33) );

    return false;
}

Должно быть возможно упаковать «не может быть идеального квадрата, если последние X цифр равны N» гораздо эффективнее, чем это! Я буду использовать 32-битные целые числа Java и произведу достаточно данных, чтобы проверить последние 16 бит числа - это 2048 шестнадцатеричных значений int.

...

В порядке. Либо я столкнулся с какой-то теорией чисел, которая мне немного недоступна, либо в моем коде есть ошибка. В любом случае вот код:

public static void main(String[] args) {
    final int BITS = 16;

    BitSet foo = new BitSet();

    for(int i = 0; i< (1<<BITS); i++) {
        int sq = (i*i);
        sq = sq & ((1<<BITS)-1);
        foo.set(sq);
    }

    System.out.println("int[] mayBeASquare = {");

    for(int i = 0; i< 1<<(BITS-5); i++) {
        int kk = 0;
        for(int j = 0; j<32; j++) {
            if (foo.get((i << 5) | j)) {
                kk |= 1<<j;
            }
        }
        System.out.print("0x" + Integer.toHexString(kk) + ", ");
        if (i%8 == 7) System.out.println();
    }
    System.out.println("};");
}

и вот результаты:

(ed: исключено из-за низкой производительности в prettify.js; просмотрите историю изменений, чтобы увидеть.)

Что касается метода Кармака, кажется, что было бы довольно легко просто повторить итерацию еще раз, что должно удвоить количество цифр точности. В конце концов, это чрезвычайно усеченный итерационный метод - метод Ньютона, с очень хорошим первым предположением.

Что касается ваших текущих результатов, я вижу две микрооптимизации:

• переместите проверку против 0 после проверки, используя mod255
• переставьте делительные степени четырех, чтобы пропустить все проверки для обычного (75%) случая.

То есть:

// Divide out powers of 4 using binary search

if ((n & 0x3L) == 0) {
  n >>=2;

  if ((n & 0xffffffffL) == 0)
    n >>= 32;
  if ((n & 0xffffL) == 0)
      n >>= 16;
  if ((n & 0xffL) == 0)
      n >>= 8;
  if ((n & 0xfL) == 0)
      n >>= 4;
  if ((n & 0x3L) == 0)
      n >>= 2;
}

Еще лучше может быть простой

while ((n & 0x03L) == 0) n >>= 2;

Очевидно, было бы интересно узнать, сколько чисел отбирается на каждой контрольной точке - я очень сомневаюсь, что проверки действительно независимы, что усложняет задачу.

Вызов sqrt не совсем точен, как уже упоминалось, но интересно и поучительно, что он не сдувает другие ответы с точки зрения скорости. В конце концов, последовательность инструкций на языке ассемблера для sqrt крошечная. У Intel есть аппаратная инструкция, которая, как мне кажется, не используется в Java, потому что она не соответствует IEEE.

Так почему же это медленно? Потому что Java на самом деле вызывает подпрограмму C через JNI, и это на самом деле медленнее, чем вызов подпрограммы Java, которая сама по себе медленнее, чем выполнение ее встроенной. Это очень раздражает, и Java должна была предложить лучшее решение, т.е. при необходимости встроить вызовы библиотек с плавающей запятой. Ну что ж.

В C++ я подозреваю, что все сложные альтернативы будут проигрывать по скорости, но я не проверял их все. То, что я сделал и что Java-разработчики сочтут полезным, - это простой прием, расширение специального тестирования, предложенного А. Рексом. Используйте одно длинное значение в качестве битового массива, границы которого не проверяются. Таким образом, у вас есть 64-битный логический поиск.

typedef unsigned long long UVLONG
UVLONG pp1,pp2;

void init2() {
  for (int i = 0; i < 64; i++) {
    for (int j = 0; j < 64; j++)
      if (isPerfectSquare(i * 64 + j)) {
    pp1 |= (1 << j);
    pp2 |= (1 << i);
    break;
      }
   }
   cout << "pp1 = " << pp1 << "," << pp2 << "\n";  
}


inline bool isPerfectSquare5(UVLONG x) {
  return pp1 & (1 << (x & 0x3F)) ? isPerfectSquare(x) : false;
}

Процедура isPerfectSquare5 выполняется примерно в три раза быстрее на моей машине core2 duo. Я подозреваю, что дальнейшие настройки в том же направлении могут еще больше сократить время в среднем, но каждый раз, когда вы проверяете, вы жертвуете дополнительным тестированием в пользу большего устранения, поэтому вы не можете слишком далеко продвинуться по этому пути.

Конечно, вместо того, чтобы проводить отдельный тест на отрицательный результат, вы могли бы таким же образом проверить старшие 6 бит.

Обратите внимание, что все, что я делаю, - это исключаю возможные квадраты, но когда у меня есть потенциальный случай, я должен вызвать исходный встроенный isPerfectSquare.

Процедура init2 вызывается один раз для инициализации статических значений pp1 и pp2. Обратите внимание, что в моей реализации на C++ я использую unsigned long long, поэтому, поскольку вы подписаны, вам придется использовать оператор >>>.

Нет никакой внутренней потребности в проверке границ массива, но оптимизатор Java должен выяснить это довольно быстро, поэтому я не виню их в этом.

Project Euler упоминается в тегах, и многие проблемы в нем требуют проверки номеров >> 2^64. Большинство упомянутых выше оптимизаций не работают легко, когда вы работаете с 80-байтовым буфером.

Я использовал java BigInteger и немного измененную версию метода Ньютона, который лучше работает с целыми числами. Проблема заключалась в том, что точные квадраты n^2 сходились к (n-1) вместо n, потому что n^2-1 = (n-1)(n+1) и конечная ошибка были всего на один шаг ниже конечного делителя, и алгоритм завершился. Это было легко исправить, добавив единицу к исходному аргументу перед вычислением ошибки. (Добавьте два для кубических корней и т. д.)

Одним из хороших свойств этого алгоритма является то, что вы можете сразу определить, является ли число точным квадратом - окончательная ошибка (не исправление) в методе Ньютона будет равна нулю. Простая модификация также позволяет быстро вычислить floor(sqrt(x)) вместо ближайшего целого числа. Это удобно при решении нескольких задач Эйлера.

Мне нравится идея использовать почти правильный метод для некоторых входных данных. Вот версия с более высоким «смещением». Кажется, что код работает и проходит мой простой тестовый пример.

Просто замените свой:

if (n < 410881L){...}

код с этим:

if (n < 11043908100L) {
    //John Carmack hack, converted to Java.
    // See: http://www.codemaestro.com/reviews/9
    int i;
    float x2, y;

    x2 = n * 0.5F;
    y = n;
    i = Float.floatToRawIntBits(y);
    //using the magic number from 
    //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
    //since it more accurate
    i = 0x5f375a86 - (i >> 1);
    y = Float.intBitsToFloat(i);
    y = y * (1.5F - (x2 * y * y));
    y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate

    sqrt = Math.round(1.0F / y);
} else {
    //Carmack hack gives incorrect answer for n >= 11043908100.
    sqrt = (long) Math.sqrt(n);
}

«Я ищу самый быстрый способ определить, является ли длинное значение точным квадратом (т.е. его квадратный корень - другое целое число)».

Ответы впечатляют, но простой проверки я не увидел:

проверьте, входит ли первое число справа от длинного числа в набор (0,1,4,5,6,9). Если это не так, то это не может быть «идеальный квадрат».

например.

4567 - не может быть идеальным квадратом.

Это самая быстрая реализация Java, которую я мог придумать, с использованием комбинации методов, предложенных другими в этом потоке.

• Мод-256 тест
• Неточный тест mod-3465 (позволяет избежать целочисленного деления за счет некоторых ложных срабатываний)
• Квадратный корень с плавающей запятой, округление и сравнение с входным значением

Я также экспериментировал с этими модификациями, но они не улучшили производительность:

• Дополнительный тест мод-255
• Делим входное значение на степени 4
• Быстрый обратный квадратный корень (для работы с высокими значениями N требуется 3 итерации, что достаточно, чтобы сделать его медленнее, чем аппаратная функция извлечения квадратного корня).

public class SquareTester {

    public static boolean isPerfectSquare(long n) {
        if (n < 0) {
            return false;
        } else {
            switch ((byte) n) {
            case -128: case -127: case -124: case -119: case -112:
            case -111: case -103: case  -95: case  -92: case  -87:
            case  -79: case  -71: case  -64: case  -63: case  -60:
            case  -55: case  -47: case  -39: case  -31: case  -28:
            case  -23: case  -15: case   -7: case    0: case    1:
            case    4: case    9: case   16: case   17: case   25:
            case   33: case   36: case   41: case   49: case   57:
            case   64: case   65: case   68: case   73: case   81:
            case   89: case   97: case  100: case  105: case  113:
            case  121:
                long i = (n * INV3465) >>> 52;
                if (! good3465[(int) i]) {
                    return false;
                } else {
                    long r = round(Math.sqrt(n));
                    return r*r == n; 
                }
            default:
                return false;
            }
        }
    }

    private static int round(double x) {
        return (int) Double.doubleToRawLongBits(x + (double) (1L << 52));
    }

    /** 3465<sup>-1</sup> modulo 2<sup>64</sup> */
    private static final long INV3465 = 0x8ffed161732e78b9L;

    private static final boolean[] good3465 =
        new boolean[0x1000];

    static {
        for (int r = 0; r < 3465; ++ r) {
            int i = (int) ((r * r * INV3465) >>> 52);
            good3465[i] = good3465[i+1] = true;
        }
    }

}

Учитывая общую длину в битах (хотя здесь я использовал конкретный тип), я попытался разработать упрощенный алгоритм, как показано ниже. Изначально требуется простая и очевидная проверка на 0,1,2 или <0. Следующее просто в том смысле, что оно не пытается использовать какие-либо существующие математические функции. Большинство операторов можно заменить поразрядными операторами. Однако я не тестировал какие-либо эталонные данные. Я не специалист в математике или разработке компьютерных алгоритмов в частности, я бы хотел, чтобы вы указали на проблему. Я знаю, что здесь есть много шансов на улучшение.

int main()
{
    unsigned int c1=0 ,c2 = 0;  
    unsigned int x = 0;  
    unsigned int p = 0;  
    int k1 = 0;  
    scanf("%d",&p);  
    if (p % 2 == 0) {  
        x = p/2; 
    }  
    else {  
        x = (p/2) +1;  
    }  
    while(x) 
    {
        if ((x*x) > p) {  
            c1 = x;  
            x = x/2; 
        }else {  
            c2 = x;  
            break;  
        }  
    }  
    if ((p%2) != 0)  
        c2++;

    while(c2 < c1) 
    {  
        if ((c2 * c2 ) == p) {  
            k1 = 1;  
            break;  
        }  
        c2++; 
    }  
    if (k1)  
        printf("\n Perfect square for %d", c2);  
    else  
        printf("\n Not perfect but nearest to :%d :", c2);  
    return 0;  
}  

Я проверил все возможные результаты, когда наблюдались последние n бит квадрата. Последовательно исследуя большее количество битов, можно исключить до 5/6 входов. На самом деле я разработал это для реализации алгоритма факторизации Ферма, и там он работает очень быстро.

public static boolean isSquare(final long val) {
   if ((val & 2) == 2 || (val & 7) == 5) {
     return false;
   }
   if ((val & 11) == 8 || (val & 31) == 20) {
     return false;
   }

   if ((val & 47) == 32 || (val & 127) == 80) {
     return false;
   }

   if ((val & 191) == 128 || (val & 511) == 320) {
     return false;
   }

   // if ((val & a == b) || (val & c == d){
   //   return false;
   // }

   if (!modSq[(int) (val % modSq.length)]) {
        return false;
   }

   final long root = (long) Math.sqrt(val);
   return root * root == val;
}

Последний бит псевдокода можно использовать для расширения тестов, чтобы исключить больше значений. Вышеупомянутые тесты предназначены для k = 0, 1, 2, 3

Я провел собственный анализ нескольких алгоритмов в этой ветке и получил некоторые новые результаты. Вы можете увидеть эти старые результаты в истории редактирования этого ответа, но они неточны, так как я допустил ошибку и потратил время на анализ нескольких алгоритмов, которые не близки. Однако, извлекая уроки из нескольких разных ответов, у меня теперь есть два алгоритма, которые сокрушают «победителя» этой ветки. Вот основная вещь, которую я делаю не так, как все остальные:

// This is faster because a number is divisible by 2^4 or more only 6% of the time
// and more than that a vanishingly small percentage.
while((x & 0x3) == 0) x >>= 2;
// This is effectively the same as the switch-case statement used in the original
// answer. 
if ((x & 0x7) != 1) return false;

Однако эта простая строка, которая в большинстве случаев добавляет одну или две очень быстрые инструкции, значительно упрощает оператор switch-case в один оператор if. Однако он может увеличить время выполнения, если многие из протестированных чисел имеют значительную степень двойки.

Ниже представлены следующие алгоритмы:

• Интернет - опубликованный ответ Кипа
• Дюррон - Мой модифицированный ответ с использованием однопроходного ответа в качестве основы
• DurronTwo - Мой измененный ответ с использованием двухпроходного ответа (от @JohnnyHeggheim) с некоторыми другими небольшими изменениями.

Вот пример времени выполнения, если числа генерируются с помощью Math.abs(java.util.Random.nextLong()).

 0% Scenario{vm=java, trial=0, benchmark=Internet} 39673.40 ns; ?=378.78 ns @ 3 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 37785.75 ns; ?=478.86 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 35978.10 ns; ?=734.10 ns @ 10 trials

benchmark   us linear runtime
 Internet 39.7 ==============================
   Durron 37.8 ============================
DurronTwo 36.0 ===========================

vm: java
trial: 0

А вот пример среды выполнения, если она работает только с первым миллионом длинных позиций:

 0% Scenario{vm=java, trial=0, benchmark=Internet} 2933380.84 ns; ?=56939.84 ns @ 10 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 2243266.81 ns; ?=50537.62 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronTwo} 3159227.68 ns; ?=10766.22 ns @ 3 trials

benchmark   ms linear runtime
 Internet 2.93 ===========================
   Durron 2.24 =====================
DurronTwo 3.16 ==============================

vm: java
trial: 0

Как вы можете видеть, DurronTwo лучше подходит для больших входных данных, потому что он очень часто использует магический трюк, но становится заторможенным по сравнению с первым алгоритмом и Math.sqrt, потому что числа намного меньше. Между тем, более простой Durron является огромным победителем, потому что ему никогда не нужно много раз делить на 4 в первом миллионном числе.

Вот Durron:

public final static boolean isPerfectSquareDurron(long n) {
    if (n < 0) return false;
    if (n == 0) return true;

    long x = n;
    // This is faster because a number is divisible by 16 only 6% of the time
    // and more than that a vanishingly small percentage.
    while((x & 0x3) == 0) x >>= 2;
    // This is effectively the same as the switch-case statement used in the original
    // answer. 
    if ((x & 0x7) == 1) {

        long sqrt;
        if (x < 410881L)
        {
            int i;
            float x2, y;

            x2 = x * 0.5F;
            y  = x;
            i  = Float.floatToRawIntBits(y);
            i  = 0x5f3759df - ( i >> 1 );
            y  = Float.intBitsToFloat(i);
            y  = y * ( 1.5F - ( x2 * y * y ) );

            sqrt = (long)(1.0F/y);
        } else {
            sqrt = (long) Math.sqrt(x);
        }
        return sqrt*sqrt == x;
    }
    return false;
}

И DurronTwo

public final static boolean isPerfectSquareDurronTwo(long n) {
    if (n < 0) return false;
    // Needed to prevent infinite loop
    if (n == 0) return true;

    long x = n;
    while((x & 0x3) == 0) x >>= 2;
    if ((x & 0x7) == 1) {
        long sqrt;
        if (x < 41529141369L) {
            int i;
            float x2, y;

            x2 = x * 0.5F;
            y = x;
            i = Float.floatToRawIntBits(y);
            //using the magic number from 
            //http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf
            //since it more accurate
            i = 0x5f375a86 - (i >> 1);
            y = Float.intBitsToFloat(i);
            y = y * (1.5F - (x2 * y * y));
            y = y * (1.5F - (x2 * y * y)); //Newton iteration, more accurate
            sqrt = (long) ((1.0F/y) + 0.2);
        } else {
            //Carmack hack gives incorrect answer for n >= 41529141369.
            sqrt = (long) Math.sqrt(x);
        }
        return sqrt*sqrt == x;
    }
    return false;
}

И мой тестовый жгут: (Требуется штангенциркуль Google 0.1-rc5)

public class SquareRootBenchmark {
    public static class Benchmark1 extends SimpleBenchmark {
        private static final int ARRAY_SIZE = 10000;
        long[] trials = new long[ARRAY_SIZE];

        @Override
        protected void setUp() throws Exception {
            Random r = new Random();
            for (int i = 0; i < ARRAY_SIZE; i++) {
                trials[i] = Math.abs(r.nextLong());
            }
        }


        public int timeInternet(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if (SquareRootAlgs.isPerfectSquareInternet(trials[j])) trues++;
                }
            }

            return trues;   
        }

        public int timeDurron(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if (SquareRootAlgs.isPerfectSquareDurron(trials[j])) trues++;
                }
            }

            return trues;   
        }

        public int timeDurronTwo(int reps) {
            int trues = 0;
            for(int i = 0; i < reps; i++) {
                for(int j = 0; j < ARRAY_SIZE; j++) {
                    if (SquareRootAlgs.isPerfectSquareDurronTwo(trials[j])) trues++;
                }
            }

            return trues;   
        }
    }

    public static void main(String... args) {
        Runner.main(Benchmark1.class, args);
    }
}

Обновлено: Я создал новый алгоритм, который в одних сценариях работает быстрее, в других - медленнее. Я получил разные тесты, основанные на разных входных данных. Если мы вычислим по модулю 0xFFFFFF = 3 x 3 x 5 x 7 x 13 x 17 x 241, мы сможем исключить 97,82% чисел, которые не могут быть квадратами. Это можно (как бы) сделать в одной строке с помощью 5 побитовых операций:

if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;

Результирующий индекс представляет собой либо 1) остаток, 2) остаток + 0xFFFFFF, либо 3) остаток + 0x1FFFFFE. Конечно, нам нужна таблица поиска остатков по модулю 0xFFFFFF, которая представляет собой файл размером примерно 3 МБ (в данном случае хранится в виде десятичных чисел в текстовом формате ascii, не оптимально, но явно улучшается с помощью ByteBuffer и т. д. Но поскольку это предварительный расчет, он не имеет большого значения. Вы можете найти файл здесь (или сгенерируйте его самостоятельно):

public final static boolean isPerfectSquareDurronThree(long n) {
    if (n < 0) return false;
    if (n == 0) return true;

    long x = n;
    while((x & 0x3) == 0) x >>= 2;
    if ((x & 0x7) == 1) {
        if (!goodLookupSquares[(int) ((n & 0xFFFFFFl) + ((n >> 24) & 0xFFFFFFl) + (n >> 48))]) return false;
        long sqrt;
        if (x < 410881L)
        {
            int i;
            float x2, y;

            x2 = x * 0.5F;
            y  = x;
            i  = Float.floatToRawIntBits(y);
            i  = 0x5f3759df - ( i >> 1 );
            y  = Float.intBitsToFloat(i);
            y  = y * ( 1.5F - ( x2 * y * y ) );

            sqrt = (long)(1.0F/y);
        } else {
            sqrt = (long) Math.sqrt(x);
        }
        return sqrt*sqrt == x;
    }
    return false;
}

Я загружаю его в массив boolean вот так:

private static boolean[] goodLookupSquares = null;

public static void initGoodLookupSquares() throws Exception {
    Scanner s = new Scanner(new File("24residues_squares.txt"));

    goodLookupSquares = new boolean[0x1FFFFFE];

    while(s.hasNextLine()) {
        int residue = Integer.valueOf(s.nextLine());
        goodLookupSquares[residue] = true;
        goodLookupSquares[residue + 0xFFFFFF] = true;
        goodLookupSquares[residue + 0x1FFFFFE] = true;
    }

    s.close();
}

Пример выполнения. Он побеждал Durron (первая версия) во всех испытаниях, которые я проводил.

 0% Scenario{vm=java, trial=0, benchmark=Internet} 40665.77 ns; ?=566.71 ns @ 10 trials
33% Scenario{vm=java, trial=0, benchmark=Durron} 38397.60 ns; ?=784.30 ns @ 10 trials
67% Scenario{vm=java, trial=0, benchmark=DurronThree} 36171.46 ns; ?=693.02 ns @ 10 trials

  benchmark   us linear runtime
   Internet 40.7 ==============================
     Durron 38.4 ============================
DurronThree 36.2 ==========================

vm: java
trial: 0

Я довольно поздно на вечеринку, но надеюсь дать лучший ответ; короче и (при условии, что мой ориентир правильный) также намного Быстрее.

long goodMask; // 0xC840C04048404040 computed below
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // This tests if the 6 least significant bits are right.
    // Moving the to be tested bit to the highest position saves us masking.
    if (goodMask << x >= 0) return false;
    final int numberOfTrailingZeros = Long.numberOfTrailingZeros(x);
    // Each square ends with an even number of zeros.
    if ((numberOfTrailingZeros & 1) != 0) return false;
    x >>= numberOfTrailingZeros;
    // Now x is either 0 or odd.
    // In binary each odd square ends with 001.
    // Postpone the sign test until now; handle zero in the branch.
    if ((x&7) != 1 | x <= 0) return x == 0;
    // Do it in the classical way.
    // The correctness is not trivial as the conversion from long to double is lossy!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

Первый тест быстро выявляет большинство неквадратов. Он использует таблицу из 64 элементов, упакованную в long, поэтому нет затрат на доступ к массиву (косвенные проверки и проверки границ). Для равномерно случайного long вероятность завершения здесь составляет 81,25%.

Второй тест выявляет все числа, имеющие нечетное количество двоек при факторизации. Метод Long.numberOfTrailingZeros очень быстр, поскольку он преобразуется в одну инструкцию i86.

После отбрасывания конечных нулей третий тест обрабатывает числа, заканчивающиеся на 011, 101 или 111 в двоичном формате, которые не являются полными квадратами. Он также обрабатывает отрицательные числа и 0.

Последний тест возвращается к арифметике double. Поскольку double имеет только 53-битную мантиссу, преобразование из long в double включает округление для больших значений. Тем не менее, тест верен (если только доказательство не ошибочен).

Попытка внедрить идею mod255 не увенчалась успехом.

Целочисленная проблема заслуживает целочисленного решения. Таким образом

Выполните двоичный поиск (неотрицательных) целых чисел, чтобы найти наибольшее целое число t такое, что t**2 <= n. Потом проверьте, действительно ли r**2 = n. Это занимает время O (log n).

Если вы не знаете, как выполнять двоичный поиск положительных целых чисел, потому что набор неограничен, это легко. Вы начинаете с вычисления возрастающей функции f (выше f(t) = t**2 - n) по степеням двойки. Когда вы видите, что он становится положительным, вы нашли верхнюю границу. Затем вы можете выполнить стандартный двоичный поиск.

Следующее упрощение решения maaartinus, похоже, сокращает время выполнения на несколько процентных пунктов, но я недостаточно хорош в тестировании, чтобы создать тест, которому я могу доверять:

long goodMask; // 0xC840C04048404040 computed below
{
    for (int i=0; i<64; ++i) goodMask |= Long.MIN_VALUE >>> (i*i);
}

public boolean isSquare(long x) {
    // This tests if the 6 least significant bits are right.
    // Moving the to be tested bit to the highest position saves us masking.
    if (goodMask << x >= 0) return false;
    // Remove an even number of trailing zeros, leaving at most one.
    x >>= (Long.numberOfTrailingZeros(x) & (-2);
    // Repeat the test on the 6 least significant remaining bits.
    if (goodMask << x >= 0 | x <= 0) return x == 0;
    // Do it in the classical way.
    // The correctness is not trivial as the conversion from long to double is lossy!
    final long tst = (long) Math.sqrt(x);
    return tst * tst == x;
}

Стоит проверить, как, пропуская первый тест,

if (goodMask << x >= 0) return false;

повлияет на производительность.

Вот самый простой и лаконичный способ, хотя я не знаю, как он сравнивается с точки зрения циклов процессора. Это отлично работает, если вы хотите знать, является ли корень целым числом. Если вам действительно важно, является ли это целым числом, вы также можете это выяснить. Вот простая (и чистая) функция:

private static final MathContext precision = new MathContext(20);

private static final Function<Long, Boolean> isRootWhole = (n) -> {
    long digit = n % 10;
    if (digit == 2 || digit == 3 || digit == 7 || digit == 8) {
        return false;
    }
    return new BigDecimal(n).sqrt(precision).scale() == 0;
};

Если вам не нужна микрооптимизация, этот ответ лучше с точки зрения простоты и ремонтопригодности. Если вы будете вычислять отрицательные числа, вам нужно будет обработать это соответствующим образом и отправить абсолютное значение в функцию. Я включил небольшую оптимизацию, потому что ни один идеальный квадрат не имеет разряда десятков 2, 3, 7 или 8 из-за квадратичных вычетов по модулю 10.

На моем процессоре выполнение этого алгоритма на 0–10 000 000 занимало в среднем 1000–1100 наносекунд на вычисление.

Если вы выполняете меньшее количество вычислений, более ранние вычисления займут немного больше времени.

У меня был отрицательный комментарий, что моя предыдущая правка не работала для больших чисел. OP упомянул длинные длинные позиции, а наибольший точный квадрат, который является длинным, равен 9223372030926249001, поэтому этот метод работает для всех длинных позиций.

Не уверен, что это самый быстрый способ, но я наткнулся на него (давным-давно в старшей школе), когда мне было скучно и я играл со своим калькулятором на уроке математики. В то время я был действительно поражен, как это работает ...

public static boolean isIntRoot(int number) {
    return isIntRootHelper(number, 1);
}

private static boolean isIntRootHelper(int number, int index) {
    if (number == index) {
        return true;
    }
    if (number < index) {
        return false;
    }
    else {
        return isIntRootHelper(number - 2 * index, index + 1);
    }
}

Метод Ньютона с целочисленной арифметикой

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

/**
 * Test if the given number is a perfect square.
 * @param n Must be greater than 0 and less
 *    than Long.MAX_VALUE.
 * @return <code>true</code> if n is a perfect
 *    square, or <code>false</code> otherwise.
 */
public static boolean isSquare(long n)
{
    long x1 = n;
    long x2 = 1L;

    while (x1 > x2)
    {
        x1 = (x1 + x2) / 2L;
        x2 = n / x1;
    }

    return x1 == x2 && n % x1 == 0L;
}

Эта реализация не может конкурировать с решениями, использующими Math.sqrt. Однако его производительность можно улучшить, используя механизмы фильтрации, описанные в некоторых других сообщениях.

Вычисление квадратных корней методом Ньютона происходит ужасно быстро ... при условии, что начальное значение разумно. Однако разумного начального значения нет, и на практике мы заканчиваем делением пополам и поведением журнала (2 ^ 64). Чтобы быть действительно быстрым, нам нужен быстрый способ получить разумное начальное значение, а это означает, что нам нужно перейти на машинный язык. Если процессор предоставляет такую ​​команду, как POPCNT в Pentium, которая считает ведущие нули, мы можем использовать это для получения начального значения с половиной значащих битов. С осторожностью мы можем найти фиксированное количество шагов Ньютона, которого всегда будет достаточно. (Таким образом, отказ от цикла и очень быстрое выполнение.)

Второе решение идет через средство с плавающей запятой, которое может иметь быстрое вычисление sqrt (как сопроцессор i87). Даже переход через exp () и log () может быть быстрее, чем Ньютон выродился в двоичный поиск. В этом есть непростой аспект: анализ, зависящий от процессора, того, что и если после этого необходимо доработать.

Третье решение решает несколько иную проблему, но о нем стоит упомянуть, потому что ситуация описана в вопросе. Если вы хотите вычислить большое количество квадратных корней для чисел, которые немного отличаются, вы можете использовать итерацию Ньютона, если вы никогда не повторно инициализируете начальное значение, а просто оставите его там, где остановился предыдущий расчет. Я успешно использовал это как минимум в одной задаче Эйлера.

Вот решение «разделяй и властвуй».

Если квадратный корень из натурального числа (number) является натуральным числом (solution), вы можете легко определить диапазон для solution на основе количества цифр number:

• number имеет 1 цифру: solution в диапазоне = 1–4
• number состоит из 2 цифр: solution в диапазоне от 3 до 10.
• number состоит из 3 цифр: solution в диапазоне = 10-40.
• number состоит из 4 цифр: solution в диапазоне от 30 до 100.
• number имеет 5 цифр: solution в диапазоне = 100 - 400

Заметили повторение?

Вы можете использовать этот диапазон в подходе бинарного поиска, чтобы узнать, существует ли solution, для которого:

number == solution * solution

Вот код

Вот мой класс SquareRootChecker

public class SquareRootChecker {

    private long number;
    private long initialLow;
    private long initialHigh;

    public SquareRootChecker(long number) {
        this.number = number;

        initialLow = 1;
        initialHigh = 4;
        if (Long.toString(number).length() % 2 == 0) {
            initialLow = 3;
            initialHigh = 10;
        }
        for (long i = 0; i < Long.toString(number).length() / 2; i++) {
            initialLow *= 10;
            initialHigh *= 10;
        }
        if (Long.toString(number).length() % 2 == 0) {
            initialLow /= 10;
            initialHigh /=10;
        }
    }

    public boolean checkSquareRoot() {
        return findSquareRoot(initialLow, initialHigh, number);
    }

    private boolean findSquareRoot(long low, long high, long number) {
        long check = low + (high - low) / 2;
        if (high >= low) {
            if (number == check * check) {
                return true;
            }
            else if (number < check * check) {
                high = check - 1;
                return findSquareRoot(low, high, number);
            }
            else  {
                low = check + 1;
                return findSquareRoot(low, high, number);
            }
        }
        return false;
    }

}

А вот пример того, как им пользоваться.

long number =  1234567;
long square = number * number;
SquareRootChecker squareRootChecker = new SquareRootChecker(square);
System.out.println(square + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677489: true"

long notSquare = square + 1;
squareRootChecker = new SquareRootChecker(notSquare);
System.out.println(notSquare + ": " + squareRootChecker.checkSquareRoot()); //Prints "1524155677490: false"

Возможно, лучший алгоритм для решения проблемы - это алгоритм быстрого целочисленного извлечения квадратного корня https://stackoverflow.com/a/51585204/5191852

Там @Kde утверждает, что трех итераций метода Ньютона будет достаточно для точности ± 1 для 32-битных целых чисел. Конечно, для 64-битных целых требуется больше итераций, может быть 6 или 7.

Квадратный корень числа, учитывая, что число представляет собой полный квадрат.

Сложность log (n)

/**
 * Calculate square root if the given number is a perfect square.
 * 
 * Approach: Sum of n odd numbers is equals to the square root of n*n, given 
 * that n is a perfect square.
 *
 * @param number
 * @return squareRoot
 */

public static int calculateSquareRoot(int number) {

    int sum=1;
    int count =1;
    int squareRoot=1;
    while(sum<number) {
        count+=2;
        sum+=count;
        squareRoot++;
    }
    return squareRoot;
}