Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 14.04.2009, 20:56
_persicum_

 
Сообщений: n/a

Вычисление факториала ;)
Озадачился вычислением факториала. Вернее, нужно было вычислить длинный полином (x-a)(x-b)(x-c)... Но потом смекнул, что тут по сути применим алгоритм быстрого вычисления факториала.

Так вот, просто удивительно, что тут на сайте в разделе про быстрые вычисления притаилась такая лажа, просто жуть! Повторяя слова автора сего опуса - вешать за такое мало!!!

Я тоже сначала думал, что последовательные умножения стандартного типа на длинный тип имеют O(n), но обнаружив непонятные и неслабые тормоза, при пошаговом просмотре обнаружил сложность O(n^2), а O(n) имеет только однократное умножение длинного типа на простой, но тут у нас их много!

Задачу решил через быстрые умножения и деления массива пополам, получилось N log^2 N

Наверное, можно еще делить массив на четыре части и умножать через Карацубу

История напоминает реализацию FFT, причем оказывается что РЕКУРСИВНЫЙ алгоритм фычисления факториала не так уж плох =))) и куда лучше последовательных умножений.
  #2  
Старый 15.04.2009, 16:40
гость

 
Сообщений: n/a

Ммда, тяжелый случай...
  #3  
Старый 15.05.2009, 04:10
SaveTheRbtz

 
Сообщений: n/a

Во многих случаях для приближенного значения факториала достаточно рассматривать только главный член формулы Стирлинга:


(c)wiki http://ru.wikipedia.org/wiki/%D0%A4%...%D0%B0%D 0%BB
  #4  
Старый 16.05.2009, 10:13
Пользователь

Отправить личное сообщение для persicum Посмотреть профиль Найти все сообщения от persicum
 
Регистрация: 11.01.2007
Сообщений: 28

Я тебе больше скажу, для многих задач теоретической и статистической физики достаточно полагать, что

ln n! = n ln n - n

Но для ряда задач криптографии и кодирование необходимо уметь вычислять факториал абсолютно точно, причем не по модулю, а целиком.

Давай прикинем, сколько десятичных знаков будет иметь 1000000! ?

Это 1000000*lg 1000000 = 6 млн. знаков

А если вычислять его в цикле, то понадобится порядка 10^11 операций умножения. Поэтому для точного вычисления факториала необходимы алгоритмы быстрого умножения, несмотря на то, что 1000000 это число всего лишь одинарной точности
  #5  
Старый 20.10.2010, 22:34
гость

 
Сообщений: n/a

Сообщение от SaveTheRbtz Посмотреть сообщение
Во многих случаях для приближенного значения факториала достаточно рассматривать только главный член формулы Стирлинга:


(c)wiki http://ru.wikipedia.org/wiki/%D0%A4%...%D0%B0%D 0%BB
Помогите решить эту эадачку плиз факториал!

y=1+x+x2/2!+x3/3!+....
  #6  
Старый 21.10.2010, 11:51
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

y = exp ( x )
  #7  
Старый 22.10.2010, 07:17
Пользователь

Отправить личное сообщение для maxal Посмотреть профиль Найти все сообщения от maxal
 
Регистрация: 28.11.2006
Сообщений: 68

На васме была большая дискуссия о вычислении факториала:
http://wasm.ru/forum/viewtopic.php?id=20626
  #8  
Старый 29.10.2010, 12:49
$persicum$

 
Сообщений: n/a

В целом обсуждение бредъ, но есть одна здравая мысля - если уметь быстро вычислять факториал по модулю то можно быстро и элементарно разлагать на множители. И еще мысля - можно было бы легко доказывать простоту числа.

Вот тока совсем уж быстрый алгоритм факториала не существует. А для степени как известно существует.
  #9  
Старый 10.11.2010, 02:51
гость

 
Сообщений: n/a

алгоритм
У меня есть быстрый алгоритм, но приближённый, естественно.
Факториал находит за миллисекунды, типа 1E+9!=9.9E+8565705522
  #10  
Старый 10.11.2010, 03:47
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
У меня есть быстрый алгоритм, но приближённый, естественно.
Факториал находит за миллисекунды, типа 1E+9!=9.9E+8565705522
баян
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Вычисление пересечения vilza Реализация, исходники, языки 7 30.01.2009 16:58
вычисление параметра t кривой Безье гость Математические алгоритмы 3 21.07.2008 23:46
Вычисление внутренних паттернов seregarem Математические алгоритмы 0 06.03.2008 09:36
Вычисление выражений Andrew Математические алгоритмы 1 27.08.2007 00:45
вычисление первообразной функции гость Математические алгоритмы (другое) 2 24.06.2007 12:43