Самый низкий общий множитель с двойными в C

Question

Я делаю задание для класса Coursera, которое просит меня вычислить наименьшее общее кратное из двух чисел, каждое из которых не больше 2 * 10 ^ 9. Я пишу это в C, и я запускаю свой код на тестовый набор с номерами 226553150 и 1023473145. Ответ 46374212988031350, но я получаю 46374212988031344, что на 6!

Я написал правильное решение в Python, которое использует тот же подход, что и тот, который я опубликовал ниже, но детали числовой точности, очевидно, позаботились обо мне. Я публикую это в SO, чтобы узнать кое-что о точности с плавающей точкой в ​​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

Ближайший номер к 46374212988031350 который может быть представлен double является 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, как показано в ответе Дэн Хайцзюнь.

Answer 2

Я сомневаюсь, почему вы используете 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;
}