журнал аргумента unsigned long long int

Мне нужно сделать следующий расчет в коде С++:

(((n*log(n)) / log(4)) + 1)

Где n имеет тип unsigned long long int (и является степенью числа 2, поэтому результат должен быть целым числом).

Для очень больших чисел я получаю некоторые ошибки, например, для n = 9007199254740992 результат должен быть 238690780250636289, но когда я запускаю код, я получаю 238690780250636288.

Может ли это быть результатом того, что функция «журнал» не имеет реализации с аргументом «unsigned long long int»? Если да, то есть ли способ обойти это без реализации новой функции журнала?

unsigned long long int upToBit(unsigned long long int n) {
    unsigned long long int check = (((n*log(n)) / log(4)) + 1);
    return check;
}

c++ cmath
person Vlad Keel    schedule 01.05.2017    source источник
comment
JFYI, C++11 позволяет упростить вычисления: (((n*log(n)) / log(4)) + 1) = (((n*log(n)) / (2*log(2))) + 1) = n/2 * std::log2(n) + 1   -  person nnovich-OK    schedule 01.05.2017
comment
Ого, сколько скобок! Неудивительно, что я не мог найти их, когда они мне были нужны.   -  person Pete Becker    schedule 01.05.2017

Ответы (1)


arrow_upward
7
arrow_downward

Может ли это быть результатом того, что функция «журнал» не имеет реализации с аргументом «unsigned long long int»?

И да и нет.

Вы используете std::log, который возвращает значение double. double не может представлять 238690780250636289 из-за расширенного диапазона. Если вы просто преобразуете это число в long long, вы получите точно такую ​​же ошибку:

int main()
{
    volatile double dd = 238690780250636289.0;
    printf("%lld\n", (long long)dd);
}

Выход:

238690780250636288

Чтобы понять, почему это происходит, есть хороший документ о плавающей запятой номера. Вам может повезти с длинной двойной версией журнала, если sizeof(long double) > 8 на вашем компиляторе. Вы также можете проверить «правильность» ваших вычислений:

bool resultOk = upToBit(9007199254740992) == 238690780250636289.0;

В общем, double имеет 52-битную мантисса, и из-за дополнительного скрытого бита максимальное надежное целое число, которое может представлять double, равно 2 в степени 53 или 9007199254740992. Если полученное двойное число имеет более высокое целочисленное значение, чем простая целочисленная математика, иногда "перестает работать":

#include <stdio.h>

int main()
{
    long long l = 9007199254740992;
    double d = (double)l;
    d += 1;
    printf("9007199254740992 + 1 = %lld\n", (long long)d);
}

Выход:

9007199254740992 + 1 = 9007199254740992

Чтобы повысить точность, вы можете использовать некоторые из арифметических библиотек с множественной точностью, которые предназначены для этого. GCC, например, использует GMP / MPFR для своих внутренних вычислений.

person Pavel P    schedule 01.05.2017
comment
Так есть ли решение? - person Sniper; 01.05.2017
comment
@sniper, вы могли бы использовать библиотеку наподобие gmp, которая позволяет выполнять арифметические операции с произвольно большими числа (превышающие диапазоны встроенных типов). - person Jesper Juhl; 01.05.2017