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

Question

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

1. Я сделал это простым способом, используя встроенный Math.sqrt() функции, но мне интересно, если есть способ сделать это быстрее, ограничить себя только целочисленным доменом.
2. Ведение справочной таблицы нецелесообразно (поскольку существует около 2 ^31,5 целые числа, площадь которых меньше 2 ⁶³ ).

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

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

Answer 1

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

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

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

например.

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

Answer 2

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

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

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

Answer 3

Что касается метода 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;

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

Answer 4

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

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

Answer 5

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