Какие квадраты быстрее или корни?

Question

for (int i = 2; i * i <= n; i++)

for (int i = 2; i <= SQRT(n); i++)

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

Answer 1

Почему бы не пропустить их обоих и использовать некоторые умные математики? В следующем коде избегайте того, чтобы оба они использовали свойство «Сумма первых нечетных чисел n» всегда как идеальный квадрат.

Бесстыдная вилка для моего старого поста в блоге (из моего мертвого блога)

int isPrime(int n)
{
    int squares = 1;
    int odd = 3;

    if( ((n & 1) == 0) || (n < 9)) return (n == 2) || ((n > 1) && (n & 1));
    else
    {
        for( ;squares <= n; odd += 2)
        {
            if( n % odd == 0) 
                return 0;
            squares+=odd;
        }
        return 1;
    }
}

Answer 2

Разве не должно быть комапрайона между

int sqrt = SQRT(n);
for (int i = 2; i <= sqrt; i++)

и

for (int i = 2; i * i <= n; i++)

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

Answer 3

Квадратный корень займет больше времени, если он не реализован в аппаратном обеспечении, поиске или специальной версии машинного кода. Итерация Ньютона - алгоритм выбора; оно сходится квадратично.

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

Answer 4

Компилятор может «кэшировать» результат SQRT (n), но i * i он должен вычислять на каждом шаге.

Answer 5

Квадрат будет быстрее.

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

В Java самое большое значение int равно 2 ^ 31 - 1, что означает, что его квадратный корень чуть меньше 46341. Если вы хотите искать простые числа, большие чемэто, квадратура остановит вас.