Driver86
@Driver86
Немодератор toster.ru

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?

Как быстро проверить, является ли некоторое огромное число (от 100 знаков) квадратом целого числа?
  • Вопрос задан
  • 322 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, гуглер, экс-олимпиадник.
Можно попробовать вычислить корень быстрым алгоритмом. Но там сложно. Гуглите Karatsuba square root. Есть открытые реализации. Есть еще какой-то адский метод через быстрое преобразование Фурье, попробуйте погуглить и его.

Более простой в реализации, но менее быстрый метод вычисления корня - бинарный поиск. Храните l, r, l^2, r^2 и lr. По этим числам можно вычислить m=(l+r)/2, m^2, m*l, m*r без длинных умножений, а только складывая длинные числа и деля на 2. Вам надо поддерживать, чтобы l^2 <= n <= r^2. Изначально можно сделать l=1, r=10^51 (или больше - половина длины входного числа + немного, чтобы точно квадрат был больше n), потом делить отрезок пополам и отбрасывать ненужную половину.

Еще есть вероятностный метод через символ Лежандра/Якоби. Это будет самым быстрым методом.

Это как смотреть на последнюю цифру. Квадраты могут давать там 0, 1, 4, 9, 6, 5. Но нет ни одного квадрата, который оканчивался бы на 2. Т.е. если число заканчивается на 2, то можно сразу говорить, что это не квадрат. Это мы взяли остаток от деления на 10 (последняя цифра) и посмотрели, какие из них хорошие. Вот символ Лежандра - это такая проверка для модуля по любому простому числу (а не 10).

Если брать некоторое простое число p, то n может быть квадратом, только если символ Лежандра (n/p) - равен 1 или 0 (По научному: n - должно быть квадратичным вычетом).

Если брать небольшие (<64-битные) простые числа, то можно за линию считать n%p и потом вычислять символ Лежандра (n%p/p) по алгоритму через символ Якоби за O(log(p)^2). Когда подсчитали символ Лежандра и если он -1, то n - точно не корень.

Тут проблема в том, что это необходимый, но недостаточный критерий - если для какого-то p вы получили -1 - то это точно не квадрат. Но возможно можно подобрать такое число, что все ваши тесты дадут 1, а оно не квадрат. Поэтому надо брать много простых чисел. Скажем, 20. Желательно еще числа брать достаточно большими. Но их не надо искать каждый раз, можно захардкодить. Грубая прикидка говорит, что вероятность ошибки такого алгоритма 2^(-количество простых чисел).

Т.е. берете много простых чисел. Считаете для каждого n%p выполняя деление большого числа на короткое (один проход по массиву цифр). Потом считаете символ Лежандра. Если получили где-то -1 - то точно не квадрат. Иначе - скорее всего квадрат.

Можно совместить вероятностный тест и вычисление корня. Сначала проверьте парочку простых чисел на символ Лежандра для отсечения точно не квадратов. Еще проверку последней цифры можно сделать, это очень дешево. Если не отсеклись, то считайте корень. Так будет всегда работать правильно но будет быстрее работать в некоторых случаях.
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
@jkotkot
режим сарказма
Ну если очень быстро это нужно предварительно просчитать нужный диапазон, а потом по мапе проверять.
Ответ написан
Griboks
@Griboks
Быстрый корень, а лучше проверьте процессор на подобную инструкцию. Иными словами, быстро != просто != точно и т.д., причём быстрота измеряется в тактах, поэтому такие алгоритмы имеют мало общего с математикой.

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

А если мы говорим про математику, то тут можно использовать свойства чисел (например, квадрат не может оканчиваться на 7 или 3) + проверку на простые числа.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы