Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Расчет больших факториалов (до 100000 !!!!!) [D5, Win95/98]

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

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

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

Slinker (2002-02-18 15:25:00) [1]

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

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

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

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

Alx2 (2002-02-18 08:24:00) [3]
>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 цифр!

Mbo (2002-02-18 06:42:00) [4]
ОК.
Да, написаны, но приличные - на Cях.
Информации мало, видимо, из-за того, что это сфера интересов криптографии.

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

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

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

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

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

MBo (2002-02-17 13:19:00) [6]
>FGInt - ламерская тормозная либа
напиши лучше, народ, которому это надо, тебя не забудет, а так ламерским является твое заявление

Slinker (2002-02-17 13:09:00) [7]
FGInt - ламерская тормозная либа.

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

Slinker (2002-02-17 04:03:00) [8]
Программа, приведенная здесь для вычисления логарифма, у меня выдает для 20000! около 74 тыс знаков, когда их всего 19тыс.

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

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

Serega_M (2002-02-15 11:23:00) [11]
Какой тип переменных использовать расчетов большого факториала (например 10E+23541)?

Alx2 (2002-02-15 10:53:00) [12]
Вот приближение десятичного логарифма факториала:
#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)

Вячеслав (2002-02-15 10:47:00) [13]
P.S. Посмотри тут.
http://algolist.by.ru/maths/count_fast/factorial.html

Вячеслав (2002-02-15 10:41:00) [14]
Воспользуйся формулой Стирлинга.

fag2000@ok.ru (2002-02-15 10:32:00) [15]
А сколько цифр было получено?
Может есть смысл хранить мантису и показатель степени?

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

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

MBo (2002-02-15 06:52:00) [17]
поищи FGINT

Kurt (2002-02-15 00:27:00) [18]
Используй "длинную арифметику" - число представляется масивом своих цыфр. Имееш большой масив иожеш считать любой фаеториал.

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »