Форум: "Основная";
Поиск по всему сайту: delphimaster.net;
Текущий архив: 2002.03.07;
Скачать: [xml.tar.bz2];




Вниз

Расчет больших факториалов (до 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



MBo   (2002-02-17 13:19) [13]

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



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


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

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

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

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



Mbo   (2002-02-18 06:42) [15]

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



Alx2   (2002-02-18 08:24) [16]

>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 цифр!



Alx2   (2002-02-18 10:20) [17]

>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
Хорошо работает, собака :)




Форум: "Основная";
Поиск по всему сайту: delphimaster.net;
Текущий архив: 2002.03.07;
Скачать: [xml.tar.bz2];




Наверх





Память: 0.75 MB
Время: 0.25 c
3-19090           DimaIv                2002-02-08 16:52  2002.03.07  
Возможно ли при помощи процедуры AppendRecord ничего


6-19270           Cepera                2001-12-04 01:26  2002.03.07  
Дьявольские API функции для посчета траффика


1-19148           Елена                 2002-02-18 14:56  2002.03.07  
Закрытие ДОС-окна


3-19083           MZ                    2002-02-07 17:46  2002.03.07  
Как программно получить список псевдонимов баз данных???


3-19044           HDD                   2002-02-07 15:50  2002.03.07  
Помогите пожалуйста дамы и господа