4

次のようなコードがあるとします。

float a, b = ...; // both positive
int s1 = ceil(sqrt(a/b));
int s2 = ceil(sqrt(a/b)) + 0.1;

それは可能ですs1 != s2か？私の関心事は、a/bが完全な正方形になるときです。たとえば、おそらくa=100.0とb=4.0の出力は であるceilはずです5.00000が、代わりに である場合は4.99999どうでしょうか?

同様の質問: と100.0/4.0評価されてから切り上げられる可能性は5.00001ありますか?ceil6.00000

私はこれを整数演算で行うことを好みsqrtますが、計画はちょっと失敗します。

編集:これをより適切に実装する方法に関する提案もいただければ幸いです! aとのb値は整数値なので、実際のコードは次のようになります。ceil(sqrt(float(a)/b))

編集: levis501の回答に基づいて、私はこれを行うと思います:

float a, b = ...; // both positive
int s = sqrt(a/b);
while (s*s*b < a) ++s;

皆さん、ありがとうございました！

4

5 に答える 5

6

それは不可能だと思います。の値に関係なく、sqrt(a/b)それが生成するのは、次のように使用する値Nです。

int s1 = ceil(N);
int s2 = ceil(N) + 0.1;

ceilは常に整数値を生成するため（doubleとして表されますが）、常に値Xがあり、最初の値が生成X.0され、2番目の値が生成されX.1ます。toに変換するintと、常にそれが切り捨てられる.1ため、両方とも。になりXます。

Xが大きすぎて、X.1がdoubleの範囲をオーバーフローした場合は、例外があるように見えるかもしれません。しかし、これがどこで可能かはわかりません。0に近い場合（オーバーフローが問題にならない場合）を除いて、数値の平方根は常に入力数値よりも小さくなります。したがって、ceil（N）+0.1がオーバーフローする前にa/b、入力として使用されているsqrt(a/b)ものはすでにオーバーフローしている必要があります。

于 2011-11-02T17:34:05.820 に答える
3

ケースに合わせて明示的な関数を書きたいと思うかもしれません。例えば：

/* return the smallest positive integer whose square is at least x */
int isqrt(double x) {
  int y1 = ceil(sqrt(x));
  int y2 = y1 - 1;
  if ((y2 * y2) >= x) return y2;
  return y1;
}

これは、比率の平方根がa/bの精度内にある奇妙なケースを処理しますdouble。

于 2011-11-02T17:42:54.847 に答える
1

浮動小数点数の同等性は確かに問題ですが、整数を扱う場合はそうではありません。

のケースがある場合は100.0/4.0、完全に と評価される必要25.0が25.0あり25.1ます。

于 2011-11-02T17:38:01.593 に答える
-1

はい、それは完全に可能ですs1 != s2。しかし、なぜそれが問題なのですか？それは十分に自然なようですs1 != (s1 + 0.1)。

5.00001ところで、の代わりに四捨五入したい場合は、5.00000の代わりにを6.00000使用してください。rintceil

そして、（コメント内の）実際の質問に答えるために-sqrt開始点を取得し、整数演算を使用して正しい正方形を見つけるために使用できます。

int min_dimension_greater_than(int items, int buckets)
{
    double target = double(items) / buckets;
    int min_square = ceil(target);
    int dim = floor(sqrt(target));
    int square = dim * dim;
    while (square < min_square) {
        seed += 1;
        square = dim * dim;
    }
    return dim;
}

はい、これは大幅に改善できます。これは簡単なスケッチです。

于 2011-11-02T17:33:25.123 に答える
-2

s1 は常に s2 と等しくなります。

C および C++ 標準では、数学ルーチンの精度についてはあまり言及されていません。C 標準は sqrt(x) が x の平方根を返すと言っていますが、2 の平方根は浮動小数点で正確に表すことができないため、文字どおりに解釈すると、標準を実装することは不可能です。

常に正しく丸められた結果を返すパフォーマンスの良いルーチンを実装する (最も近い値に丸めるモードでは、結果は正確な結果に最も近い表現可能な浮動小数点数であり、低いゼロ ビットを優先して同点が解決されることを意味します) ) は難しい研究問題です。優れた数学ライブラリは、1 ULP 未満の精度 (したがって、最も近い 2 つの表現可能な数値のうちの 1 つが返される) を目標としており、おそらく .5 ULP をわずかに超える程度です。(ULP は最小精度の単位であり、指数フィールドの特定の値に与えられた下位ビットの値です。) 一部の数学ライブラリは、これよりも大幅に悪い場合があります。詳細については、ベンダーに問い合わせるか、ドキュメントを確認する必要があります。

そのため、sqrt はわずかにずれている可能性があります。正確な平方根が整数 (整数が浮動小数点で正確に表現できる範囲内) であり、エラーが 1 ULP 未満であることをライブラリが保証する場合、sqrt の結果は正確でなければなりません。正確な結果は、少なくとも 1 ULP 離れています。

同様に、エラーが 1 ULP 未満であることをライブラリが保証する場合、正確な結果は表現可能であり、他の結果は少なくとも 1 ULP 離れているため、ceil は正確な結果を返す必要があります。さらに、ceil の性質は、ライブラリの残りの部分が高品質でなくても、適切な数学ライブラリは常に整数を返すと私が期待するようなものです。

オーバーフローの場合、ceil(x) がすべての整数を正確に表現できる範囲を超えていた場合、ceil(x)+.1 は他の表現可能な数値よりも ceil(x) に近いため、丸められた結果はceil(x) に .1 を追加すると、浮動小数点標準 (IEEE 754) を実装するシステムでは ceil(x) になります。これは、最も近い値に丸めるデフォルトの丸めモードであることが前提です。丸めモードを round-toward-infinity のようなものに変更すると、ceil(x)+.1 が ceil(x) より大きい整数になる可能性があります。

于 2011-11-04T17:01:27.713 に答える