почему использование int64_t дает неправильный результат, в то время как удвоение работает, как ожидается, для простых целочисленных умножений

Question

вот мой код:

using integer = int64_t;

integer factorial(integer number) {
    return number <= 0 ? 1 : number * factorial(number - 1);
}

integer binomial_coefficent(integer n, integer r) {
    return factorial(n) / (factorial(r) * factorial(n - r));
}

int main()
{
    using namespace std;
    cout << binomial_coefficent(40, 20) << endl;
    return 0;
}

это печатает

0

, что является неправильным ответом, но если я изменю тип целого числа на удвоенный, то будет напечатано 1.37847e+11, что является правильнымответ, мой вопрос, почему использование int64_t дает мне неправильный ответ

Answer 1

40! составляет около 8e47.64-разрядное целое число со знаком может содержать максимум 2^63-1, около 1e19.

factorial(40) переполнено, и поскольку переполнение целочисленных типов со знаком является неопределенным поведением, все, что вы наблюдаете, объяснить невозможно.

Answer 2

Добро пожаловать в мир чисел с конечной точностью!факт (40) равен 815915283247897734345611269596115894272000000000 или 0x8eeae81b84c7f27e080fde64ff05254000000000, который, очевидно, не поместится ни в uint64_t, ни в 128 бит long long, поскольку для него действительно требуется 160 бит!вычисляется с использованием uint64_t при условии, что вы используете правильный алгоритм, к которому привыкли люди, прежде чем компьютеры появятся повсюду:

integer binomial_coefficient(integer n, integer r) {
    integer bc = 1;
    integer q = n - r;
    for(integer i=1; i<=r; i++) {
        br = br * (q + i) / i;
    }
    return bc;
}

Этот код даст вам правильное значение 137846528820 без переполнения.

(вышеуказанная функция пропускает тест для r <= n / 2, который может быть дополнительной оптимизацией, поскольку Cn, p по построению Cn, np) </p>

Answer 3

и int64_t также не переполняются

Хотя это так.Для отладки подобных вещей вы можете запустить это с -fsanitize=signed-integer-overflow (подразумевается -fsanitize=undefined) в GCC или clang, чтобы увидеть:

ошибка времени выполнения: целочисленное переполнение со знаком: 21 * 2432902008176640000 не может быть представленов типе «long»
ошибка времени выполнения: целочисленное переполнение со знаком: 2432902008176640000 * 2432902008176640000 не может быть представлено в типе «long»