webdevqa.jp.net

標準C ++ライブラリでなぜint pow(int base、int exponent)ではないのですか?

私はただそれを見つけることができないに違いないと感じています。 c ++ pow関数がfloatとdouble以外の「power」関数を実装しない理由はありますか?

実装が簡単なことはわかっていますが、標準ライブラリにあるべき作業をしているように感じます。堅牢なべき乗関数(つまり、一貫した明示的な方法でオーバーフローを処理する)は、書くのは面白くありません。

104
Dan O

実際のところ、そうです。

C++ 11以降、pow(int, int)のテンプレート化された実装があります---さらに一般的な場合は、 http://en.cppreference.com/w/cpp/の(7)を参照してください。数値/数学/パワー

1
Dima Pasechnik

_C++11_の時点で、特別なケースが一連のべき関数(およびその他)に追加されました。 _C++11 [c.math] /11_は、すべての_float/double/long double_オーバーロードを一覧表示した後(私の強調、言い換え):

さらに、doubleパラメータに対応する引数の型がdoubleまたは整数型の場合、 doubleパラメータに対応するすべての引数は、実質的にdoubleにキャストされます。

したがって、基本的に、整数パラメーターは、操作を実行するためにdoubleにアップグレードされます。


_C++11_(質問が行われたとき)の前には、整数のオーバーロードは存在しませんでした。

私はCの作成者にも_C++_の作成者とも密接に関連付けられていなかったので(私はamかなり古い)、ANSI/ISOの一部でもありませんでした基準を作成した委員会、これは必然的に私の意見です。私はそれがinformed意見だと思いたいのですが、私の妻があなたに言うように(頻繁に、そして多くの励ましが必要なく)、私は前に間違っていました:-)

それが価値があるという理由で、推測が続きます。

I 疑わしい元のANSI以前のCにこの機能がなかった理由は、完全に不要だったためです。まず、整数のべき乗を行うための完全に良い方法がすでにありました(doubleを使用してから、単純に整数に変換し直し、変換前に整数のオーバーフローとアンダーフローをチェックします)。

第二に、覚えておく必要があるもう1つのことは、Cの本来の意図がsystemsプログラミング言語としてのものであり、その分野で浮動小数点が望ましいかどうかは疑問です。

最初の使用例の1つはUNIXのコーディングであったため、浮動小数点はほとんど役に立たなかったでしょう。 CのベースとなったBCPLも、パワーを使用しませんでした(メモリからは浮動小数点がまったくありませんでした)。

余談ですが、整数のべき乗演算子は、おそらくライブラリ呼び出しではなく、バイナリ演算子でした。 x = add (y, z)で2つの整数を追加するのではなく、_x = y + z_-ライブラリではなく言語固有の一部を追加します。

第三に、積分力の実装は比較的些細なことなので、言語の開発者がより有用なものを提供するために時間を有効に使うことはほぼ確実です(機会費用に関するコメントを参照)。

これは、元の_C++_にも関連します。元の実装は実質的にCコードを生成する単なるトランスレーターであったため、Cの属性の多くを引き継ぎました。元々の意図は、クラス付きのCであり、クラスに余分な数学を加えたものではありませんでした。

_C++11_の前に標準に追加されなかった理由については、標準設定機関が従うべき特定のガイドラインを持っていることを覚えておく必要があります。たとえば、ANSI Cは、既存のプラクティスを体系化するために特別にタスクが割り当てられ、新しい言語を作成するためにnotが割り当てられました。そうでなければ、彼らは夢中になり、私たちにエイダを与えたかもしれません:-)

その標準のその後の繰り返しにも特定のガイドラインがあり、根拠文書に記載されています(言語自体の根拠ではなく、委員会が特定の決定を行った理由に関する根拠)。

たとえば、_C99_根拠文書は、追加できるものを制限する_C89_の2つの指針を具体的に進めています。

  • 言語を小さくシンプルに保ちます。
  • 操作を行う方法を1つだけ提供します。

ガイドライン(必ずしもこれらのspecificである必要はありません)は、個々のワーキンググループに対して定められているため、_C++_委員会(および他のすべてのISOグループ)も制限しています。

さらに、標準化団体は、彼らが行うすべての意思決定に機会費用(意思決定を控えなければならないことを意味する経済用語)があることを認識しています。たとえば、10,000ドルのユーバーゲーミングマシンを購入する機会費用は、約6か月間、他の半分との誠実な関係(またはおそらくall関係)です。

Eric Gunnersonは、これを -100ポイントの説明 で説明します。これは、Microsoft製品に常に追加されるとは限らない理由です。考慮されるべきです。

言い換えれば、標準のパワーオペレータ(正直なところ、10分の半分のコーダーなら誰でも起動できる)またはマルチスレッドを標準に追加したいのではないでしょうか。私にとっては、後者を使用したいので、UNIXとWindowsでのさまざまな実装をいじる必要はありません。

標準ライブラリ(ハッシュ、btree、赤黒木、辞書、任意のマップなど)の何千ものコレクションも見たいのですが、理論的根拠は次のとおりです。

標準は、実装者とプログラマの間の条約です。

そして、標準化団体の実装者の数は、プログラマー(または少なくとも機会費用を理解していないプログラマー)の数をはるかに上回っています。これらすべてが追加された場合、次の標準_C++_は_C++215x_になり、おそらく300年後にコンパイラ開発者によって完全に実装されるでしょう。

とにかく、それはこの問題に関する私の(かなり膨大な)考えです。票数だけが質ではなく量に基づいて配布された場合、私はすぐに他の全員を水から吹き飛ばすでしょう。聞いてくれてありがとう :-)

57
paxdiablo

とにかく、固定幅の整数型の場合、可能な入力ペアのほぼすべてが型をオーバーフローします。可能な入力の大部分に有用な結果をもたらさない関数を標準化する使用法は何ですか?

関数を有効にするには、大きな整数型が必要になります。ほとんどの大きな整数ライブラリは関数を提供します。


編集:質問に対するコメントで、static_rttiは「ほとんどの入力がオーバーフローを引き起こしますか?expおよびdouble powについても同じです。文句を言う人はいません」と書いています。これは間違っています。

expは脇に置いておきましょう。それはポイントの横にあるからです(実際には私の場合はより強力になりますが)double pow(double x, double y)に注目してください。 (x、y)ペアのどの部分で、この関数は何か有用なことを行います(つまり、単にオーバーフローまたはアンダーフローではありません)?

実際には、powが意味をなす入力ペアのごく一部のみに焦点を当てます。これは、私のポイントを証明するのに十分であるためです。xが正で、| y |である場合<= 1の場合、powはオーバーフローもアンダーフローもしません。これは、すべての浮動小数点ペアのほぼ4分の1で構成されます(非NaN浮動小数点数の正確に半分は正であり、非NaN浮動小数点数の半分未満は1未満の大きさです)。明らかに、多くの他の入力ペアがあり、それらに対してpowは有用な結果を生成しますが、少なくとも1つであることを確認しました-すべての入力の4分の1。

次に、固定幅(つまり、非bignum)の整数べき関数を見てみましょう。どの部分の入力に対して、単にオーバーフローしないのですか?意味のある入力ペアの数を最大化するには、基数に符号を付け、指数に符号を付けないでください。基数と指数が両方ともnビット幅であると仮定します。意味のある入力の部分に簡単に境界を付けることができます。

  • 指数が0または1の場合、任意の底が意味を持ちます。
  • 指数が2以上の場合、2 ^(n/2)より大きい基数は意味のある結果を生成しません。

したがって、2 ^(2n)の入力ペアのうち、2 ^(n + 1)+ 2 ^(3n/2)未満は意味のある結果を生成します。最も一般的な使用法である32ビット整数を調べると、これは、入力ペアの1パーセントの1/1000のオーダが単純にオーバーフローしないことを意味します。

39
Stephen Canon

とにかくintですべての整数のべき乗を表す方法がないためです。

>>> print 2**-4
0.0625

それは実際に興味深い質問です。私が議論で見つけられなかった1つの議論は、引数の明らかな戻り値の単純な欠如です。仮想int pow_int(int, int)関数が失敗する方法を数えましょう。

  1. オーバーフロー
  2. 結果は未定義pow_int(0,0)
  3. 結果を表すことができませんpow_int(2,-1)

この機能には、少なくとも2つの障害モードがあります。整数はこれらの値を表すことができません。これらの場合の関数の動作は標準で定義する必要があり、プログラマは関数がこれらのケースを正確に処理する方法を認識する必要があります。

全体的に関数を除外することは、唯一の賢明なオプションのようです。プログラマは、代わりにすべてのエラーレポートを使用できる浮動小数点バージョンを使用できます。

9
phoku

簡潔な答え:

pow(x, n)nが自然数であるように特殊化すると、時間パフォーマンスに役立つことがよくあります。しかし、標準ライブラリの汎用pow()は、この目的には依然としてかなり機能します(驚くほど!)。標準Cライブラリにできるだけ少ないものを含めることが絶対に重要です。ポータブルで、可能な限り簡単に実装できます。一方、それはC++標準ライブラリまたはSTLに存在することをまったく止めません。これは、何らかの組み込みプラットフォームでの使用を計画している人はいないと確信しています。

さて、長い答えを。

pow(x, n)は、多くの場合、nを自然数に特化することにより、はるかに高速にできます。私が書いたほぼすべてのプログラムに対して、この関数の独自の実装を使用する必要がありました(しかし、Cで多くの数学プログラムを書いています)。特殊な操作はO(log(n))の時間で実行できますが、nが小さい場合は、単純な線形バージョンの方が高速になります。以下に両方の実装を示します。

_
    // Computes x^n, where n is a natural number.
    double pown(double x, unsigned n)
    {
        double y = 1;
        // n = 2*d + r. x^n = (x^2)^d * x^r.
        unsigned d = n >> 1;
        unsigned r = n & 1;
        double x_2_d = d == 0? 1 : pown(x*x, d);
        double x_r = r == 0? 1 : x;
        return x_2_d*x_r;
    }
    // The linear implementation.
    double pown_l(double x, unsigned n)
    {
        double y = 1;
        for (unsigned i = 0; i < n; i++)
            y *= x;
        return y;
    }
_

pow(double x, unsigned n)の結果はpow(double, double)とほぼ同じ倍数に収まるので、xと戻り値をdoubleとして残しました。)

(はい、pownは再帰的ですが、最大スタックサイズがlog_2(n)にほぼ等しく、nは整数であるため、スタックの分割は絶対に不可能です。nNoハードウェアにはそのような極端なメモリ制限がありますが、ハードウェアスタックが3から8の関数呼び出しの深さしかないいくつかの危険なPICを除きます。 )

性能に関しては、園芸品種pow(double, double)の能力に驚かれることでしょう。 xが反復数に等しく、nが10に等しい5歳のIBM Thinkpadで1億回の反復をテストしました。このシナリオでは、_pown_l_が勝ちました。 glibc pow()には12.0ユーザー秒、pownには7.4ユーザー秒、_pown_l_には6.5ユーザー秒しかかかりませんでした。だから、それはそれほど驚くことではありません。多かれ少なかれこれを期待していた。

次に、xを定数(2.5に設定)にし、nを0〜19億回ループしました。今回は、まったく予想外に、glibc powが勝ち、地滑りで! 2.0ユーザー秒しかかかりませんでした。私のpownは9.6秒かかり、_pown_l_は12.2秒かかりました。ここで何が起こったのですか?別のテストを行って調べました。

100万に等しいxでのみ上記と同じことをしました。今回は、pownが9.6秒で勝ちました。 _pown_l_は12.2秒かかり、glibc powは16.3秒かかりました。今、それは明らかです! glibc powは、xが低い場合は3つよりもパフォーマンスが高くなりますが、xが高い場合は最悪です。 xが高い場合、nが低い場合は_pown_l_が最高のパフォーマンスを発揮し、pownが高い場合はxは最高のパフォーマンスを発揮します。

そのため、3つの異なるアルゴリズムがあり、それぞれ適切な状況下で他のアルゴリズムよりも優れたパフォーマンスを発揮できます。したがって、最終的に、どちらを使用するかは、powをどのように使用するかによって異なりますが、適切なバージョンisを使用する価値があり、すべてのバージョンを使用するのは良いことです。実際、次のような関数を使用してアルゴリズムの選択を自動化することもできます。

_double pown_auto(double x, unsigned n, double x_expected, unsigned n_expected) {
    if (x_expected < x_threshold)
        return pow(x, n);
    if (n_expected < n_threshold)
        return pown_l(x, n);
    return pown(x, n);
}
_

_x_expected_および_n_expected_がコンパイル時に決定される定数であり、おそらく他のいくつかの注意事項がある限り、その価値のある最適化コンパイラーは_pown_auto_関数呼び出し全体を自動的に削除し、 3つのアルゴリズムの適切な選択。 (今、実際にseを試そうとする場合、おそらく少し試してみる必要があるでしょう。なぜなら、私はcompiling上に書いてあります;))

一方、glibc pow動作しますであり、glibcはすでに十分な大きさです。 C標準は、さまざまな組み込みデバイス(実際、どこでも組み込み開発者がglibcが既に大きすぎることに同意している)を含む、移植性があると想定されています。数学関数mightを使用するすべての代替アルゴリズムを含める必要があります。したがって、それがC標準に含まれていない理由です。

脚注:時間パフォーマンステストでは、私のシステム(archlinux)でglibcをコンパイルするために使用される可能性のあるものに匹敵する可能性が高い、比較的寛大な最適化フラグ(_-s -O2_)を関数に与えました。したがって、結果はおそらく公正です。より厳密なテストのために、私は自分でglibcをコンパイルする必要があり、eeeeallyそんなことをする気はありません。以前はGentooを使用していたので、タスクが自動化されたであっても、どれくらい時間がかかるか覚えています。結果は、私にとって十分な決定的(またはむしろ決定的でない)です。もちろん、自分でこれを行うことはできます。

ボーナスラウンド:pow(x, n)をすべての整数に特化したものは、正確な整数出力が必要な場合にinstrumentalです。 p ^ N要素を持つN次元配列にメモリを割り当てることを検討してください。 1つでもp ^ Nをオフにすると、ランダムに発生するセグメンテーションフォールトが発生する可能性があります。

7

C++が追加のオーバーロードを持たない1つの理由は、Cと互換性があることです。

C++ 98にはdouble pow(double, int)のような関数がありますが、これらはC99に含まれていないという引数とともにC++ 11で削除されました。

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2011/n3286.html#55

わずかに正確な結果を取得することは、わずかなdifferent結果を取得することも意味します。

6
Bo Persson

世界は常に進化しており、プログラミング言語も進化しています。 C 10進数TRの4番目の部分 ¹は、_<math.h>_にいくつかの関数を追加します。これらの機能の2つのファミリは、この質問に興味があるかもしれません。

  • pown関数。浮動小数点数と_intmax_t_指数を受け取ります。
  • powr関数。2つの浮動小数点数(xy)を取り、式でxのべき乗yを計算します。 exp(y*log(x))

結局、標準的な人たちはこれらの機能が標準ライブラリに統合するのに十分有用であると考えたようです。ただし、合理的なのは、これらの関数が ISO/IEC/IEEE 60559:2011 で推奨されていることです。浮動小数点数。 C89の時点でどの「標準」が守られていたかは確かに言えませんが、_<math.h>_の将来の進化は、おそらくISOの将来の進化の影響を大きく受けるでしょう。/IEC/IEEE 60559標準。

10進数のTRの4番目の部分はC2x(次​​のメジャーCリビジョン)には含まれず、おそらくオプション機能として後で含まれることに注意してください。 TRのこの部分を将来のC++リビジョンに含めることを知っている意図はありませんでした。


¹いくつかの作業中のドキュメントを見つけることができます こちら

3
Morwenn

おそらく、プロセッサのALUがそのような整数用の関数を実装していなかったために、そのようなFPU命令が存在するためです(Stephenが指摘するように、実際にはペアです)。したがって、整数演算を使用して実装するよりも、実際にはdoubleにキャストし、powをdoubleで呼び出し、オーバーフローをテストしてキャストバックする方が高速でした。

(1つには、対数は乗算のパワーを減らしますが、整数の対数はほとんどの入力で多くの精度を失います)

スティーブンは、最新のプロセッサではこれはもはや真実ではないことは正しいですが、数学関数が選択されたときのC標準(C++はC関数を使用しただけです)は今、20歳ですか?

2
Ben Voigt