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

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

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

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 с помощью JIT.

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

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

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

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

Сложность - 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;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Следующее упрощение решения 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;

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

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

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

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

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

И потом я вспомнил, что в исходном коде 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 бит квадрата. Последовательно исследуя большее количество битов, можно исключить до 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

Это самая быстрая реализация 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;
        }
    }

}

Должна быть возможность упаковать «не может быть идеальным квадратом, если последние 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,1,4,5,6,9). В противном случае это не может быть «идеальным квадратом».

например,

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

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

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

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

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

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

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

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

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

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

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

• переместить чек против 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;

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

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

Ваш алгоритм может быть почти оптимальным, но вы можете сделать быструю проверку, чтобы исключить некоторые возможности, прежде чем вызывать процедуру извлечения квадратного корня. Например, посмотрите на последнюю цифру своего номера в шестнадцатеричном формате, выполняя побитовое «и». Идеальные квадраты могут оканчиваться только на 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 #.

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

Вам следует с самого начала избавиться от 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% чисел.

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

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

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

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

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

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

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

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

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

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

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

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

(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 итераций.

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