2009-05-30 8 views
3

Кто-нибудь знают способ я могу вычислить очень большие целые числа в C#работает с очень большими числами в C#

Я пытаюсь вычислить факториал числа, например,

5! = 5 * 4 * 3 * 2 * 1 = 120

с небольшими номерами это не проблема, но попытка вычислить факториал самого большого значения unsigned int, который составляет 4 294 967 295, кажется невозможным.

Я посмотрел в класс BigInteger, но это, кажется, не делать то, что мне нужно

любая помощь будет принята с благодарностью

+1

проблема с факториалом заключается в том, что даже при работе с релятивистами небольшие целые числа, такие как 256, он по-прежнему вычисляет результат, который составляет около 507 цифр, поэтому мне было бы неловко думать, сколько цифр 4294967295! будет yeild. переменные с плавающей запятой не полезны для моего приложения. – Avner

+1

Какое приложение нуждается в этом? Звучит скорее как домашняя проблема CS :) –

+4

Мне все еще интересно, что вы делаете, для чего требуется точное значение (2^32)! В соответствии с этим: http://www47.wolframalpha.com/input/?i=(2^32)! Это около 10^39507966976. Чтобы представить в перспективе, атомы в наблюдаемой вселенной составляют всего около 10^80, поэтому вы смотрите на число около 10^39507966896 раз больше числа атомов в наблюдаемой вселенной. – Davy8

ответ

4

4294967295! = 10^(10^10.597) ~ 10^(40000000000) Для сохранения этого значения требуется около 40 ГБ ОЗУ, даже если вы найдете реализацию BigInteger для C#!

P.S. Ну, с оптимизированным хранением, скажем, 9 цифр в 4 байта, потребуется около 18 ГБ ОЗУ.

+1

Я вижу вашу точку зрения. Думаю, с нынешней технологией это было бы непрактично. спасибо – Avner

+0

Эй, ребята, ваш разговор полностью не математичен :) Нам нужны факториалы от произвольных чисел точности, основанных на гамма-функции. Не рекурсивный мозг, мертвый. Их много, но я еще не нашел их на C#. – Harry

4

Во-первых, стоит отметить, что факториал uint.MaxValue является астрономически большой. Я не могу найти хорошую оценку порядка величины своего факториала, но его битовое представление, вероятно, будет занимать высокий процент стандартной ОЗУ, если оно не будет значительно превышать.

Класс A BigInteger, кажется, является тем, что вы хотите, предоставляя вам всего лишь около 1 000 000 или около того (очень грубо). После этого время и память становятся очень запретительными. В текущих (стабильных) версиях .NET, до 3.5, вам нужно выполнить специальную реализацию. This one в CodeProject, по-видимому, высоко оценен. Если вы собираетесь разрабатывать .NET 4.0, команда Microsoft, наконец, собралась, чтобы включить класс BigInteger в пространство имен System.Numerics BCL. В отличие от некоторых реализаций BigInteger, один из существующих в .NET 4.0 не имеет встроенного факториального метода (я не уверен в CodeProject), но это должно быть тривиально для реализации одного - метод расширения был бы приятным путь.

Поскольку вы, кажется, думаете, что не хотите использовать тип BigInteger, было бы полезно, если бы вы могли убедиться, что это не то, что вы хотите, прочитав мой ответ, а затем объясните, почему это не подходит вашему цели.

+0

Это было в 2.0 beta и было удалено в финале ... Это было System.Numeric.BigInteger в то время, я надеюсь, что на этот раз они не передумают ... –

+0

@Mehrdad: Действительно. Я знал, что его вытащили из .NET 3.5, но не 2.0. В .NET 4.0 beta 1 уже существует стабильная реализация, поэтому было бы совершенно глупо удалить ее сейчас. – Noldorin

+0

Да, это было 3.5. Я думаю, что он тоже был стабильным ... Иногда люди делают глупое дело;) Кто знает: P –

0

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

+0

У вас есть базовый код, который реализует то, что вы описываете? когда вы говорите, что каждый член массива будет представлять десятичную цифру - не будет ли это тратить пространство, потому что даже если у меня есть массив байтов - каждый байт будет содержать одну цифру, если реально он может содержать значение до 255., если только Я тебя не понял ?! – Avner

+0

Я понял, что он похож на создание нового целочисленного типа. Вам необходимо реализовать основные операции, такие как многосвязность.Это может быть пустой тратой пространства для хранения 1 десятичной цифры в байт. Но вы можете использовать бит-массив (например, класс BitArray). Существует некоторый базовый код http://www.daniweb.com/code/snippet233.html Надеюсь, это поможет. – Vanuan

9

Чтобы рассчитать факториал uint.MaxValue, вам понадобится лот.

Например, Wikipedia article as 8.2639316883 ... × 10^5,565,708. Вы получите информацию, как сумасшедшую.

I настоятельно подозревают, что вы не найдете способ расчета его на разумном компьютере в разумные сроки. Зачем вам это значение? Будет ли приближение Стирлинга достаточно близко?

+0

Я не вижу, как какое-либо приближение собирается решить проблему. во-первых, потому что мне нужен результат exac, а во-вторых, потому что даже приближение все равно нужно будет вычислить и будет по-прежнему очень большим - нет? – Avner

+0

Ну, это зависит от того, что вам нужно делать с этим. Если бы вы могли сохранить его как «это примерно 10^х» для некоторого х, это было бы намного меньше информации, чем «Это точно 1929494 ....» Однако, если вам нужен точный результат, я подозреваю, что у вас будет большая проблема. –

0

Если у вас установлен J # redist, альтернативный способ будет использовать java.math.BigInteger, добавив ссылку на сборку vjslib.

2

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

Просто результат вычисления факториала (2^32-1) займет много места, примерно 16 ГБ.

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

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

0

Если вы выполняете вычисления с использованием факториалов, например, вам редко приходится умножать все до 1 (например, 98 * 98 * 97, поскольку все остальное отменяет).

0

Here. Самый быстрый, прямо из Факториала - Петр Лушный.

Смежные вопросы