Я не знаю, упоминалось ли это ранее. Но я нашел решение здесь :

int result = (int)(floor(sqrt(b)) - ceil(sqrt(a)) + 1);

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

Должна быть возможность упаковать 'не может быть идеальным квадратом, если последние 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("};");
}

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

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

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

Если квадратный корень из натурального числа (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"

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

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

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

/**
 * 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. Однако его производительность можно улучшить, используя механизмы фильтрации, описанные в некоторых других публикациях.

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

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

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

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

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

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

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

Это доработка от десятичного к двоичному алгоритму старого калькулятора Марчанта (извините, у меня нет ссылки) в 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

Вот обработка что-то похожее (пожалуйста, не голосуйте за стиль кодирования / запахи или неуклюжий ввод-вывод - это алгоритм, который имеет значение, а 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;
};

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

И затем я помню, было это окружение функции вокруг 'сети от Исходного кода 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;
}

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

Это должно быть применимым и могло бы даже быть быстрее, это от одной из феноменальной идентификационной игры программного обеспечения!

Это записано в C++, но не должно быть слишком трудно снова использовать ту же технику в Java, как только Вы получаете идею:

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

метод Newton объяснил в Википедии: http://en.wikipedia.org/wiki/Newton%27s_method

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

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

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

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

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

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

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

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 #.

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

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

(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: Вы близки, но это не прекрасно: возвратите 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 повторения.

Я хочу, чтобы эта функция работала со всеми положительными 64-битными целыми числами со знаком

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

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

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

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

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

Между прочим, если Java имеет способ сохранить упакованный массив битов для таблицы поиска, не используйте его. 110 880 32-разрядных слов не являются большим количеством RAM в эти дни, и выборка машинного слова будет быстрее, чем выборка единственного бита.

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

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

// 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 Caliper 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

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

Сначала создайте таблицу квадратов простых чисел, которые меньше, чем 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 в своем ответе.

Необходимо избавиться от части с 2 питанием 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% чисел.

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

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

• перемещают проверку по сравнению с 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 найдут полезным, является простым взломом, расширением тестирования особого случая, предложенного A. Король. Используйте единственное длинное значение в качестве небольшого массива, который не является проверенными границами. Тем путем у Вас есть булев поиск на 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 работает приблизительно в 1/3 время на моей core2 машине дуэта. Я подозреваю, что дальнейшие тонкие настройки в том же направлении могли уменьшить время далее в среднем, но каждый раз Вы проверяете, Вы обмениваете больше тестирования на большее количество устранения, таким образом, Вы не можете пойти слишком много дальше на той дороге.

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

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

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

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

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

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

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

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

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

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

• Дополнительный тест mod-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;
        }
    }

}

"I'm looking for the fastest way to determine if a long value is a perfect square (i.e. its square root is another integer)."

The answers are impressive, but I failed to see a simple check :

check whether the first number on the right of the long it a member of the set (0,1,4,5,6,9) . If it is not, then it cannot possibly be a 'perfect square' .

eg.

4567 - cannot be a perfect square.