Форум: "Основная";
Поиск по всему сайту: 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.035 c
