質問: compare(x, y); printf("%d\n",n); return 0; } ``` ### 試したこと 小数点を繰り上げようと10^nをかけて繰り上げて比較しようとしても大きい値の入力を得た時にオーバーフローしてしまいました。 またdouble型にキャストも考えましたがlong long int型より有効桁が少ないためできませんでした。 ### 補足情報(FW/ツールのバージョンなど) ここにより詳細な情報を記載してください。
回答: 精度を考慮して、極力浮動小数点の演算を排除して行う方法です。 又、浮動小数点演算を行う場合は、精度の範囲内の演算であるため、正しい結果が得られることが担保されます。こちらで、確認した限りでは、正しい結果が得られてます。必要であれば、実装したソースの提供も可能です。 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 ならX0又は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とすると Aabs0となります。 6)A<0かつB>0の場合、Aの絶対値をAabs、Bの絶対値をBabsとすると Aabs0となります。左記以外は、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のケース)左辺>右辺となります。 正しい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 の数値となり整数部は信頼できる範囲の数値です。