Вот программа для поиска факториала числа.Почему я получаю 0 в качестве ответа?Какой тип данных я должен использовать вместо этого?

Question

Я относительно новичок в C. Я сделал эту программу, чтобы найти факториал любого числа.После выполнения программы, когда я предоставляю 33 в качестве ввода - я получаю 2147483648 в качестве ответа.Если я предоставлю 34, я получу 0 в качестве ответа.

Переход к моему вопросу - Почему я получил 0 в качестве ответа?Тип данных, который я использовал, имеет диапазон 0-4294967295.Я получаю 0, потому что это за пределами диапазона без знака int?Какой тип данных мне следует использовать, если я хочу получить большое число в качестве результата?

Используется компилятор - GCC 8.2.1

Вот код -

#include<stdio.h>
#include<stdlib.h>
int fact(unsigned int n)
{
        int result;
        if(n==0 || n==1)
                result=1;
        else
                result=n*fact(n-1);
        return result;
}
int main()
{
        unsigned int n,ans;
        printf("Enter n:");
        scanf("%u",&n);
        ans=fact(n);
        printf("Factorial of %u:%u",n,ans);
}

Answer 1

unsigned int имеет диапазон значений от 0 до 2^32-1 или 2^32 = 4,294,967,296.Присвоение result значения выше 2^32-1 = 4,294,967,295 приводит к переполнению значения.Это просто означает, что он возвращается к 0, после чего может снова увеличиться до 4,294,967,295.

Первое переполнение происходит при вычислении 13!, когда мы ожидаем, что значение result будет13! = 6,227,020,800.Однако мы не приняли во внимание переполнение.Вместо этого значение result будет равно оставшейся части уравнения 13! % 2^32, или 1,932,053,504, потому что именно так увеличивается result после последнего (и, в данном случае, только) цикла до 0.

Теперь 33! или 34! представляют значения, которые невообразимо велики и вызывают переполнение result много раз.Мы можем вычислить, сколько раз 33! вызывает переполнение, просто разделив его на 2^32, что приведет к переполнению 2.02e27.Однако ваш вопрос касается не количества переполнений, а значения остатка после последнего переполнения.В этом случае он равен 33! % 2^32 = 2,147,483,648.Мы можем сделать то же самое для 34: 34! % 2^32 = 0.

Это означает, что, по совпадению, 2^32 является правильным делителем 34!.Или это не случайно после всех ?

Редактировать : как и другие предлагали, вам следует взглянуть на библиотеку GMP Bignum без ограничений в точности арифметики, кроме вашей машины.

Answer 2

Вы получаете 0, когда переполняете свои типы данных.Формально поведение при переполнении int равно undefined .Если вы переключите последовательно на unsigned типы, то переполнение будет таким, что поведение будет соответствовать арифметическому модулю 2, возведенному в степень числа бит в вашем типе unsigned.

Поскольку большой факториал кратен степени 2, 0, как вы заметили, будет достигнут на удивительно малом входном сигнале.

Answer 3

33! фактически является выходом из диапазона 32-битного int, независимо от того, подписано оно или нет.12! имеет значение 479001600, а 13! имеет значение 6227020800, поэтому вы выходите за пределы диапазона 13!.

Обратите внимание, что result определяется как int, и вы возвращаете int из fact.Это означает, что вы получите целочисленное переполнение со знаком, которое вызывает неопределенное поведение .Это можно исправить, изменив тип обоих на unsigned, хотя вы по-прежнему ограничены 12!.

Вместо этого вы можете попробовать использовать unsigned long long для своих типов.Это даст вам до 20!.Если вы хотите, чтобы значения были больше этого, вам нужно использовать библиотеку bigint, такую ​​как GMP.

Answer 4

Факториал растет очень быстро .13!уже находится вне диапазона, представляемого 32-разрядным целым числом без знака.Арифметика без знака возвращает остаток, когда результат не может быть представлен, то есть вы получаете только младшие биты истинного математического результата.Вы могли бы пойти немного выше, используя более широкий тип данных, но не намного.Вам нужен арифметический пакет произвольной точности и много памяти, чтобы идти гораздо дальше.

А почему вы получаете результат 34!равно нулю , обратите внимание, что среди факторов 1 * 2 * 3 * ... * 33 * 34 есть 17, кратные двум, 8 из которых также кратны 4, 4 из которых также кратны8, два из которых кратны 16, и один из которых равен 32. Это в сумме 32 2 с при простой факторизации математического результата, поэтому остаток по модулю 2 ³² равен точно нулю.

Answer 5

Ваше предположение Тип данных, который я использовал, имеет диапазон 0-4294967295. неверно.Вы определяете параметр ans как unsigned int, который имеет диапазон 0-4294967295, но в своей функции факта вы используете int, который имеет диапазон -2,147,483,648 to 2,147,483,647.

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

#include<stdio.h>
#include<stdlib.h>
unsigned int fact(unsigned int n)
{
        unsigned int result;
        if(n==0 || n==1)
                result=1;
        else
                result=n*fact(n-1);
        return result;
}
int main()
{
        unsigned int n,ans;
        printf("Enter n:");
        scanf("%u",&n);
        ans=fact(n);
        printf("Factorial of %u:%u",n,ans);
}

Вы также можете использовать unsigned long long вместо unsigned int, который будет поддерживать большие числа и больше подходит для факторного расчета.

#include<stdio.h>
#include<stdlib.h>
unsigned long long fact(unsigned int n)
{
        unsigned long long result;
        if(n==0 || n==1)
                result=1;
        else
                result=n*fact(n-1);
        return result;
}
int main()
{
        unsigned int n;
        unsigned long long ans;
        printf("Enter n:");
        scanf("%u",&n);
        ans=fact(n);
        printf("Factorial of %u:%u",n,ans);
}

Больше чтения о типах данных и ихдиапазон: https://www.tutorialspoint.com/cprogramming/c_data_types.htm