Comments 13
Забавно, но именно сегодня задался решением той же проблемы — является ли целое число квадратом (простенькая задачка в codewars). В результате прикинул, что самым дешевым способом может оказаться анализ числа по признакам, приведенным в википедии:
В десятичной записи квадратные числа имеют следующие свойства:
Последняя цифра квадрата в десятичной записи может быть равной 0, 1, 4, 5, 6 или 9 (квадратичные вычеты по модулю 10).
Квадрат не может оканчиваться нечётным количеством нолей.
Квадрат либо делится на 4, либо при делении на 8 даёт остаток 1. Квадрат либо делится на 9, либо при делении на 3 даёт остаток 1.
Две последние цифры квадрата в десятичной записи могут принимать значения 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89 или 96 (квадратичные вычеты по модулю 100).
А можете дать ссылку на ваше решение. Недавно сам делал эту задачу.
Ну это необходимые, но не достаточные условия
Вот именно. Зная их, можно лишь отсеять точно-не-квадраты.
я конечно понимаю, что мой метод работает медленнее, зато надежный как швейцарские часы и простой:
взять sqrt(x), округлить, возвести в квадрат, проверить, что совпадает с x.
Ну и в статье есть не очевидные утверждения:
Вроде как это даже правда и даже кем-то доказано, но догадаться до этого самостоятельно сложно. И не понятно, что делать с числами, у которых корня нет
взять sqrt(x), округлить, возвести в квадрат, проверить, что совпадает с x.
Ну и в статье есть не очевидные утверждения:
Для нечетного N и 2k, k > 3, если N ≡ 1 mod 8, то есть 4 разных корня по модулю 2k, а иначе корней нет. Нам нужен наименьший из этих четырех корней x. При этом другие три корня это 2k — x, 2k-1 + x и 2k — 2k-1 — x
Вроде как это даже правда и даже кем-то доказано, но догадаться до этого самостоятельно сложно. И не понятно, что делать с числами, у которых корня нет
Взять sqrt очень тяжко, как и делать округление. paluke, сделайте пожалуйста тест производительности, для round(sqrt(x)) и вашей функции. Интересно было б посмотреть
ну я указал, что это медленнее и зависит от того, насколько критична производительность в этом случае, я скорее к тому, что преждевременная оптимизацией заниматься не стоит. Тем более, что в приведенном способе все-равно придется это сделать, если обнаружится, что корня по модулю нет и в худшем случае производительность от этой оптимизации станет только хуже на несколько проверок. Если нужно прям очень производительно, то нужно просто преподсчитать все квадраты и искать бинарным поиском за O(log(sqrt(n))
На х86 при включении оптимизации sqrt будет инлайниться компилятором в sqrtsd (sse) или fsqrt (x87), и это на самом деле быстрее.
Этот метод может быть быстрее для BigInteger чисел. Ну или где-нибудь в embedded, где нет сопроцессора (правда непонятно, зачем в embedded может понадобиться корень).
Протестировал. sse чуть быстрее, х87 чуть медленее
Этот метод может быть быстрее для BigInteger чисел. Ну или где-нибудь в embedded, где нет сопроцессора (правда непонятно, зачем в embedded может понадобиться корень).
Протестировал. sse чуть быстрее, х87 чуть медленее
Двоичный поиск, конечно, чуть медленее, зато может искать floor/ceil квадратного корня и не зависит от типа данных.
Зачем изобретать велосипед, когда все уже придумано до нас?
Генри Уоррен, «Алгоритмические трюки для программистов», на основе алгоритма, описанного в 1945 году!!! Джоном фон Нейманном:
Группу операторов в if можно даже упростить, используя знаковый сдвиг вправо на 31 бит, избежав одной проверки и условного перехода:
Там же в книге есть и другие варианты поиска целочисленных корней (в том числе с разбором варианта идеи, предложенной топикстартером), в том числе и кубических. И много другого вкусного.
Код выше приведен как есть в книге, его нужно будет причесать в плане разрядности в зависимости от компилятора и операционной системы.
Генри Уоррен, «Алгоритмические трюки для программистов», на основе алгоритма, описанного в 1945 году!!! Джоном фон Нейманном:
int isqrt(unsigned x)
{
unsigned m, y, b;
m = 0x40000000;
y = 0;
while (m != 0)
{
b = y | m;
y >>= 1;
if (x >= b)
{
x -= b;
y |= m;
}
m >>= 2;
}
return y;
}
Группу операторов в if можно даже упростить, используя знаковый сдвиг вправо на 31 бит, избежав одной проверки и условного перехода:
int t = (int) (x | ~(x - b)) >> 31; // -1, если x >= b, иначе 0
x -= (b & t);
y |= (m & t);
Там же в книге есть и другие варианты поиска целочисленных корней (в том числе с разбором варианта идеи, предложенной топикстартером), в том числе и кубических. И много другого вкусного.
Код выше приведен как есть в книге, его нужно будет причесать в плане разрядности в зависимости от компилятора и операционной системы.
Заморачивался оптимизацией получения квадратного корня, когда участвовал в AI Cup. Пробовал фишки «из Quake», приблизительный обратный корень SSE и целочисленные приближения. На современном процессоре (у меня haswell) оно совершенно не стоит того. Деталей не помню, но ускорение дает только приблизительный обратный корень на SSE, и это ускорение несущественно — процентов 10-20 ценой потенциальных багов на потере точности и округлениях.
Понятно, что можно реализовать метод Ньютона в целых числах, но он требует деления на каждом шаге. А нельзя ли по другому?
А то есть операция взятия остатка не использует внутри себя операцию деления? Физически же остаток считается делением в столбик, или нет?
Sign up to leave a comment.
Вычисление целочисленного квадратного корня