在C双打最小公倍数 [英] Lowest Common Multiple with doubles in C
问题描述
我做了，要求我计算出两个号码，其中任何一个没有大于的最小公倍数一类证书课程分配2 * 10 ^ 9我用C写这个，我跑在测试案例与数字226553150和1023473145.答案是46374212988031350，但我得到46374212988031344，这是关闭的6我的code！
我已经用Python写的一个正确的解决方案，基本上采用相同的方法，因为我已经贴在下面的人，但数字precision的细节显然是照顾有加。我张贴这因此要学会一些有关浮点precision在C，因为大多数我见过在互联网上的问题和有关SO LCM只处理整数。
下面是我的code，而我与 GCC哌-O2 -std = C11 lcm.c 编译：
的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆math.h中GT;双GCD（双一，双二）{
如果（二== 0）{
返回;
} 返回GCD（B，FMOD（A，B））;
}双LCM（双一，双二）{
返回（A * B）/ GCD（A，B）;
}诠释主（）{ 双A;
双B： scanf函数（％LF％LF，＆安培;一，和b）; 的printf（％0lf \\ n，LCM（A，B））; 返回0;
}
最近数 46374212988031350 可以重新通过双是 46374212988031352 （关闭的 2 ）。您可以使用最简单的计算测试。
的#include＆LT;＆stdio.h中GT;诠释主（）{ //的226553150和1023473145的GCD是5
双A = 226553150;
双B = 1023473145;
双C = B / 10; 双LCM =一* C; 的printf（LCM：％.0lf \\ n，LCM）; 返回0;
}
输出：
LCM：46374212988031352
您正在使事情变得更糟通过计算（A * B）/ GCD（A，B）。最近数 231871064940156750 ，（A * B），也可以重新$ P $由浮点数psented为 231871064940156736 。换句话说，你是通过计算（A * B）第一。
您还没有公布Python的code你用来做相同的计算。我猜测的Python是使用积分类型的数字。如果我使用：
A = 226553150;
B = 1023473145;
C = B / 5;LCM =一* C打印（LCM，LCM）
我得到的输出：
（'LCM：'46374212988031350）
不过，如果我使用浮点面值为 A 和 B ，我得到不同的结果：
A = 226553150.0;
B = 1023473145.0;
C = B / 5;LCM =一* C打印（LCM，％18.0lf％LCM）
输出：
（'LCM：'，'46374212988031352'）
总之，你的C程序和Python程序之间眼看着差异是由于使用浮点类型VS整型。如果你使用长或长长而不是双击，你应该得到的输出作为Python程序相同，如
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!
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.
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;
}
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;
}
Output:
lcm: 46374212988031352
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.
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)
I get the output:
('lcm:', 46374212988031350)
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)
Output:
('lcm:', ' 46374212988031352')
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屋！
