質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.23%

long long int型において小数点を含む比の数値比較ができません。

解決済

回答 5

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,393

apeirogon0813

score 68

 前提・実現したいこと

C言語においてある比 φ = (1 + √5) / 2 の値を用いて、標準入力から a + b φ (a, b は整数) の形の 2 つの数に対し,1つめの方が大きければ 1 を,2 つめの方が大きければ -1 を,どちらも等しければ 0 を標準出力に出力するプログラムを作成するにおいて、
各整数をlong long int型で絶対値は10^10以下で考えて良いという問題なのですが、
比の値が小数点を含んでおり、long long int型で計算を行うと正しい結果が出力されません。
この場合どのように数値を比較したら良いのでしょうか?

入力例      出力例
5 -3        -1
-3 2


3 -1                       1
-2 2


3 -2                       0
3 -2


1392 -1209            1
-2789 1375


34264 -18079        1
-40761 28289


 発生している問題・エラーメッセージ

long long int型において小数点を含む大きな値の数値比較ができない。

 該当のソースコード

#include<stdio.h>
#include<math.h>

struct golden {
  long long int a;
  long long int b;
};


int compare(struct golden x, struct golden y) {
  long long int s, t;

  s = (x.a + x.b * ( 1 + sqrt(5) )/2) * 10000000;
  t = y.a + y.b * ( 1 + sqrt(5) )/2 * 10000000;
  //printf("s=%lld t=%lld\n",s ,t);                                             

 if(s == t){ return 0; }
 if(s > t){ return 1;}
 else { return -1; }
}

int main(void) {
  struct golden x, y;
  int n;
  scanf("%lld %lld",&x.a, &x.b);
  scanf("%lld %lld",&y.a, &y.b);
  n = compare(x, y);
  printf("%d\n",n);
  return 0;
}

 試したこと

小数点を繰り上げようと10^nをかけて繰り上げて比較しようとしても大きい値の入力を得た時にオーバーフローしてしまいました。
またdouble型にキャストも考えましたがlong long int型より有効桁が少ないためできませんでした。

 補足情報(FW/ツールのバージョンなど)

ここにより詳細な情報を記載してください。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • ikadzuchi

    2018/10/18 22:48

    式変形をするとたぶんルートをとるために2乗が必要なのでオーバーフローすると思います。

    キャンセル

  • episteme

    2018/10/21 11:47

    で、long double や sqrtl() は使えないの? 高精度で演算するのが目的なんしょ?

    キャンセル

  • apeirogon0813

    2018/10/23 10:53 編集

    sqrtl()使うことによって高精度で演算できました!
    莫大な感謝でいっぱいです!!

    キャンセル

回答 5

checkベストアンサー

+2

精度を考慮して、極力浮動小数点の演算を排除して行う方法です。
又、浮動小数点演算を行う場合は、精度の範囲内の演算であるため、正しい結果が得られることが担保されます。こちらで、確認した限りでは、正しい結果が得られてます。必要であれば、実装したソースの提供も可能です。

X=a1+b1Φ
Y=a2+b2Φ
とします。(a1,b1は1件目の入力値、a2,b2は2件目の入力値、Φ=(1+sqrt(5))/2とします)
X-Yを計算し、その結果をZとすると
Z=0 ならX=Y
Z>0 ならX>Y
Z<0 ならX<Yとなります。

Z=a1+b1Φ-(a2+b2Φ)
=(a1-a2)+(b1-b2)Φ
となります。

a1-a2=A
b1-b2=Bとすると
Z=A+BΦ
となります。

ここで、BΦは、整数×無理数=無理数なので、
Z=0となる為には、A=0,B=0であることが唯一の解であり、これ以外は、Zは0になりません。
よって、上記以外の場合は、Z>0又はZ<0のケースです。
上記以外のケースは以下のようになります。
1)A>0かつB>0なら、Z>0になります。
2)A<0かつB<0なら、Z<0になります。
3)上記以外で、B=0の場合は、Z=Aとなり、A>0なら、Z>0になります。A<0ならZ<0になります。
4)上記以外で、A=0の場合は、Z=BΦとなり、B>0なら、Z>0になります。B<0ならZ<0になります。

ここまでは、整数の演算のみで判定が可能です。
以降は、AもBも0でない場合のケースです。

5)A>0かつB<0の場合、Aの絶対値をAabs、Bの絶対値をBabsとすると
Aabs<Babs*Φなら、Z<0となります。左記以外は、Z>0となります。

6)A<0かつB>0の場合、Aの絶対値をAabs、Bの絶対値をBabsとすると
Aabs<Babs*Φなら、Z>0となります。左記以外は、Z<0となります。

7)上記の5)6)の判定ですが、以下のようにします。
両辺を2倍した
2*Aabsと2*Babs*Φを比較しても同じなので、これを比較します。
右辺に注目すると、
2*Babs*Φ=2*Babs*(1+sqrt(5))/2=Babs(1+sqrt(5))=Babs+Babs*sqrt(5)となります。
両辺からBabsを引くと
2*Aabs-BabsとBabs*sqrt(5)を比較しても同じことになります。
W=2*Aabs-Babs
V=Babs*sqrt(5)
とするとWは整数型の演算のみで結果が取得できます。
正しい演算が誤差なく行われたとして
VはBabs*sqrt(5)の真の値の小数点以下を切り捨てた整数の値とします。
即ち、V<真の値<V+1となります。(sqrt(5)は無理数なので真の値は整数にはなりません)
W=<Vなら左辺<右辺となります。
上記以外は(W>Vのケース)左辺>右辺となります。

正しいVの算出は、以下のようになります。
long long int Babs;
long long int V;
V = Babs * sqrt(5);
sqrt(5)は、double型なので、有効桁数は10進数に換算して約15桁、少なく見積もって14桁となります。
http://www.cc.kyoto-su.ac.jp/~yamada/programming/float.html
sqrt(5)=2.23606797749979のうち、
2.2360679774997 までは信頼できる数値です。Babsの最大値ですが10^10以下なので,10^10倍としても
22360679774.9979 の数値となり整数部は信頼できる範囲の数値です。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/10/21 00:24 編集

    上記のように実装してみたのですが
    以下の入力に対する出力が誤っていました。
    コードが合っているか確認していただきたいです。
    ====================入力====================
    51630685 -25993565
    -113949456 76340590
    =================================================
    ====================出力====================
    1←これが−1になってしまった
    =================================================

    long long int A, B, Aabs, Babs, V, W;
    double q;

    q = ( 1 + sqrt(5))/2;
    //printf("%f\n",q);
    A = x.a - y.a;
    B = x.b - y.b;
    Aabs = abs(A);
    Babs = abs(B);
    V = Babs * sqrt(5);
    W = 2 * Aabs - Babs;

    if(A == 0 && B == 0) { return 0; } // 0 )

    if(A > 0 && B > 0) { return 1; } // 1 )
    if(A < 0 && B < 0) { return -1; } // 2 )

    if(B == 0) { // 3 )
    if(A > 0) { return 1; }
    else { return -1; } //A=0なら前の条件でreturnされているためelse
    }
    if(A == 0) { // 4 )
    if(B > 0) {return 1; }
    else { return -1; }
    }

    if(A > 0 && B < 0) { // 5 )
    if(W <= V) { return -1;}
    else { return 1; }
    }
    if(A < 0 && B > 0) { // 6 )
    if(W <= V) { return 1;}
    else { return -1; }
    }

    キャンセル

  • 2018/10/21 09:26

    コードの内容はあっています。
    absはllabsを使った方が良いですが、今回の件とは、無関係です。
    こちらでも、確認してみました。
    結果が-1になっています。
    途中経過を確認すると、
    V = Babs * sqrt(5);で
    V=228826127 となっています。
    正確には、
    2288261269.9999999125973932163773447315
    の値が、途中でまるめられ、
    double型の状態で、228826127.00000 となっています。
    そのため、long long int型のVに設定した値は
    228826127 となっています。
    本来なら
    V=228826126となるべきですが、そのようになっていませんでした。
    double型を使用し、整数倍した場合、整数部分は正しいはずと書きましたが、間違っていました。
    お詫びして訂正します。
    従って、この方法では解決できません。
    他に解決する案として、
    GNPで提供されている多倍長整数ライブラリを使用する方法がありますが、
    https://sehermitage.web.fc2.com/etc/gmp.html
    そのようなものの使用は可能なのでしょうか。
    (課題の制約事項として、double型とlong long int型のみ使用可能なのですか)
    (linuxでなら使用可能です。gccは64ビット対応が望ましい)
    もし、使用可能なら、それを使用した解決案が提供可能です。
    (こちらでは既に実装し、確認済みです)

    キャンセル

  • 2018/10/21 11:04

    連投です。
    GNPで提供されている多倍長整数ライブラリを利用すると、無制限の桁数の整数が扱えます。
    但し、1点、利用する場合の注意点として、
    long int型が設定値及び取得値の型となっています。
    long int型が32ビットのGCCでは、4バイト整数(int型)と同じ
    long int型が64ビットのGCCでは、8バイト整数(long long int型)と同じ
    と同じです。
    ちなみに、long long int型はどちらの環境でも8バイト整数となります。
    あなたの環境はどちらでしょうか。
    printf("long int size=%d\n",sizeof(long int));
    を実行して、8が表示されれば64ビット環境、4が表示されれば32ビット環境です。
    32ビット環境で、long long int型の値を多倍長整数ライブラリに設定する場合、一旦、文字列にしてから、その文字列を、設定しなければいけません。
    64ビット環境なら、直接、long long int型の値を多倍長整数ライブラリに設定可能です。

    キャンセル

  • 2018/10/21 14:08

    なるほど大きい整数とdouble型の掛け算だと丸められてしまうのですね。
    おっしゃるとおり、課題ではdouble型とlong long int型のしていです。
    学校のOSはCent OSとlinuxのubuntuがありますがターミナルで提出する感じなのでよくわかりません。
    gccは64bit環境でした。
    ここまできたら課題関係なしに正しい出力を得たいのでよければご教示願います。

    キャンセル

+2

こういう分野は苦手な問題ですが、回答依頼いただいたので頑張ってみました。
(効率とか知りません)

ご提示のコードでできない原因は、stlong long int
小数部が無視されるからですね。
(既に気づいていらっしゃる通りです。)

で、計算部分ですが、素直にそのまま計算しました。
(一応オーバーフロー対策で式変形して乗算を使わないようにしましたが。)
ただし、計算結果を整数部と小数部に分けてそれぞれ変数に保存し、

long long int s_int = ...
double s_dec = ...
long long int t_int = ...
double t_dec = ...

最後にそれらを比較することで提示された例通りの出力を出せました。

コード載せちゃうと一応動く答えを載せることになっちゃうので、
とりあえずこういうことしましたよっていう回答にしておきます。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/10/19 22:03

    「以下のように」とありますが、どこのことでしょうか?

    キャンセル

  • 2018/10/20 19:15

    申し訳ないです添付し忘れていました。
    //少数部がマイナスだと結果に支障をきたすためその分両方に足して正にする
    if(s_dec < t_dec) {//2つの少数部のうち小さい方を両方に足せば良い

    if(s_dec < 0.) { //小さい方で、かつ足すのは影響が出る負の場合
    t_dec += fabs(s_dec);
    s_dec += fabs(s_dec);

    if(t_dec >= 1.) {//負の小数点の絶対値を足したことによって(少数部>1.)となった時、繰り上げ
    t_int++;
    t_dec -= 1;
    }
    }
    } else if(t_dec < 0.) { //同様
    s_dec += fabs(t_dec);
    t_dec += fabs(t_dec);

    if(s_dec >= 1.) {//繰り上げ
    s_int++;
    s_dec -= 1;
    }
    }

    キャンセル

  • 2018/10/22 11:38

    貼っていただいたコードを試しましたが、整数部への切り上げは行われているようです。
    無理数の計算なので、おそらく誤差で0.999999...となっているのかもしれません。

    ちなみに、マイナスのintによる切り捨てが+方向に付与するのであれば、
    「マイナスの時は-1して(int)で切り捨て」すれば良いという案だったのですが、
    よくよく考えればfloorで事足りる気がします。

    キャンセル

+1

小数点を繰り上げようと10^nをかけて繰り上げて比較しようとしても大きい値の入力を得た時にオーバーフローしてしまいました

とありますが、問題が

絶対値は10^10以下で考えて良い

で、long long は最大が 9*10^18 なので 数桁の下駄を履かせるくらいは問題ないように思えます。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/10/18 22:52

    10桁の数値と比較するには10桁の下駄が必要で、オーバーフローするのでそれができないという問題なのではありませんか?

    キャンセル

  • 2018/10/18 23:50

    こういう場合、φにも有効桁数10桁必要なんでしたっけ?
    久しく考えていなかったので、てっきり小数点4,5桁もあれば十分かと思ってました(汗)

    キャンセル

  • 2018/10/19 02:34

    すみませんtの式のカッコ書き忘れていました。ソースはしっかり書いてますが正しく出力されませんでした。

    キャンセル

0

>ここまできたら課題関係なしに正しい出力を得たいのでよければご教示願います。
GNPのMPライブラリを使う方法です。
問題は、V = Babs * sqrt(5);で正しい結果が得られないので、この箇所をGNP のMPで対応します。
5の平方根は、
https://keisan.casio.jp/exec/system/1260402326
で取得します。
2.23606797749978969640917366873
なので、10^29倍すると
223606797749978969640917366873
になります。
Babs*223606797749978969640917366873 を行い
その結果を10^29でわります。
これで正しいVが得られます。
ソースでは、
V = mult_by_sqrt5(Babs);
で、mult_by_sqrt5の関数を追加し、Babsに223606797749978969640917366873を掛けて、
その積を10^29で割り、その商を返します。
ソース使用時は、"gmp.h"をincludeします。
使い方は
https://sehermitage.web.fc2.com/etc/gmp.html
を参考にして作りました。

リンクするときは -lgmp を指定します。
ソース名がsample.cの場合
gcc -o sample sample.c -lgmp
のようにします。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include "gmp.h"
struct golden {
    long long int a;
    long long int b;
};

long long int mult_by_sqrt5(long long int x){
    // sqrt(5)の値は下記のサイトで取得
    // https://keisan.casio.jp/exec/system/1260402326
    // sqrt(5) = 2.23606797749978969640917366873
    char str_sq5[] = "223606797749978969640917366873";
    char str_10_29[]="100000000000000000000000000000";
    mpz_t mp_a,mp_b,mp_c,mp_x,mp_sq5,mp_10_29;
    long long int ans;
    mpz_init(mp_a);
    mpz_init(mp_b);
    mpz_init(mp_c);
    mpz_init(mp_x);
    mpz_init(mp_sq5);
    mpz_init(mp_10_29);
    mpz_init_set_str(mp_sq5,str_sq5,10);
    mpz_init_set_str(mp_10_29,str_10_29,10);
    mpz_set_si(mp_x,x);
    mpz_mul(mp_a,mp_x,mp_sq5);
    mpz_tdiv_q(mp_b,mp_a,mp_10_29);
    ans = mpz_get_si(mp_b);
    printf("\nmp_a=");
    mpz_out_str(stdout, 10, mp_a);
    printf("\nmp_b=");
    mpz_out_str(stdout, 10, mp_b);
    printf("\nans=%lld\n",ans);
    mpz_clear(mp_a);
    mpz_clear(mp_b);
    mpz_clear(mp_c);
    mpz_clear(mp_x);
    mpz_clear(mp_sq5);
    mpz_clear(mp_10_29);
    return ans;
}
int compare(struct golden x, struct golden y) {
    //戻り値の定義
    // x > y の時:1
    // x < y の時:-1
    // x = y の時:0
    long long int A, B, Aabs, Babs, V, W;
    double q;

    q = ( 1 + sqrt(5))/2;
    //printf("%f\n",q);
    A = x.a - y.a;
    B = x.b - y.b;
    Aabs = llabs(A);
    Babs = llabs(B);
    V = Babs * sqrt(5);
    printf("native V=%lld\n",V);
    V = mult_by_sqrt5(Babs);
    printf("GMP V=%lld\n",V);

    W = 2 * Aabs - Babs;

    if(A == 0 && B == 0) { return 0; }// 0 )

    if(A > 0 && B > 0) { return 1; } // 1 )
    if(A < 0 && B < 0) { return -1; } // 2 )

    if(B == 0) { // 3 )
    if(A > 0) { return 1; }
    else { return -1; } //A=0なら前の条件でreturnされているためelse
    }
    if(A == 0) { // 4 )
    if(B > 0) {return 1; }
    else { return -1; }
    }

    if(A > 0 && B < 0) { // 5 )
    if(W <= V) { return -1;}
    else { return 1; }
    }
    if(A < 0 && B > 0) { // 6 )
    if(W <= V) { return 1;}
    else { return -1; }
    }
}

int main(void) {
    struct golden x, y;
    int n;
    scanf("%lld %lld",&x.a, &x.b);
    scanf("%lld %lld",&y.a, &y.b);
    printf("x.a=%lld x.b=%lld y.a=%lld y.b=%lld\n",x.a,x.b,y.a,y.b);
    n = compare(x, y);
    printf("%d\n",n);
    return 0;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

-3

まず、PCが扱う浮動小数点数というのは2進数の数値となります
そして、あなたが扱う数値は10進数の数値となります
その10進数と2進数の数値の違いが、いわゆる誤差、となり、あなたのいう正しく出力されない結果となってしまいます

ということで、そこらへん調べてみましょう

#あなたのいう0.1は、浮動小数点数では表現できません

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.23%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる