Почему в for'е именно sqrt(n) + 0.00001?

Question

#include <stdio.h>
#include <math.h>

int main()
{
    int n;
    system("chcp 1251");
    printf("Введите целое число\t");
    scanf_s("%d", &n);

    for (int i = 2; i < sqrt(n) + 0.00001; ) {
        if (n % i == 0) {
            printf("%d ", i);
            n /= i;
        }
        else {
            ++i;
        }
    }

    if (n > 1)
        printf("%d", n);
    getchar(); getchar();
    return 0;
}

Вот простой код на С, который выводит простые делители числа.

Пример: 2600 = 2*2*2*5*5*13. Так вот, почему в for'е написано именно sqrt(n) + 0.00001?

Arhadthedev · Accepted Answer · 2019-03-30T13:03:25.113

5

i < sqrt(n) + 0.00001 — это аналог i <= sqrt(n) с учётом неточностей при вычислений дробных чисел. Автор алгоритма решил (или просто взял с потолка), что эта неточность — промах счётчика мимо значения корня — будет не более одной стотысячной, оттуда и константа.

Если переводить на человеческий язык, условие буквально означает «останови цикл, когда значение i чуть-чуть превысит значение квадратного корня из n».

edited Mar 30 '19 at 13:03

answered Mar 29 '19 at 02:02

Arhadthedev

11,528

Но почему просто не i <= n? – Asmund Mar 29 '19 at 02:10
2

кстати, любопытно, что на большинстве платформ (с 32-битным int и IEEE754 double) этот пример будет работать корректно даже при сравнении с <= т.к. целые типы представляются без погрешности... само собой, я не рекомендую и не оправдываю использование таких тонких и зыбких механик где-либо... – Fat-Zer Mar 29 '19 at 02:15
@Asmund, связанный вопрос: https://ru.stackoverflow.com/questions/417453/%d0%92%d1%8b%d1%87%d0%b8%d1%81%d0%bb%d0%b5%d0%bd%d0%b8%d1%8f-%d0%bd%d0%b0-%d1%87%d0%b8%d1%81%d0%bb%d0%b0%d1%85-%d1%81-%d0%bf%d0%bb%d0%b0%d0%b2%d0%b0%d1%8e%d1%89%d0%b5%d0%b9-%d1%82%d0%be%d1%87%d0%ba%d0%be%d0%b9-%d0%bd%d0%b5-%d1%80%d0%b0%d0%b1%d0%be%d1%82%d0%b0%d1%8e%d1%82/417454#417454... и в данном случае правильно было бы избавиться от арифметики с плавающей точкой и использовать i*i <= n. – Fat-Zer Mar 29 '19 at 02:17
1

@Asmund Ошибка может накопиться как в меньшую сторону, так и в большую. i <= n не учтёт второй случай, из-за чего, к примеру, значение 4.0000015268 будет ошибочно пропущено при n = 16. – Arhadthedev Mar 29 '19 at 02:17
1

@Asmund ... или наоборот, квадратный корень выдаст значение меньше идеального, из-за чего последнее значение i опять же будет пропущено. Это целочисленная арифметика гарантирует неявное округление после каждой операции, которое сбрасывает неточности. При double же и float нам приходится самим учитывать наличие погрешности и её рост. – Arhadthedev Mar 29 '19 at 02:25
1

Если вопрос не конкретно про sqrt() + EPS, то никогда так не работайте с нецелочисленным типом данных. А с учетом тяжести операции sqrt() - это ужас. Вариант с целыми числами: i * i <= n. – Khetag Abramov Mar 29 '19 at 08:52
1

@Arhad "не более одной десятимиллионной" - стотысячной, если позанудствовать... – tum_ Mar 30 '19 at 07:34
1

@tum_, спасибо, исправил. – Arhadthedev Mar 30 '19 at 13:03

Почему в for'е именно sqrt(n) + 0.00001?

1 Answers1