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 の試行はしたくないので、ベンチマークなどを使用してプログラムを複雑にしたくありません。大きく変化します。たとえば、一度私が得た

Newton Iteration: 0.466200 ミリ秒 (8 回の繰り返し) Midpoint Method: 21.090700 ミリ秒 (330 回の繰り返し) Secant Method: 0.134500 ミリ秒 (11 回の繰り返し)

別の時間に、ニュートンの反復を取得しました: 0.550700 ミリ秒 (8 回の反復が行われました) 中間点法: 23.168400 ミリ秒 (330 回の反復が行われました) セカント法: 0.130400 ミリ秒 (11 回の反復が行われました)

今、私はニュートン反復を取得しています: 0.469500 ミリ秒 (8 回の反復が行われました) 中間点法: 22.437700 ミリ秒 (330 回の反復が行われました) セカント法: 0.189200 ミリ秒 (11 回の反復が行われました)

彼らは単にあまり近くにありません。これはなぜですか？私は毎回同じことをしていますが、実行するたびに1回しか実行していないため、Javaは最適化できない可能性があります。

では、どのように進めるのが最善でしょうか? 考えられる解決策がいくつかあります。

  • トライアルを1回だけ行う

    • 利点: 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 に答える