Функция math.h pow () не работает правильно?

Я работал над личным проектом, в котором мне нужно было определить все главные силы между 0 и 999. Поскольку я не особенно хорош в математике, мне надоел следующий грубый подход.

bool constexpr is_prime(int imp)
{
return imp == 1 ? false : (imp % imp == 0 && imp % 1 == 0 && [&imp]{ for(int i = 2; i < imp; ++i)  if(imp % i == 0) return false; return true;}());
}

bool is_prime_power(int imp)
{
for(int i = 1; i < 1000; ++i)
if (is_prime(i))
for (int j = 0; j < 100; ++j)
if (imp == pow(i, j))
return true;
return false;
}

Для 0 … 30 вывод должен быть (согласно A000961):

1 2 3 4 5 7 8 9 11 13 16 17 19

Тем не менее, это то, что я получаю вместо этого:

1 2 3 4 5 7 8 9 11 16 19

Куда пропали 13 и 17?

Поскольку я не мог найти никаких логических проблем с моим подходом, я реализовал свою собственную функцию pow ().

double constexpr _pow(double base, double exp)
{
return exp == 0 ? 1 : base*pow(base, exp - 1);
}

Теперь, если я вызову мою версию _pow () вместо pow () из math.h, вывод отобразится как исключение. Моя реализация неверна? Если нет, pow () из math.h не может работать правильно.
Есть идеи, что вызывает это?

1

Решение

Проблема в том, что double (и числа с плавающей точкой в ​​целом) не являются точными, и математические функции в стандартной библиотеке также используют приближенные формулы для выполнения вычислений. Если вы позвоните pow(2, 10), вы можете получить 1023.999375Например, (который затем, в зависимости от контекста, может быть сокращен до 1023).

Таким образом, вместо использования с плавающей точкой pow() функция из стандартной библиотеки, вы можете пойти со своим, точный реализация для целых чисел:

int constexpr _pow(int base, int exp)
{
return exp == 0 ? 1 : base * _pow(base, exp - 1);
}

(или измените его на тот, который вам нужен, если вам нужно unsigned или же long long).

3

Другие решения

Вам никогда не нужно проверять, что число делится само по себе и что число делит число. Это бесполезно imp % imp == 0 && imp % 1 == 0

В противном случае ваша проблема в том, что pow возвращает double или float, а вы сравниваете его с целым числом. Сопоставление может быть неудачным из-за ошибки округления. Я бы посоветовал вам реализовать свою собственную операцию целочисленного питания, чтобы избежать ошибок округления. Также можно конвертировать i в double и использовать сравнение с небольшим допуском на эпсилон.

1

По вопросам рекламы [email protected]