4

X と Y の 2 つの unsigned long long があり、X < Y ですが、どちらも非常に大きい可能性があります。X / Y の小数点以下の最初の桁を計算したい。たとえば、X が 11 で Y が 14 の場合、11 / 14 は .785 になるので、結果は 7 になるはずです。

(X * 10) / Y は機能しますが、X * 10 がオーバーフローした場合に間違った結果が生成されます。double への変換は、正しい結果を計算するのに十分正確であると信じる理由があればうまくいきます。

これはCです。助けてくれてありがとう！

4

6 に答える 6

4

仮数部にすべての整数値を正確に表すのに十分なビットがない限り、浮動小数点キャストによる正確な結果を保証したくありません。たとえば、トンサイダー y=9223372036854775807 および x = (y div 10) - 1 = 922337203685477579 です。「div」は整数除算です。x/y は 0.09999999999999999981568563067746... ですが、double を使用すると >= 0.1 になります。これは、有効桁数の精度が 52 桁しかない double の結果です (y には 61 ビット、x には約 58 ビットが必要です)。

80 ビットまたは 128 ビットの FP 精度を使用できる場合があります。その場合、仮数が >=64 ビット (ULL は 64 ビットですよね?) になるため、正しい答えが得られ、数値を無損失で表すことができます。

概算 (整数演算または FP 演算のいずれかを使用) から始めてから、乗算を試行して、答えが 1 未満か 1 より大きいかを確認します。重要な洞察は、2 つの数量の差が最大 unsigned int の半分未満であることがわかっている限り、オーバーフローした可能性のある 2 つの int を比較できることです。この種の比較手法は、たとえば TCP シーケンス番号がオーバーフローした場合に必要です。

整数演算のみを使用したい場合は、以下の関数「fdd(x,y)」が機能します。結果を表示するために main() を含めました。

#include <iostream>
using namespace std;

typedef unsigned char ull; // change char to any integral type e.g. long long

const ull maxull=(ull)-1;
const ull halfull = maxull/2;
typedef unsigned long long asint;

// x = X mod (maxull+1), y= Y mod (maxull+1).  we only know x and y
// if we assume |X-Y|<halfull, then we return X<Y:
inline bool less_mod_near(ull x, ull y) {

    return (x<=halfull == y<=halfull) ? x<y : y>x;
}

// assuming x<y, return first decimal digit of 10x/y (return is in [0..9])
inline int fdd(ull x, ull y) { 
// assert(x<y);
 if (x<=maxull/10) return (10*x)/y; 
  // for speed, and to ensure that y>10 to avoid division by 0 later
 ull r=y/10;
 if (r*10==y) return x/r;
 ull ub=x/(r+1); // ub >= 10x div y (without overflow)
 ull x10=x*10; // allow overflow
 cout<<"ub="<<(asint)ub<<" x10="<<(asint)x10<<" r="<<(asint)r<<" ";
 return less_mod_near(x10,ub) ? ub-1 : ub; 
  // we already handled the 10 evenly divides y case
}

int pdd(ull x, ull y,ull mustbe)
{
    ull d=fdd(x,y);
    cout << (asint)x << '/' << (asint)y << " = ." << (asint)d << "...";
    if (d!=mustbe) cout << " (should be "<<(asint)mustbe<<")";
    cout<<endl;
//    assert(a==d);
}

int main() {
    pdd(0,1,0);
    pdd(1,2,5);
    pdd(11,101,1);
    pdd(10,101,0);
    pdd(49,69,7);
    pdd(50,69,7);
    pdd(48,69,6);
    pdd(160,200,8);
    pdd(161,200,8);
    pdd(159,200,7);
    pdd(254,255,9);
}

出力：

0/1 = .0...
1/2 = .5...
11/101 = .1...
10/101 = .0...
ub=7 x10=234 r=6 49/69 = .7...
ub=7 x10=244 r=6 50/69 = .7...
ub=6 x10=224 r=6 48/69 = .6...
160/200 = .8...
161/200 = .8...
159/200 = .7...
ub=9 x10=236 r=25 254/255 = .9...
于 2009-08-16T23:08:13.103 に答える
3

double への変換は、正しい結果を計算するのに十分正確であると信じる理由があればうまくいきます。

最初の桁だけが必要な場合は、確実に倍精度で十分です。

編集：コメントのwrang-wrangの反例は、私が間違っていることを証明しています。

于 2009-08-16T22:54:30.813 に答える
1

Double に変換すると、被除数と分母の両方で 64 のうち 12 ビットの精度が失われます。ほとんどの場合、正しい答えが得られますが、80 ビット浮動小数点形式を使用して保存されていない限り、丸めエラーが発生することがあります。 .

編集：眠すぎてエラーが表示されない限り、wrang-wrangの答えはうまくいくと思います。私は午前中に仕事を得て、顧客のサイトまで車で 6 時間かかりました。うぐ。夜。

編集：最後にもう1つ。x86 は 80 ビットの内部表現を使用します。いくつかのasm命令を投げたい場合は、int64からfloat80への変換を保証するオペコードがあると思います。これは、移植性はありませんが、純粋な C 実装よりもエレガントで確かに高速なソリューションです。

于 2009-08-17T00:52:24.437 に答える
0

X％Yは余りRを与えます

次に、RとYから回答の小数部分を計算できます

R / Y

1桁目を取得するには、整数除算を使用します。

(long)((long)10*R/Y)

これにより、数値が切り捨てられ、余分な小数が削除されます。

編集：

あなたの質問に一致するように（うるさくなりたい人のために）その

Y % X = R

と

R / X
于 2009-08-17T01:43:40.970 に答える
0

どうですか

x / ((y + 9) / 10)

y + 9 は、分母の商 y/10 を切り上げるためのものなので、全体の結果は切り捨てられます。

大きな x と y の場合、ほとんどの場合正しいはずですが、完璧ではありません。例の 11 / 14 に対して 5 が生成されます。

問題は、分割によって情報が失われることです。10 の乗算は既にオーバーフローしているため、より大きな数値データ型を使用しない限り、それを回避することはできません。

于 2009-08-17T11:28:43.707 に答える
-1

範囲の制限を受け入れる準備ができている場合は、すべて整数演算で行うことができます:-

(X * 10) / Y

あなたの例では：

(11 * 10) / 14

=> 110 / 14

=> 7

制限は、X の最大値を 10 分の 1 に減らしたことです。

于 2009-08-17T03:19:38.943 に答える