Функция 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 не может работать правильно. Любая идея, что вызывает это?


c++ math.h primes prime-factoring
person Byzantian    schedule 11.03.2013    source источник
comment
Никогда не сравнивайте double с int.   -  person Hans Passant    schedule 12.03.2013
comment
@Hans Passant Я впервые слышу что-то подобное. В чем проблема? Разве компилятор не должен предупреждать меня о таких вещах?   -  person Byzantian    schedule 12.03.2013
comment
@cyberpunk_ floating-point-gui.de   -  person Anirudh Ramanathan    schedule 12.03.2013
comment
@HansPassant, никогда не говори никогда. Это нормально, если двойник был назначен из целого числа. Однако в данном случае это было не так.   -  person Mark Ransom    schedule 12.03.2013

Ответы (2)


arrow_upward
3
arrow_downward

Проблема в том, что 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).

person Community    schedule 11.03.2013
comment
Пока имеет смысл. Но почему моя реализация, которая STILL возвращает double, похоже, работает? - person Byzantian; 12.03.2013
comment
@cyberpunk_, ваша версия работает, потому что все двойные числа, которые вы обрабатываете, были преобразованы из целых чисел. Математическая библиотечная функция pow использует более быструю математику, но требует реальных операций с плавающей запятой, которые немного теряют в точности. - person Mark Ransom; 12.03.2013
comment
Одним из способов реализации pow(x,y) является exp(y * ln(x)) и как ln(), так и exp() могут вызывать ошибки округления. (Я уверен, что настоящий pow() не использует этот метод.) - person brian beuning; 12.03.2013
comment
Не пропало подчеркивание? - person Alexey Frunze; 12.03.2013
comment
@AlexeyFrunze Действительно есть. - person ; 12.03.2013
comment
Как насчет того, чтобы просто добавить 0,5 перед приведением к типу int? Это на самом деле округлило бы число с плавающей запятой до значения closes int, что, скорее всего, и имелось в виду pow под возвращаемым значением. - person notadam; 31.12.2015

arrow_upward
1
arrow_downward

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

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

person Ivaylo Strandjev    schedule 11.03.2013