Почему uint64_t не может правильно показать pow(2, 64) - 1?

Я пытаюсь понять, почему тип uint64_t не может правильно отображать pow(2,64)-1. Стандарт cplusplus — 199711L.

Я проверил функцию pow() по стандарту С++ 98, которая

double pow (double base     , double exponent);
float pow (float base      , float exponent);
long double pow (long double base, long double exponent);
double pow (double base     , int exponent);
long double pow (long double base, int exponent);

Поэтому я написал следующий фрагмент

double max1 = (pow(2, 64) - 1);
cout << max1 << endl;

uint64_t max2 = (pow(2, 64) - 1);
cout << max2 << endl;

uint64_t max3 = -1;
cout << max3 << endl;

Выходы:

max1: 1.84467e+019
max2: 9223372036854775808
max3: 18446744073709551615

c++ double floating-point uint64
person Diame    schedule 01.03.2019    source источник
comment
связанный: заголовок stackoverflow.com/questions/3793838/   -  person NathanOliver    schedule 01.03.2019
comment
Чтобы вычислить 2 ^ 64 - 1, 2 ^ 64 должно поместиться в регистре до вычитания 1. Конечно, результат помещается в uint64_t, но не в промежуточный результат.   -  person AlexG    schedule 01.03.2019
comment
@AlexG, спасибо. Я думал дело в этом. Однако это не может объяснить, почему double max1 = (pow(2, 64) - 1); показывает правильно.   -  person Diame    schedule 01.03.2019
comment
Вы уверены, что он использует целочисленную версию функции pow?   -  person AlexG    schedule 01.03.2019
comment
Следует отметить одну вещь: IEEE 754 (за которым обычно следует double) определяет 52 бита для мантиссы, что ограничивает точность double (в нормализованном режиме у вас есть на один неявный бит больше). , но все равно). Таким образом, вы никогда не сможете правильно представить 2^64-1 в двойном размере, но на самом деле страдаете от округления.   -  person Aconcagua    schedule 01.03.2019
comment
Я не могу скомпилировать это: godbolt.org/z/sz5atd   -  person Justin    schedule 01.03.2019
comment
@Diame double нет, но вы не проверяете неправильные цифры   -  person Caleth    schedule 01.03.2019
comment
@Justin, тебе не хватает #include <cmath> и (возможно) std:: с сайта вызова   -  person Caleth    schedule 01.03.2019
comment
@Caleth Нет, я объявил функции. Я мог бы переименовать его в foo(...). Я просто показывал, что указанный набор перегрузки не может скомпилироваться с данным выражением. Хотя, наверное, было бы разумнее сделать это именно так.   -  person Justin    schedule 01.03.2019
comment
uint64_t max2b = pow(2.0, 64.0) - 2048.0; будет ближе к тому, что вы хотите, поскольку 2048.0 - это эпсилон в этом диапазоне. (Предполагая IEEE 754.)   -  person Eljay    schedule 01.03.2019
comment
Обратите внимание, что 2^64-1 == uint64_t(-1).   -  person Max Langhof    schedule 01.03.2019

Ответы (2)


arrow_upward
5
arrow_downward

Числа с плавающей запятой имеют конечную точность.

В вашей системе (и, как правило, в двоичном формате IEEE-754) 18446744073709551615 не является числом, которое имеет представление в формате double. Ближайшим числом, которое имеет представление, является 18446744073709551616.

Вычитание (и сложение) вместе двух чисел с плавающей запятой, имеющих совершенно разные величины, обычно приводит к ошибке. Эта ошибка может быть существенной по отношению к меньшему операнду. В случае 18446744073709551616. - 1. -> 18446744073709551616. ошибка вычитания равна 1, что фактически равно значению меньшего операнда.

Когда значение с плавающей запятой преобразуется в целочисленный тип, а значение не помещается в целочисленный тип, поведение программы не определено, даже если целочисленный тип не имеет знака.

person eerorika    schedule 01.03.2019

arrow_upward
0
arrow_downward

TL;DR: дело не в том, что тип uint64_t не может правильно отображать pow(2,64)-1, а наоборот: double не может хранить ровно 264 - 1 из-за отсутствия значащих бит. Вы можете сделать это только с типами с точностью 64 бита или более (например, long double на многих платформах). Попробуйте std::pow(2.0L, 64) - 1.0L (обратите внимание на суффикс L) или powl(2.0L, 64) - 1.0L; и посмотрите

В любом случае вы не должны использовать тип с плавающей запятой для целочисленной математики с самого начала. Мало того, что вычисление pow(2, x) намного медленнее, чем 1ULL << x, это также вызовет проблему, которую вы видели, из-за ограниченной точности double. Вместо этого используйте uint64_t max2 = -1 или ((unsigned __int128)1ULL << 64) - 1, если компилятор поддерживает __int128.

pow(2, 64) - 1 — это выражение double, не int, поскольку pow не имеет перегрузки, которая возвращает целочисленный тип. Целое число 1 будет повышено до того же ранга, что и результат pow.

Однако, поскольку длина двойной точности IEEE-754 составляет всего 64 бита, вы никогда не можете хранить значения, имеющие 64 или более значащих бита, например 264-1.

Таким образом, pow(2, 64) - 1 будет округлено до ближайшего представимого значения, которое равно самому pow(2, 64), а pow(2, 64) - 1 == pow(2, 64) даст 1. Наибольшее значение, которое меньше этого, равно 18446744073709549568 = 264 - 2048. Вы можете проверить это с помощью std::nextafter.

На некоторых платформах (особенно x86, кроме MSVC) long double имеет 64 бита значимости, поэтому в этом случае вы получите правильное значение. следующий фрагмент

double max1 = pow(2, 64) - 1;
std::cout << "pow(2, 64) - 1 = " << std::fixed << max1 << '\n';
std::cout << "Previous representable value: " << std::nextafter(max1, 0) << '\n';
std::cout << (pow(2, 64) - 1 == pow(2, 64)) << '\n';

long double max2 = pow(2.0L, 64) - 1.0L;
std::cout << std::fixed << max2 << '\n';

распечатывает

pow(2, 64) - 1 = 18446744073709551616.000000
Previous representable value: 18446744073709549568.000000
1
18446744073709551615.000000

Вы можете ясно видеть, что long double может хранить правильное значение, как и ожидалось.

На многих других платформах double может быть четырехкратной точности IEEE-754 или двойной-двойной. Оба имеют более 64 битов значимости, поэтому вы можете делать одно и то же. Но, конечно, накладные расходы будут выше

person phuclv    schedule 01.03.2019