C语言中双打的最小公倍数

Question

我正在为 Coursera class 做作业，要求我计算两个数字的最小公倍数，其中任何一个都不大于 2 * 10 ^ 9。我正在写这个C，我运行我在测试用例上的代码，编号为 226553150 和 1023473145。答案是 46374212988031350，但我得到的是 46374212988031344，相差 6！

我在 Python 中编写了一个正确的解决方案，它使用的方法与我在下面 post 编辑的方法基本相同，但数字精度的细节显然已得到处理我。我 post 这样做是为了学习一些关于 C 中浮点精度的知识，因为我在互联网上看到的大多数问题和 SO 关于 LCM 只处理整数。

这是我使用 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

我怀疑你为什么使用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;
}

Answer 2

可以用 double 表示的最接近 46374212988031350 的数字是 46374212988031352（被 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 程序之间看到的差异是由于使用浮点类型与整数类型。如果您使用 long 或 long long 而不是 double，您应该得到与 Python 程序相同的输出，如 .[=31= 所示]

C语言中双打的最小公倍数

Lowest Common Multiple with doubles in C

c

double

lcm