Самый быстрый способ определить, является ли квадратный корень целого числа целым числом ⇐ JAVA

[Anonymous]

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

• Я сделал это простым способом, используя встроенную функцию Math.sqrt()
  , но мне интересно, есть ли способ сделать это быстрее,
  ограничив себя только целочисленными значениями домена.
• Поддерживать таблицу поиска нецелесообразно (поскольку существует около
  231,5 целых чисел, квадрат которых меньше 263).

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

Код: Выделить всё

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

long tst = (long)(Math.sqrt(n) + 0.5);
return tst*tst == n;
}

Примечание. Я использую эту функцию во многих задачах Project Euler. Таким образом, никому больше никогда не придется поддерживать этот код. И такая микрооптимизация действительно может изменить ситуацию, поскольку часть задачи состоит в том, чтобы выполнить каждый алгоритм менее чем за минуту, а в некоторых задачах эту функцию придется вызывать миллионы раз.



Я пробовал разные решения проблемы:

• После исчерпывающего тестирования я обнаружил, что добавление 0,5 к Результат Math.sqrt() не нужен, по крайней мере, на моей машине.
• Быстрый обратный квадратный корень работал быстрее, но давал неверные результаты для n >= 410881. Однако, как предложил Бобби Шафто, мы можем использовать хак FISR для n < 410881.
• Метод Ньютона был немного медленнее, чем Math.sqrt(). Вероятно, это связано с тем, что Math.sqrt() использует нечто похожее на метод Ньютона, но реализовано аппаратно, поэтому он намного быстрее, чем в Java. Кроме того, метод Ньютона по-прежнему требовал использования двойных чисел.
• Модифицированный метод Ньютона, в котором использовалось несколько приемов, чтобы использовались только целочисленные математические операции, требовал некоторых хаков, чтобы избежать переполнения (я хочу, чтобы эта функция работала со всеми положительными 64-битными целыми числами со знаком), и он все еще был медленнее, чем Math.sqrt().
• Двоичная обработка была еще медленнее. Это имеет смысл, поскольку для поиска квадратного корня из 64-битного числа в среднем требуется 16 проходов.
• Согласно тестам Джона, использование операторов or в C++ выполняется быстрее, чем использование переключателя, но в Java и C#, похоже, нет никакой разницы между or и переключателем.
• Я также попробовал создать таблицу поиска (в виде частного статического массива из 64 логических значений) ценности). Тогда вместо оператора switch или or я бы просто сказал if(lookup[(int)(n&0x3F)]) { test } else return false;. К моему удивлению, это было (немного) медленнее. Это связано с тем, что в Java проверяются границы массива.

Подробнее здесь: https://stackoverflow.com/questions/295 ... an-integer