C Обработка факториала с большими числами

Я пытаюсь вычислить 52! используя язык C. Но мне кажется, что я как-то не справляюсь с большими числами. Я не могу сказать, мой ли это компилятор или я что-то делаю неправильно ...

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

uint64_t factorielle(int n) {
   if(n == 0)
       return 1;
    else
      return n * factorielle(n-1);
}

int main(int argn, char** argv) {

  printf("Number : %"PRId64"\n", factorielle(52));

  return 0;
}

Получаю такой результат:

Number : -8452693550620999680

Я пробовал с GCC 5.3.0, GCC 7.2.0 и Zapcc 5.0.0

Большое спасибо !


person Community    schedule 27.11.2017    source источник
comment
Стоит провести небольшое исследование диапазона значений, которые подходят для int.   -  person Oliver Charlesworth    schedule 27.11.2017
comment
Вы не можете вычислить факториал чисел больше 21! на 64-битной машине этим методом.   -  person haccks    schedule 27.11.2017
comment
При печати результата у вас несоответствующий формат и тип аргумента. Вы указываете printf напечатать значение со знаком, но factorielle возвращает значение без знака. Однако исправление этого не поможет, для этого вам понадобится библиотека bignum.   -  person Some programmer dude    schedule 27.11.2017
comment
52! = 8.0658175e + 67 ›(гораздо больше ужина)› 2 ^ 64-1 = 1.8446744e + 19   -  person Julien    schedule 27.11.2017
comment
Обычно: каждый раз, когда вы пишете или думаете что-то вроде , я не могу сказать, мой ли это компилятор или я делаю это неправильно, вы делаете что-то не так.   -  person Jabberwocky    schedule 27.11.2017
comment
Пытаетесь найти комбинации перестановок в карточной игре?   -  person Vagish    schedule 27.11.2017
comment
Попробуйте использовать PRIu64 вместо PRId64. Ваша функция возвращает целое число без знака! Но думаю 52! создать слишком большое число!   -  person Sir Jo Black    schedule 27.11.2017
comment
Время от времени его спрашивают (см. Дубликат), и что ж, встроенные типы данных действительно имеют некоторые ограничения. Ради забавы я придумал эту реализацию. некоторое время назад.   -  person    schedule 27.11.2017
comment
Всем большое спасибо, я разберусь с этим!   -  person    schedule 27.11.2017
comment
Большее число, которое вы можете представить с помощью uint64_t, очевидно, 0xFFFFFFFFFFFFFFFF, то есть 18.446.744.073.709.551.615!   -  person Sir Jo Black    schedule 27.11.2017
comment
@SergioFormiggini, особенно в контексте этого вопроса, 18.446.744.073.709.551.615! (!) Кажется немного большим ...;)   -  person    schedule 27.11.2017
comment
@FelixPalmen, как ты думаешь, почему он великоват !? Я распечатал результат, используя: uint64_t x = (0xFFFFFFFFFFFFFFFF); printf("Number : %"PRIu64"\n", x); ...;)   -  person Sir Jo Black    schedule 27.11.2017
comment
52! 8,0658175170943878571660636856404e + 67 ... e + 67 немного больше, чем 18.446.744.073.709.551.615 (1,8 e + 19).   -  person Sir Jo Black    schedule 27.11.2017
comment
@FelixPalmen, да (извините) в контексте максимальное 64-битное целое число немного мало 52! ...;)   -  person Sir Jo Black    schedule 27.11.2017
comment
Ах, ах, ах ... @FelixPalmen, я не понимал, что написал 18.446.744.073.709.551.615! ... XD   -  person Sir Jo Black    schedule 27.11.2017


Ответы (3)


Узнайте больше о факториалах.

Подсказка: всегда полезно немного прочитать перед написанием кода, если вы не знакомы с предметом.

Попробуйте найти оценку факториала 52 (например, его логарифма). Для этой цели вы можете использовать приближение Стирлинга. Вы обнаружите, что это действительно большое число (намного больше, чем 2 64 -1, что обычно является наибольшим числом, которое может обработать ваша реализация C).

Рассмотрите возможность использования некоторой библиотеки арифметики произвольной точности (также известной как "bignum" s), например GMPlib. Кстати, эффективные библиотеки bignum действительно сложно кодировать (так что вы сделаете намного хуже, чем то, что вам дают существующие библиотеки), потому что их алгоритмика очень сложна.

Возможно, вам не нужно вычислять такой большой факториал.

person Basile Starynkevitch    schedule 27.11.2017
comment
Хорошо, спасибо большое. Я ничего об этом не знал. Я проведу небольшое исследование. - person ; 27.11.2017
comment
Для небольших чисел, например 52, вы можете вычислить логарифм n! используя математическую библиотечную функцию lgamma (). Преобразование этого естественного журнала в журнал base2 даст вам оценку того, сколько битов вам понадобится. В этом случае lgamma (53.0) / log (2.0) дает 2.255810031e + 02, поэтому вам понадобится 226 бит. - person dmuir; 27.11.2017

Вы никогда не можете представить 52! в любом из C целочисленных типов (64-разрядные). Одно из решений - использовать вашу собственную структуру данных для представления такого большого значения или попытаться найти какую-нибудь библиотеку (например, GMP, которая предоставляет эту возможность.

Вы можете проверить, что значение самого 2^64 равно 1.8446744e+19, что намного меньше 8.0658175e+67. Таким образом, невозможно использовать integer типов в C.

Еще несколько мыслей по поводу Вы никогда не сможете представить 52! ни одним из C целочисленных типов

Как уже упоминалось, для многих систем невозможно использовать 64-битные целочисленные типы (int64_t). Давайте углубимся в дело. (54! требует 238 двоичных единиц). Типом int256_t можно было бы представить 52!. Но int256_t на данный момент не является стандартным типом. DEC VAX даже поддерживает операции с 128-битными целыми числами. Как упомянуто chux даже сейчас различные компиляторы поддерживают 128-битные целочисленные типы и операции, поэтому вполне возможно расширить его для поддержки 256-битных целочисленных типов. Тогда, думаю, этого нельзя было сказать Вы никогда не можете представить 52! ни в одном из C целочисленных типов

person user2736738    schedule 27.11.2017
comment
Хорошо, я попробую использовать лучшую структуру данных. Я разберусь с этим. Спасибо ! - person ; 27.11.2017
comment
Вы никогда не сможете представить 52! в любом из целочисленных типов C. - ›54! требуется около 238 двоичных разрядов. Такой тип, как int256_t, может с этим справиться. Хотя int256_t не является стандартным типом, никогда не бывает надолго. Даже сейчас различные компиляторы предлагают 128-битные целочисленные типы, и сегодня компилятор может поддерживать такие широкие 128/256-битные типы. 256-битное целое число не так уж надумано. Может, через десять-два года. - person chux - Reinstate Monica; 27.11.2017
comment
@chux .: Хорошая мысль. Собственно, я так и думал, когда писал. То, как все меняется, может зайти так далеко. Еще раз спасибо за вклад. Я отредактирую ... и попрошу посмотреть, если вы не против. - person user2736738; 27.11.2017

Факториал 54 равен

230843697339241380472092742683027581083278564571807941132288000000000000

который слишком велик для обработки какими-либо примитивными типами данных в C.

Если вы пытаетесь реализовать факторную программу для вычисления факториалов таких больших чисел, вы можете следовать этому учебник.

person haccks    schedule 27.11.2017
comment
Я проверю этот урок, спасибо. На самом деле я не искал самой ценности, но я хотел решить эту проблему для личных знаний. - person ; 27.11.2017