Java: Производительность SQRT Расчеты

Question

У меня есть этот код:

package math; 

import java.io.IOException; 
import java.util.Scanner; 

public class Main 
{ 
    public static void main(String[] args) throws IOException 
    { 
     System.out.println("Hi, I will beat Java's Math.sqrt(double) method"); 
     System.out.println("Both ways of calculation will be done"); 
     System.out.println("I will time how long they took to calculate"); 
     System.out.println("Random doubles will be generated"); 
     System.out.println(); 
     System.out.println("Please give the number of sqrt-calculation will be done"); 
     int calcs = new Scanner(System.in).nextInt(); 
     boolean output = true; 
     if (calcs > 10000) 
     { 
      System.out.println("You're asking much calculations"); 
      System.out.println("Disabling output is recommend"); 
      System.out.println("Disable output? (y/n)"); 
      char a = (char) System.in.read(); 
      if (a == 'y') 
      { 
       output = false; 
      } 
     } 
     System.out.println("Press enter to start"); 
     System.in.read(); 
     test(calcs, output); 
     System.out.println(); 
     System.out.println("I was much faster I think"); 
     System.out.println("Now you can check my precision"); 
     System.out.println("Please give a complex double"); 
     double x = Double.parseDouble(new Scanner(System.in).next()); 
     System.out.println(); 
     System.out.println("Math.sqrt(" + x + ")   = " + Math.sqrt(x)); 
     System.out.println("SqrtCalculator.sqrt(" + x + ") = " + sqrt(x)); 
     System.out.println("------------------------"); 
     System.out.println("Now please make your conclusion"); 
     System.out.println("Thanks for trying"); 
    } 

    public static void test(int calculations, boolean output) 
    { 
     double factor = Math.random()/2; 
     // Math 
     long mathStart = System.currentTimeMillis(); 
     for (int i = 1; i <= calculations; i++) 
     { 
      double x = i * factor; 
      double result = Math.sqrt(x); 
      if (output) 
      { 
       System.out.println("Math.sqrt(" + x + ") = " + result); 
      } 
     } 
     long mathStop = System.currentTimeMillis(); 
     long mathTime = mathStop - mathStart; 
     // My Method 
     long myStart = System.currentTimeMillis(); 
     for (int i = 1; i <= calculations; i++) 
     { 
      double x = i * factor; 
      double result = sqrt(x); 
      if (output) 
      { 
       System.out.println("SqrtCalculater.sqrt(" + x + ") = " + result); 
      } 
     } 
     long myStop = System.currentTimeMillis(); 
     long myTime = myStop - myStart; 
     System.out.println(); 
     if (output) 
      System.out.println("---------------------------"); 
     System.out.println("Here are the results:"); 
     System.out.println("Math and SqrtCalculator did each " + calculations + " of the same sqrt-calculations"); 
     System.out.println(); 
     System.out.println("Math: " + mathTime + " milliseconds"); 
     System.out.println("I: " + myTime + " milliseconds"); 
    } 

    public final static double sqrt(double x) 
    { 
     double previous = 1; 
     double now = 0; 
     for (;;) 
     { 
      now = (x/previous + previous)/2; 
      if (previous == now) 
      { 
       return now; 
      } 
      previous = now; 
     } 
    } 
} 

Этот метод SQRT называется "heroon".
Если я запускаю свою программу и задаю 80000 вычислений, и я отключил вывод, Math.sqrt() намного быстрее, чем мой метод. Если я попрошу 80000 calcs и я включу вывод, мой метод будет намного быстрее.

Может кто-нибудь объяснить это?

Thanks

Извините за плохой английский.

Answer 1

Я не смог воспроизвести ваши результаты. Несколько раз пробовал использовать Eclipse Galileo и JDK 1.6.0.

Для 80000, выход отключен, я получил что-то вроде:

Math: 15 milliseconds 
I: 32 milliseconds 

малые времена, было бы лучше использовать System.nanoTime() или более взаимодействий.

Для 80000, включен выход:

Math: 3609 milliseconds 
I: 4906 milliseconds 

Так, вероятно, проблема заключается в том, что способ вывода обрабатывается (скроллинг, буферизация, ...)

Answer 2

Возможно, вы превысили фактическое время вычисления с выходным временем и столкнулись с случайностью буферизации. Профайлер покажет вам, что на самом деле потребляет время.

Answer 3

Метод Math.sqrt отклоняется до StrictMath.sqrt, который выполняется в аппаратном или собственном коде. (Посмотрите на источник JDK - вы увидите, что это собственный метод.) Это, безусловно, быстрее, чем все, что вы напишете. Возможно, вы даже используете тот же алгоритм, который вы закодировали. Это хорошо известно. Ваш метод - это просто метод Ньютона для вычисления квадратных корней. Известно since Babylon; Ньютон просто отнял его, используя исчисление. Квадратичная сходимость хороша.

Независимо от того, что вы сделали, маловероятно, что вы обнаружили что-то новое или заслуживающее внимания. Похоже, что что-то связанное с IO искусственно смещает результаты.

Answer 4

Престижность в попытке улучшить существующую реализацию; даже если вы терпите неудачу, вы можете много узнать об алгоритмах в этом процессе. Естественно, вам нужно протестировать свою альтернативу, используя этот микро-бенчмарк. К сожалению, есть многочисленные подводные камни. В частности, не смешивать нерелевантный код, например, тестирование и вывод, с вашими расчетами; сделать разогреть JVM в начале вашего теста. В этом article on bechmarking. Кроме того, при сравнении значений с плавающей запятой рассмотрите эти Guidelines for comparing floating point numbers.