为什么乘以比平方根快许多倍？

我有几个问题用以下算法判断一个数字是否为素数，我也知道用Eratosthenes的筛子可以更快地响应。

1. 为什么计算ii * sqrt (n)次的速度更快。 比sqrt (n)只有一次？
2. 为什么Math.sqrt()比我的sqrt()方法更快？

3. 这些算法的复杂性是什么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  err * n) p = (p + n / p) / 2.0; return p; } } 

这也是我的代码的链接： http ： //ideone.com/Fapj1P

Answer 1

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 ?
Math.sqrt（）委托调用StrictMath.sqrt，这是在硬件或本机代码中完成的。

3. What is the complexity of these algorithms?
您描述的每个function的复杂性

i=2 .. i*i O（sqrt（n））

i=2 .. sqrt(n) O（sqrt（n）* log（n））

i=2 .. sqrt (by Newton's method) O（sqrt（n））+ O（log（n））

i=2 .. sqrt (by Math.sqrt) O（sqrt（n））

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

Answer 2

平方数实际上是整数运算，而sqrt是浮点数。 认识到投射和计算的运行时分配您观察到的结果并不令人惊讶。

sqrt http://en.wikipedia.org/wiki/Square_root上的维基百科页面有一个很好的计算部分。

至于我相信的更快的方法，你可以调查（子）线性运行时操作n ^ 2。

关于运行时的注意事项，您可能会喜欢我编写的这段代码来演示在迭代期间对函数进行的系统调用的数量，您可能会发现它，或者类似于java中的类似函数，因为您考虑这种类型的东西。 gist.github.com/Krewn/1ea0c788ac7210efc475

编辑：这是整数sqrt的一个很好的解释。 运行时间http://www.codecodex.com/wiki/Calculate_an_integer_square_root

编辑：在64 nm core2上— — 计算平方根的速度有多慢（多少个周期）？

请尽可能在post中包含输出与您的问题相关，但以不同的方式接近素数，

 def getPrimes(n): primes = [2] # instantiates our list to a list of one element, 2 k = 3 while(len(primes) < n): # python uses the prefix function len(var) for lists dictionaries and strings k2 = 0 isprime=True #Vacuously true assumption that every number is prime unless while(primes[k2]**2<=k): # <> this is where you are substituting sqrt with sq <> # if(k%primes[k2]==0): isprime=False break k2+=1 if(isprime):primes.append(k) k+=2 return(primes) print (getPrimes(30))