Почему моя арифметика с длинным длинным int ведет себя так? - PullRequest
Новая
       78

Почему моя арифметика с длинным длинным int ведет себя так?

31 голосов
/ 03 мая 2019

Я пытаюсь вычислить большие целые числа с типом данных long long, но когда он становится достаточно большим (2^55), арифметическое поведение непредсказуемо.Я работаю в Microsoft Visual Studio 2017.

В этом первом случае я вычитаю 2 из long long переменной m при инициализации.Это прекрасно работает для всех n, пока я не попробую 54, тогда m просто не будет вычтено 2. 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>

using namespace std;

#define LL long long

int main()
{
    LL n;
    cin >> n;
    LL m = pow(2, n + 1) - 2;
    cout << m;
    return 0;
}

Однако, использование этого кода m действительно вычитается2 и работает так, как я ожидал. 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>

using namespace std;

#define LL long long

int main()
{
    LL n;
    cin >> n;
    LL m = pow(2, n + 1);
    m -= 2;
    cout << m;
    return 0;
}

Я ожидаю, что оба кода эквивалентны, почему это не так?

Ответы [ 3 ]

50 голосов
/ 03 мая 2019

Проблема с 

LL m = pow(2, n + 1) - 2;

означает, что pow(2, n + 1) не является long long. Он имеет тип double, и поскольку значение слишком велико, вычитание 2 из него не изменит его значения. Это означает, что m не будет иметь правильное значение. Как вы уже нашли, вам нужно сначала присвоить результат, а затем выполнить вычитание. Другая альтернатива - написать свой собственный pow, который будет возвращать целочисленный тип, когда ему дан целочисленный тип, чтобы вы могли одновременно делать возведение в степень и вычитание.

19 голосов
/ 03 мая 2019

Я ожидаю, что оба кода эквивалентны, почему это не так?

Ваше ожидание неверно.Ваш второй код будет эквивалентен следующему: 

auto m = static_cast<LL>( pow(2, n + 1) ) - 2;

в связи с правилом преобразования для арифметических операторов и тем фактом, что std::pow() возвращает double вв этом случае:

Для бинарных операторов (кроме сдвигов), если повышенные операнды имеют разные типы, применяется дополнительный набор неявных преобразований, известных как обычные арифметические преобразования, с целью создания общего типа(также доступно через черту типа std :: common_type).Если до какого-либо интегрального преобразования один операнд имеет тип перечисления, а другой - тип с плавающей запятой или другой тип перечисления, такое поведение не рекомендуется.(начиная с C ++ 20)

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

В противном случае, если один из операндовlong double, другой операнд преобразуется в long double

В противном случае, если один из операндов является двойным, другой операнд преобразуется в двойной

В противном случае, если один из операндовfloat, другой операнд преобразуется в float

...

(акцент мой), ваше оригинальное выражение приведет к double - double вместо long long int- long long int как и во втором случае, отсюда и разница.

16 голосов
/ 03 мая 2019

Функция pow возвращает значение типа double, которое имеет только 53 бита точности. Хотя возвращаемое значение будет соответствовать double, даже если n больше 53, вычитание 2 приводит к значению типа double, для которого требуется точность более 53 битов, поэтому результат вычитания округляется до ближайшее представимое значение.

Причина, по которой начинается вычитание, состоит в том, что значение double, возвращаемое из pow, присваивается long long, затем вы вычитаете int из long long.

Поскольку вы не имеете дело с числами с плавающей запятой, и вы повышаете только 2 до степени, вы можете заменить вызов на pow простым сдвигом влево: 

LL m = (1LL << (n + 1)) - 2;

При этом все промежуточные значения сохраняются в типе long long.

...