Факториальная программа на C неверна после 20

Он работает до 20, но если введено 21, он возвращает 1419745... когда 21 факториал на самом деле равен 51090942171709440000. Я предполагаю, что это из-за максимального значения unsigned long, но откуда взялось это неправильное число (141...) откуда и как я могу разрешить программе вычислять факториал больших чисел?

#include <stdio.h>

unsigned long fact(unsigned long input);

int main()

{

    int input;

    printf("Enter an integer to find the factorial of: ");
    scanf(" %d", &input);

    printf("The Factorial of %d = %lu\n" , input, fact(input)); 

    return 0;
}

unsigned long fact(unsigned long input)
{
    if (input == 0)
            return 1;
    else    
        return input * fact(input - 1);
}

c long-integer factorial unsigned
person banana1337    schedule 09.03.2016    source источник
comment
А что такое ULONG_MAX в вашей системе?   -  person too honest for this site    schedule 09.03.2016
comment
Попробуйте unsigned long long.   -  person Spikatrix    schedule 09.03.2016
comment
@ Олаф, я не уверен, что это такое, не могли бы вы объяснить, пожалуйста?   -  person banana1337    schedule 09.03.2016
comment
После переполнения умножения обычно остается наименее значащая часть, но это двоичное усечение, а не десятичное, поэтому значение кажется бессмысленным. Есть 2 подхода: используйте большую библиотеку int, или иногда после этого требуется модуль произведения - держите число в пределах, применяя модуль после каждого умножения.   -  person Weather Vane    schedule 09.03.2016
comment
@CoolGuy unsigned long long недостаточно (по крайней мере, если компилятор использует минимальный размер, установленный стандартом)   -  person Garf365    schedule 09.03.2016
comment
20! требуется 62-битная память   -  person Weather Vane    schedule 09.03.2016
comment
Просто распечатайте! И гугл твой друг.   -  person too honest for this site    schedule 09.03.2016
comment
@banana1337 ULONG_MAX — это макрос, который содержит максимальное значение, которое может быть сохранено внутри unsigned long.   -  person Garf365    schedule 09.03.2016
comment
@ Garf365 Что ты имеешь в виду? Я думал, что unsigned long long может хранить больше значений, чем unsigned long.   -  person Spikatrix    schedule 09.03.2016
comment
@CoolGuy long long не должен быть длиннее 64 бит. На компьютере OP long уже 64-битный. int, с другой стороны, не должен быть длиннее 32 бит в любой системе.   -  person vll    schedule 09.03.2016
comment
В повторяющемся вопросе ОП вычислял условия для ряда Тейлора. В ответе @nickie указано, что вам даже не нужно вычислять факториал, поскольку каждый член можно рассчитать из предыдущего члена с помощью умножения и деления.   -  person Weather Vane    schedule 09.03.2016
comment
@CoolGuy на самом деле, это не совсем так: unsigned long должно быть не менее 32-битным, unsigned long long должно быть не менее 64-битным и sizeof(unsigned long long) >= sizeof(unsigned long). Так что не исключено, что unsigned long long и unsigned long имеют одинаковый размер и поэтому хранят одинаковые значения.   -  person Garf365    schedule 09.03.2016
comment
Численные пределы различных целочисленных типов — это первое, что обсуждается при изучении любого языка программирования. Обычно это обсуждается в главе 1 или 2 любой книги по программированию для начинающих для любого языка программирования.   -  person Lundin    schedule 09.03.2016
comment
@Ville-ValtteriTiittanen: нет ограничений на ширину любого целочисленного типа. int вполне может иметь 1024 бита.   -  person too honest for this site    schedule 09.03.2016

Ответы (2)


arrow_upward
4
arrow_downward

Это отвечает только на половину вашего вопроса (почему это так работает).

Вы получите следующий результат: 21! mod 2^64. Это связано с тем, что вы используете 64-битную систему, а 21! больше, чем максимальное число, которое может быть сохранено как целое число без знака в 64-битном формате.

Все факториалы, которые вы вычисляете для значений, больших или равных 21, неверны; они не могут быть представлены 64-битными целыми числами, потому что они длиннее.

Вы можете попробовать использовать unsigned long long в качестве типа значений, возвращаемых функцией fact() (и перейти на строку формата printf() %lu с %llu); это может помочь, но это зависит от некоторых факторов. Например, это не помогает в моей архитектуре.

Вы можете узнать, может ли это вам помочь, проверив значение, возвращаемое sizeof(unsigned long long). Если 8, то вам не повезло. 20 — это наибольшее число, которое вы можете вычислить факториалом в этой системе.

Если вашей целью является вычисление факториалов, вам нужно использовать библиотеку, которая знает, как обрабатывать большие числа. Однако, если вам нужны факториалы для других вычислений (например, для комбинаций), вы можете попробовать избегайте создания больших чисел и найдите способ сопоставить каждое умножение с делением. Таким образом, величина используемых вами чисел находится в пределах 64-битных целых чисел, и вы можете пойти дальше, чем 21.

Или вы можете использовать double вместо целых чисел, и вы снова в деле, но с потерей точности. Большие числа с плавающей запятой правильно сохраняют величину числа и его первые цифры. Последние цифры теряются.

Я не очень много программировал на C/C++ в последнее время, я не могу порекомендовать вам библиотеку, которая может помочь вам выполнять вычисления с большими числами :-(

person axiac    schedule 09.03.2016

arrow_upward
0
arrow_downward

Число происходит от переполнения. Арифметика без знака выполняется по модулю (максимальное значение этого типа), поэтому немного математики должно объяснить, почему вы получаете такой результат.

Результат переполнения целого числа со знаком не определен, поэтому вы могли бы получить что угодно, если бы использовали целые числа со знаком (хотя есть вероятность, что во многих системах это было бы точно так же)

person Tom Tanner    schedule 09.03.2016