1

我写了一个程序来计时某些平方根算法

import java.math.BigDecimal;
public class ScienceFairTwo {
    public static final BigDecimal TWO = new BigDecimal(2);
    public static final BigDecimal SQRT_TWO = new BigDecimal("1.4142135623730950488016887242096980785696718753769480731766797379907324784621070388503875343276415727");
    public static final BigDecimal TOLERANCE = BigDecimal.ONE.scaleByPowerOfTen(-100);
    public static long[] NewtonMethod() {
        int iterations = 0; // so far, we haven't done any iterations
        BigDecimal a = BigDecimal.ONE; // set a to be one
        long start = System.nanoTime(); // start the timer
        while(a.subtract(SQRT_TWO).abs().compareTo(TOLERANCE) >= 0) { // while our decimal isn't close enough to the square root of two
            a = a.add(TWO.divide(a, 100, BigDecimal.ROUND_HALF_UP)).divide(TWO); // set a to (a + 2/a)/2
            iterations++; // add one to our iteration counter
        }
        return new long[] {System.nanoTime() - start, iterations}; // return the time taken and the iterations taken
    }
    public static long[] BhaskaraBrounckerAlgorithm() {
        int iterations = 0; // so far, we haven't done any iterations
        BigDecimal a = BigDecimal.ONE; // set a to be one
        long start = System.nanoTime(); // start the timer
        while(a.subtract(SQRT_TWO).abs().compareTo(TOLERANCE) >= 0) { // while our decimal isn't close enough to the square root of two
            a = a.add(TWO).divide(a.add(BigDecimal.ONE), 100, BigDecimal.ROUND_HALF_UP); // set a to (a+2)/(a+1)
            iterations++; // add one to our iteration counter
        }
        return new long[] {System.nanoTime() - start, iterations};  // return the time taken and the iterations taken
    }
    public static long[] MidpointMethod()
    {
        int iterations = 0; // so far, we haven't done any iterations
        BigDecimal a = BigDecimal.ONE; // set a to be one
        BigDecimal b = TWO; // set b to be two  
        long start = System.nanoTime(); // start the timer
        while(a.add(b).divide(TWO).subtract(SQRT_TWO).abs().compareTo(TOLERANCE) >= 0) { // while our decimals aren't close enough to the square root of two
            if(a.multiply(a).subtract(TWO).abs().compareTo(b.multiply(b).subtract(TWO).abs()) == 1)  // if a is farther from the square root of two than b
                a = a.add(b).divide(TWO); // set a to be the average of a and b
            else // if a is closer to the square root of two than b
                b = a.add(b).divide(TWO); // set b to be the average of a and b
            iterations++; // add one to our iteration counter
        }
        return new long[] {System.nanoTime() - start, iterations}; // return the time taken and the iterations taken
    }
    public static long[] SecantMethod()
    {
        BigDecimal a = BigDecimal.ONE; // set a to be one
        BigDecimal b = TWO; // set b to be two
        BigDecimal b_old = TWO; // set b_old to be two (this is a transferring variable)
        long start = System.nanoTime(); // start the timer
        int iterations = 0; // so far, we haven't done any iterations
        while(a.add(b).divide(TWO).subtract(SQRT_TWO).abs().compareTo(TOLERANCE) >= 0) { // // while our decimals aren't close enough to the square root of two
            b_old = b; // set b_old to be b
            b = a.multiply(b).add(TWO).divide(a.add(b), 100, BigDecimal.ROUND_HALF_UP); // set b to be (ab + 2)/(a+b)
            a = b_old; // set a to be the previous value of b
            iterations++; // add one to our iterations counter
        }
        return new long[] {System.nanoTime() - start, iterations}; // return the time taken and the iterations taken
    } 
    public static void main(String[] args) {
        System.out.printf("Newton Iteration: %f milliseconds (%d iterations taken)\n", NewtonMethod()[0] / 10e6, NewtonMethod()[1]); // print the results
        System.out.printf("Midpoint Method: %f milliseconds (%d iterations taken)\n", MidpointMethod()[0] / 10e6, MidpointMethod()[1]); // print the results
        System.out.printf("Secant Method: %f milliseconds (%d iterations taken)\n", SecantMethod()[0] / 10e6, SecantMethod()[1]); // print the results
        System.out.printf("Bhaskara-Brouncker Algorithm: %f milliseconds (%d iterations taken)\n", BhaskaraBrounckerAlgorithm()[0] / 10e6, BhaskaraBrounckerAlgorithm()[1]); // print the results
    }
}

我不想做 100/1000 次试验，因为我需要把这个程序放在科学展览板上，所以我不想通过使用基准测试等使程序复杂化。但是，当我这样做时，结果我变化很大。例如，一旦我得到

牛顿迭代：0.466200 毫秒（进行了 8 次迭代） 中点法：21.090700 毫秒（进行了 330 次迭代） 正割法：0.134500 毫秒（进行了 11 次迭代） Bhaskara-Brouncker 算法：1.315300 毫秒（进行了 132 次迭代）

另一次我得到牛顿迭代：0.550700 毫秒（进行了 8 次迭代）中点方法：23.168400 毫秒（进行了 330 次迭代）正割法：0.130400 毫秒（进行了 11 次迭代） Bhaskara-Brouncker 算法：1.078100 毫秒（进行了 132 次迭代）

现在我得到牛顿迭代：0.469500 毫秒（进行了 8 次迭代）中点方法：22.437700 毫秒（进行了 330 次迭代）正割法：0.189200 毫秒（进行了 11 次迭代） Bhaskara-Brouncker 算法：1.807600 毫秒（进行了 132 次迭代）

他们只是不是很接近。为什么会这样？我每次都在做同样的事情，而 java 不可能优化，因为我每次运行时只做一次。

那么最好的方法是什么？有几种可能的解决方案：

  • 只做一次试验

    • 优点：Java无法优化
    • 缺点：不是很一致（如上所示）

  • 做 1000 次试验

    • 优点：相当一致
    • 缺点：java会优化所以结果不准确

  • 进行 1000 次试验，但每次使用 rand 更改我们近似平方根的值

    • 优点：相当准确，无需优化
    • 缺点：由于随机性，每次答案都会有所不同

  • 做 969 次试验，但每次都做 2, 3, ..., 1000 的平方根（不包括 1,4,..,961）

    • 优点：相当准确，无需优化
    • 缺点：

我倾向于最后一个。这是一个好主意吗？

4

1 回答 1

0

你说的是0.1毫秒的差异。由于负载，相同的算法通常会在运行时间中波动这么多。在 0.1 毫秒时差异很小，如果你想确保避免“优化”，那么你应该用管理较少的语言编写程序，可能是 c 甚至汇编，但我见过的所有算法在运行时都会有这么小的波动跑步。

于 2013-12-01T00:18:06.773 回答