为什么要乘以比服用平方根快很多倍？ [英] Why is multiplied many times faster than taking the square root?

问题描述

我有几个问题与下面的算法来判断一个数是素的，我也知道，随着筛埃拉托色尼的可以更快的响应。

I have several questions with the following algorithms to tell if a number is prime, I also know that with the sieve of Eratosthenes can be faster response.

1. 为什么要快，计算 II * SQRT（N）次。比的sqrt（N）只是一个时间？
2. 为什么的Math.sqrt（）比我的 SQRT更快的（）的方法？

3. 什么是这些算法为O（n），O（开方（N）），O（N日志（N））？复杂

1. Why is faster to compute i i * sqrt (n) times. than sqrt (n) just one time ?
2. Why Math.sqrt() is faster than my sqrt() method ?

3. What is the complexity of these algorithms O (n), O (sqrt (n)), O (n log (n))?

public class Main {

public static void main(String[] args) {

// Case 1 comparing Algorithms
long startTime = System.currentTimeMillis(); // Start Time
for (int i = 2; i <= 100000; ++i) {
    if (isPrime1(i))
        continue;
}
long stopTime = System.currentTimeMillis(); // End Time
System.out.printf("Duracion: %4d ms. while (i*i <= N) Algorithm\n",
        stopTime - startTime);

// Case 2 comparing Algorithms
startTime = System.currentTimeMillis();
for (int i = 2; i <= 100000; ++i) {
    if (isPrime2(i))
        continue;
}
stopTime = System.currentTimeMillis();
System.out.printf("Duracion: %4d ms. while (i <= sqrt(N)) Algorithm\n",
        stopTime - startTime);

// Case 3 comparing Algorithms
startTime = System.currentTimeMillis();
for (int i = 2; i <= 100000; ++i) {
    if (isPrime3(i))
        continue;
}
stopTime = System.currentTimeMillis();
System.out.printf(
          "Duracion: %4d ms. s = sqrt(N) while (i <= s) Algorithm\n",
          stopTime - startTime);

// Case 4 comparing Algorithms
startTime = System.currentTimeMillis();
for (int i = 2; i <= 100000; ++i) {
    if (isPrime4(i))
        continue;
}
stopTime = System.currentTimeMillis();
System.out.printf(
          "Duracion: %4d ms. s = Math.sqrt(N) while (i <= s) Algorithm\n",
          stopTime - startTime);
}

public static boolean isPrime1(int n) {
    for (long i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

public static boolean isPrime2(int n) {
    for (long i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

public static boolean isPrime3(int n) {
    double s = sqrt(n);
    for (long i = 2; i <= s; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

public static boolean isPrime4(int n) {
    // Proving wich if faster between my sqrt method or Java's sqrt
    double s = Math.sqrt(n);
    for (long i = 2; i <= s; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

public static double abs(double n) {
    return n < 0 ? -n : n;
}

public static double sqrt(double n) {
    // Newton's method, from book Algorithms 4th edition by Robert Sedgwick
    // and Kevin Wayne
    if (n < 0)
        return Double.NaN;

    double err = 1e-15;
    double p = n;

    while (abs(p - n / p) > err * n)
        p = (p + n / p) / 2.0;

    return p;
}
}

这是我的code也链接： http://ideone.com/Fapj1P

This is the link of my code also: http://ideone.com/Fapj1P

推荐答案

1。为什么更快地计算I * I，开方（N）次。超过的sqrt（N）只是一个时间？ 看看下面的复杂性。计算平方根的额外费用。

1. Why is faster to compute i*i, sqrt (n) times. than sqrt (n) just one time ? Look at the complexities below. The additional cost of computing square root.

2。为什么的Math.sqrt（）比我的sqrt（）方法快？
的Math.sqrt（）代表调用StrictMath.sqrt这是在硬件或本地code完成。

2. Why Math.sqrt() is faster than my sqrt() method ?
Math.sqrt() delegates call to StrictMath.sqrt which is done in hardware or native code.

3。什么是这些算法的复杂性？
您所描述的每个功能的复杂性

3. What is the complexity of these algorithms?
The complexity of each function you described

I = 2 ..我* I n种 O（开方（N））

I = 2 ..开方（N） O（开方（N）*的log（n））

I = 2 ..开方（牛顿法） O（开方（N））+ O（日志（N））

I = 2 ..开方（通过的Math.sqrt） O（开方（N））

牛顿法的从
复杂性 http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity

Newton's method's complexity from
http://en.citizendium.org/wiki/Newton%27s_method#Computational_complexity

这篇关于为什么要乘以比服用平方根快很多倍？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！