Вычислить факториалы в С#

Ответ 1

Посмотрите на структуру BigInteger:

http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.aspx

Возможно, это поможет вам реализовать эту функциональность.

CodeProject имеет реализацию для более старых версий фреймворка http://www.codeproject.com/KB/cs/biginteger.aspx.

Ответ 2

Если я попытаюсь написать простой факториал в С# [рекурсивный или цикл], производительность будет очень плохой. Чтобы получить ответ, требуется несколько секунд.

Давайте сделаем быстрый порядок величины здесь для наивной реализации факториала, который выполняет n умножений. Предположим, что мы на последнем шаге. 19999! составляет около 2 18 бит. 20000 составляет около 2 × 5 бит; мы предположим, что это 32-битное целое число. Следовательно, конечное умножение включает добавление до 2 ^ 5 частичных результатов, каждый примерно 2 18-бит. Таким образом, количество бит-операций будет порядка 2 ^ 23. Это для последнего этапа; на каждом этапе будет 20000 = 2 ^ 16 таких операций, так что это всего около 2 ^ 39 операций. Некоторые из них, конечно, будут дешевле, но здесь мы собираемся на порядок.

Современный процессор выполняет около 2 ^ 32 операций в секунду. Поэтому для получения результата потребуется около 2 ^ 7 секунд.

Конечно, большие писатели целочисленных библиотек не были наивными; они используют способность чипа выполнять многобитовые операции параллельно. Вероятно, они делают математику в 32-битных кусках, давая ускорения в 2-5 раз. Таким образом, наш общий порядок величины вычислений состоит в том, что для получения результата потребуется около 2 ^ 2 секунд.

2 ^ 2 - 4. Таким образом, ваше наблюдение, что требуется несколько секунд, чтобы получить результат, ожидается.

Как вычисляется в Windows 2k3 (или XP) возможность выполнить такой огромный факториал менее чем за 10 секунд?

Я не знаю. Крайняя уловка в использовании математических операций на чипе. Или, используя не наивный алгоритм вычисления факториала. Или, возможно, они используют аппроксимацию Стирлинга и получают неточный результат.

Есть ли другой способ вычисления факториала программно в С#?

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

Ответ 3

Существуют сложные вычислительные алгоритмы для эффективного вычисления факториалов больших чисел произвольной точности. алгоритм Schönhage-Strassen, например, позволяет выполнить асимптотически быстрое умножение для сколь угодно больших целых чисел.

Случай, Mathematica вычисляет 22000! на моей машине менее чем за 1 секунду. На странице Замечания по внедрению на странице reference.wolfram.com указано:

(Mathematica's) n! uses an O(log(n) M(n)) algorithm of Schönhage based on dynamic decomposition to prime powers.

К сожалению, реализация таких алгоритмов сложна и подвержена ошибкам. Вместо того, чтобы пытаться свернуть свою собственную реализацию, может быть разумнее лицензировать копию Mathematica (или аналогичного продукта который соответствует вашим функциональным и эксплуатационным требованиям) и либо используйте его, либо .NET-интерфейс программирования для выполнения своих вычислений.

Ответ 4

Вы посмотрели System.Numerics.BigInteger?

Ответ 5

Использование System.Numerics BigInteger

var bi = new BigInteger(1);
var factorial = 171;
for (var i = 1; i <= factorial; i++)
{
    bi *= i;
}

будет рассчитываться как

1241018070217667823424840524103103992616605577501693185388951803611996075221691752992751978120487585576464959501670387052809889858690710767331242032218484364310473577889968548278290754541561964852153468318044293239598173696899657235903947616152278558180061176365108428800000000000000000000000000000000000000000

За 50000! для вычисления требуется несколько секунд, но, похоже, это работает, и результат составляет 213237 цифр, и это также говорит о Wolfram.

Ответ 6

Вам, вероятно, придется реализовать свой собственный произвольный тип точности.

Существуют различные подходы. вероятно, не самый эффективный, но, возможно, самый простой - иметь массивы переменной длины байта (unsigned char). Каждый элемент представляет собой цифру. в идеале это будет включено в класс, и вы можете добавить метод, который позволит вам умножить число с другим произвольным числом точности. Умножение со стандартным С# целым числом, вероятно, также будет хорошей идеей, но немного сложнее реализовать.

Ответ 7

Для этого вам нужна специальная библиотека большого числа. Эта ссылка представляет класс System.Numeric.BigInteger и, кстати, имеет примерную программу, которая вычисляет факториалы. Но не используйте пример! Если вы это повторите, ваш стек будет ужасно расти. Просто напишите for-loop, чтобы выполнить умножение.

Ответ 8

Так как они не дают вам результат до последней цифры, они могут быть "обманывать", используя некоторое приближение. Проверьте http://mathworld.wolfram.com/StirlingsApproximation.html Используя формулу Стирлинга, вы можете вычислить (приближение) факториал n в logn time. Разумеется, они могут иметь словарь с заранее вычисленными значениями factorial (n) для каждого n до миллиона, что делает калькулятор очень результативным.

Ответ 9

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

Как видите, их много.

>>> factorial(20000)
<<non-zeroes removed>>0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000L

Ответ 10

Этот ответ охватывает ограничения для базовых типов .Net для вычисления и представления n!

Базовый код для вычисления factorial для "SomeType", который поддерживает умножение:

SomeType factorial = 1;
int n = 35;
for (int i = 1; i <= n; i++)
{
   factorial *= i; 
}

Пределы для встроенных типов номеров:

• short - правильные результаты до 7!, неправильные результаты впоследствии, код возвращает 0 начиная с 18 (аналогично int)
• int - правильные результаты до 12!, неправильные результаты впоследствии, код возвращает 0, начиная с 34 (Почему вычисление факториала из реальных чисел (34+) возвращает 0)
• float - точные результаты до 14!, правильные, но не точные впоследствии, возвращает бесконечность начиная с 35
• long - правильные результаты до 20!, неправильные результаты впоследствии, код возвращает 0, начиная с 66 (аналогично int)
• double - точные результаты до 22!, правильные, но не точные впоследствии, возвращает бесконечность начиная с 171
• BigInteger - точный и верхний предел задается только с использованием памяти.

Примечание. Целые типы переполняются довольно быстро и начинают выдавать неверные результаты. Реально, если вам нужны факториалы для любого практического использования long - это тип (до 20!), Если вы не можете ожидать ограниченные числа - BigInteger - единственный тип, предоставляемый в .NET Framework для предоставления точных результатов ( хотя и медленный для больших чисел, поскольку нет встроенного оптимизированного метода n!)