2

どちらも 2 * 10 ^ 9 を超えない 2 つの数値の最小公倍数を計算するように求められる Coursera クラスの割り当てを行っています。これを C で作成し、コードを実行しています。数字 226553150 と 1023473145 のテスト ケース。答えは 46374212988031350 ですが、46374212988031344 が得られ、6 ずれています!

以下に投稿したものと本質的に同じアプローチを使用する正しいソリューションをPythonで作成しましたが、数値精度の詳細は明らかに私のために処理されます。これを SO に投稿して、C の浮動小数点精度について学習します。インターネットで見た質問のほとんどと、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;
}
4

2 に答える 2

3

46374212988031350で表すことができるそれに最も近い数doubleは46374212988031352(off by 2) です。最も単純な計算を使用して、それをテストできます。

#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 プログラムの違いは、浮動小数点型と整数型の使用によるものです。の代わりにlongorを使用すると、Deng Haijun による回答に示されているように、Python プログラムと同じ出力が得られるはずです。long longdouble

于 2016-04-11T05:41:18.103 に答える
1

float を長く使用しない理由は疑問です。次のように float を long に変更すると、正常に動作します。

#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;
}
于 2016-04-11T05:24:48.247 に答える