13

それで私は就職の面接に行って、彼らは私に簡単な数学的能力の方法をホワイトボードに書き出すように頼んだ.

public static double pow(double base, double power) {
    double result = 1.0;
    for(double x = 0; x < power; x++) {
        result = result * base;
    }

    return result;
}

これは機能し、彼らはそれに満足していましたが、それをより効率的にするにはどうすればよいかを私に尋ねましたが、私は応答しませんでした. だから私の質問は、これよりも効率的になることができますか、それとも私を少し汗ばませるための質問でしたか? 直接ビットシフトの解決策があるかもしれないと考えていますが、正確にはわかりません.2の累乗にしか適用できないと思いますか? 何か案は?

*編集 申し訳ありませんが、メソッド署名が私に与えられたことを忘れていました(入力としてのダブル)、組み込みの数学ライブラリを使用できないと言われました。

4

3 に答える 3

20

http://en.wikipedia.org/wiki/Exponentiation_by_squaringこの O(n) アルゴリズムとは対照的に、「基本的な方法」は O(log n) です。( Guavaには非再帰的な実装があります。)

また、電力パラメータはほぼ確実にint. (実際に数値を非整数累乗するアルゴリズムを実装したい場合は、さらに多くの計算が必要になります。)

于 2013-04-23T23:38:40.713 に答える