Расчет больших факториалов (до 100000 !!!!!)

← →
Serega_M (2002-02-14 21:58) [0]

Уважаемые мастера!!! Помогите решить проблему с расчетом факториалов больших чисел (до 100 000 может и более). При использовании типа EXTENDED, максимум что моге посчитать это факториал 1750. Window-ый калькулятор считает!!!. Можно-ли это сделать в Дельфях. Если приведете кусочек кода буда очень признетелен. Если можете мыльте.

Краткая математическая справка: Факториал числа N вычисляется по следующей формуле 1*2*3*...(N-1)*N, факториал 0 равен 1.

Заранее спасибо.С уважением Serega.

← →
Kurt (2002-02-15 00:27) [1]

Используй "длинную арифметику" - число представляется масивом своих цыфр. Имееш большой масив иожеш считать любой фаеториал.

← →
MBo © (2002-02-15 06:52) [2]

поищи FGINT

← →
Serega_M (2002-02-15 10:29) [3]

для Kurt`а ______ Если можно -поподробней !!! Как использовать массив цифр и производить вычисление? Писал процедуру расчета факториала для больших чисел. Числа представлял в виде текста или массива PCHAR.Перемножение и сложение происходило между отдельными цифрами. По-типу умножения в 1-ом классе (столбиком). Расчет факториала 20000 занял часов 6. Очень долго не находите :)

для МВо ________ что такое FGINT? Функция API или Делфей?

← →
fag2000@ok.ru © (2002-02-15 10:32) [4]

А сколько цифр было получено?
Может есть смысл хранить мантису и показатель степени?

← →
Вячеслав © (2002-02-15 10:41) [5]

Воспользуйся формулой Стирлинга.

← →
Вячеслав © (2002-02-15 10:47) [6]

P.S. Посмотри тут.
http://algolist.by.ru/maths/count_fast/factorial.html

← →
Alx2 © (2002-02-15 10:53) [7]

Вот приближение десятичного логарифма факториала:
#include <math.h> double log10factorial(n) double n; { double t1; double t15; double t17; double t2; double t23; double t25; double t3; { t1 = n*n; t2 = t1*n; t3 = t1*t1; t15 = log(902961561600.0*t3*t2+75246796800.0*t3*t1+3135283200.0*t3*n -2421135360.0*t3-207204480.0*t2+707957280.0*t1+62961828.0*n-534703531.0); t17 = log(n); t23 = log(0.3141592653589793E1/0.4076697908635553E24); t25 = log(10.0); return((2.0*t15-13.0*t17+2.0*n*t17-2.0*n+t23)/t25/2.0); } }
Естественно, целая часть этого покажет количество знаков числа+1, а с мантиссой можно работать.
Исходная формула (аппроксимация факториала):
n! ~ 1/902961561600*sqrt(2)*sqrt(Pi)*(902961561600*n^7+75246796800*n^6+3135283200*n^5-2421135360*n^4-207204480*n^3+707957280*n^2+62961828*n-534703531)*n^(-13/2+n)*exp(-n)

← →
Serega_M (2002-02-15 11:23) [8]

Какой тип переменных использовать расчетов большого факториала (например 10E+23541)?

← →
Alx2 © (2002-02-15 11:34) [9]

используй логарифмическую шкалу.
Поправлю себя:
Следует читать (пред. мое сообщение)
"Естественно, целая часть этого покажет количество знаков числа -1, а с мантиссой можно работать"

← →
MBo © (2002-02-15 13:26) [10]

вопрос- надо получить все верные цифры или хорошее приближение?
если первое - отлично подойдет, как уже сказали, формула Стирлинга.
Если второе - FGINT - это библиотека,
http://triade.studentenweb.org
Факториал 20000 считает 20 сек.
100 000! - 14 минут (Р600)
только в строку не может преобразовать такое число ;(

← →
Slinker (2002-02-17 04:03) [11]

Программа, приведенная здесь для вычисления логарифма, у меня выдает для 20000! около 74 тыс знаков, когда их всего 19тыс.

← →
Slinker (2002-02-17 13:09) [12]

FGInt - ламерская тормозная либа.

Расчет факториала, например, на http://algonew.manual.ru/maths/count_fast/factorial.php

>FGInt - ламерская тормозная либа
напиши лучше, народ, которому это надо, тебя не забудет, а так ламерским является твое заявление

← →
Slinker (2002-02-18 01:30) [14]

Давай без личных наездов 8).

Крутую либу писать не буду, так как это мне, во-первых, не интересно, а, во-вторых, они уже написаны. Например, Freelip.

Если честно - либу я написал, работает она асимптотически быстрее, чем FGInt, если нужно - дам линк, но она больше для учебных целей написана. А так - крутая либа GNU, например.

Ламерской я назвал FGInt просто потому, что под видом умных люди реализовывают "Fast" алгоритмы без сколь-ко либо серьезных попыток оптимизации.

ОК.
Да, написаны, но приличные - на Cях.
Информации мало, видимо, из-за того, что это сфера интересов криптографии.

>Slinker (17.02.02 04:03)
>Программа, приведенная здесь для вычисления логарифма,
>у меня выдает для 20000! около 74 тыс знаков,
>когда их всего 19тыс.
Неверно. Знаков этого числа больше чем 68895.
Доказательство:
Рассмотрим ряд:
1^(10-1)*10^(100-10)*100^(1000-100)*1000^(10000-1000)*10000^(20000-10000+1)=10^68894<20000!
Этот ряд получается следующей заменой:
вместо
1*2*3*4*5*6*7*8*9 пишем 1*1*1*1*1*1*1*1*1 (9 раз)
вместо 10*11*12*13*14*15*...*99 пишем 10*10*10*...*10 (90 раз)
вместо 100*101*...*999 пишем 100*100*..*100(900 раз)
и так далее.
Очевидно, что наш ряд меньше, чем ряд 1*2*3*...*20000.
Но в нашем ряде уже 68895 цифр!

>Slinker (17.02.02 04:03)
>когда их всего 19тыс.
В догонку:
Еще один способ "в лоб":
просуммируем логарифмы чисел от 1 до 20000 и полученную сумму разделим на ln(10). При этом получим десятичный логарифм факториала 20000. Это примерно 77337.26. То есть всего 77338 цифр. Откуда все-таки взялись ваши 19 тысяч?

← →
Slinker (2002-02-18 15:25) [18]

Каюсь..
19 тысяч взялись от вычислений по основанию 10000 ...

На самом деле там их ровно 77338, прога - 77337.259882

Длина 100000! 456574, прога - 456573.450900
Хорошо работает, собака :)

Расчет больших факториалов (до 100000 !!!!!) Найти похожие ветки