最低の共通倍数がCで倍精度になる

Question

2つの数値のうち、最小公倍数が2 * 10^9以下のものを計算するよう求めているCourseraクラスの割り当てを行っています。これを書いていますCでは226553150と1023473145のテストケースでコードを実行しています。答えは46374212988031350ですが、私は46374212988031344を取得していますが、これは6で終了しています！

私は、以下に投稿したのと本質的に同じアプローチを使用するPythonで正しい解決法を書いていますが、数値精度の詳細は明らかに私のために扱われています。私はCに浮動小数点精度について何かを学ぶためにSOにこれを投稿します。そして、LCMに関して私がインターネットやSOで見た質問のほとんどが整数だけを扱うからです。ここで

は私がgcc -pipe -O2 -std=c11 lcm.cしてコンパイルしてる私のコードです：

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

double gcd(double a, double b) { 
    if (b == 0) { 
     return a; 
    } 

    return gcd(b, fmod(a,b)); 
} 

double lcm(double a, double b) { 
    return (a * b)/gcd(a,b); 
} 

int main() { 

    double a; 
    double b; 

    scanf("%lf %lf", &a, &b); 

    printf("%.0lf\n", lcm(a,b)); 

    return 0; 
} 

Answer 1

doubleで表すことができる46374212988031350に最も近い数（2によってオフ）46374212988031352あります。最も単純な計算を使用して、それをテストすることができます。

#include <stdio.h> 

int main() { 

    // The gcd of 226553150 and 1023473145 is 5 
    double a = 226553150; 
    double b = 1023473145; 
    double c = b/5; 

    double lcm = a*c; 

    printf("lcm: %.0lf\n", lcm); 

    return 0; 
} 

出力：

lcm: 46374212988031352 

あなたは(a * b)/gcd(a, b)を計算することによって事態を悪化作っています。浮動小数点数で表すことができる231871064940156750、(a*b)に最も近い数値は231871064940156736です。言い換えれば、最初に(a*b)を計算することによって、より正確さが失われています。

あなたは同じ計算をしていたPythonコードを投稿していません。私はPythonが整数型を使用していると推測しています。私が使用している場合：

a = 226553150; 
b = 1023473145; 
c = b/5; 

lcm = a*c 

print("lcm:", lcm) 

私は出力を得る：

('lcm:', 46374212988031350) 

私はaとbのための浮動小数点リテラルを使用する場合は、私は別の出力を得る：

a = 226553150.0; 
b = 1023473145.0; 
c = b/5; 

lcm = a*c 

print("lcm:", "%18.0lf" % lcm) 

出力：

('lcm:', ' 46374212988031352') 

要約すると、CプログラムとPythonプログラムの間に見られる違いは、浮動小数点型と整数型の使用によるものです。 doubleの代わりにlongまたはlong longを使用する場合は、​​に示すように、Pythonプログラムと同じ出力を得る必要があります。

Answer 2

あなたがいない長いフロートを使用する理由私は疑います。私は次のように浮動小数点を長く変更し、うまく動作します。

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

long gcd(long a, long b) { 
    if (b == 0) { 
     return a; 
    } 

    return gcd(b, a%b); 
} 

long lcm(long a, long b) { 
    return (a * b)/gcd(a,b); 
} 

int main() { 

    long a; 
    long b; 

    scanf("%ld %ld", &a, &b); 
    printf("%ld\n", lcm(a,b)); 

    return 0; 
}