最低共同倍数在C中加倍 [英] Lowest Common Multiple with doubles in C

问题描述

我正在为一个Coursera类做一个任务，要求我计算两个数字的最低公倍数，其中任一个不大于2 * 10 ^ 9。我正在C中写这个，我正在运行我的代码在一个测试用例226553150和1023473145.答案是46374212988031350，但我得到46374212988031344，这是关闭6！

I am doing an assignment for a Coursera class that asks me to calculate the Lowest Common Multiple of two numbers, either of which are no larger than 2 * 10 ^ 9. I'm writing this in C and I'm running my code on a test case with the numbers 226553150 and 1023473145. The answer is 46374212988031350, but I'm getting 46374212988031344, which is off by 6!

我已经写Python中正确的解决方案使用了与我下面发布的方法基本相同的方法，但是数字精度的细节显然是对我的照顾。我发布这个到了解C中的浮点精度的一些事情，因为我在互联网上看到的大多数问题和关于LCM的SO只处理整数。

I've written a correct solution in Python that uses essentially the same approach as the one I've posted below, but the details of numeric precision are obviously taken care of for me. I post this to SO to learn something about floating point precision in C, and because most of the questions I've seen on the internet and SO regarding LCM deal only with integers.

这是我的代码，我正在使用编译gcc -pipe -O2 -std = c11 lcm.c ：

Here is my code, which I'm compiling with 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;
}

推荐答案

最接近 46374212988031350 可以由双重表示是 46374212988031352 （关闭 2 ）。您可以使用最直接的计算来测试。

The closest number to 46374212988031350 that can be represented by a double is 46374212988031352 (off by 2). You can test that by using the most straight forward calculation.

#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

code>（a * b）/ gcd（a，b）。可以由浮点数表示的最接近的数字 231871064940156750 ，（a * b） 231871064940156736 。换句话说，您首先通过计算（a * b）而失去更多的准确性。

You are making things worse by computing (a * b)/gcd(a, b). The closest number to 231871064940156750, (a*b), that can be represented by floating point numbers is 231871064940156736. In other words, you are losing more accuracy by computing (a*b) first.

您没有发布你用来做同样计算的Python代码。我猜Python是使用整​​数类型的数字。如果我使用：

You haven't posted the Python code you used to do the same computation. I am guessing Python is using integral types for the numbers. If I use:

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

lcm = a*c

print("lcm:", lcm)

我得到输出：

('lcm:', 46374212988031350)

但是，如果我使用浮点文字 a code> b ，我得到一个不同的输出：

However, if I use floating point literals for a and b, I get a different output:

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程序相同的输出，如邓海军的答案所示。

In summary, the difference you are seeing between the C program and the Python program is due to use of floating point types vs integral types. If you use long or long long instead of double, you should get the same output as the Python program, as shown in the answer by Deng Haijun.

这篇关于最低共同倍数在C中加倍的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！