информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Портрет посетителяГде водятся OGRы
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Простое пробивание рабочего/провайдерского... 
 400 уязвимостей в процессорах Snapdragon 
 Яндекс неуклюже оправдался за установку... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Пишу, вот. Придумать формулу для приближенного вычисления... 22.03.05 12:22  Число просмотров: 7660
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
<"чистая" ссылка>
> А) Идея хоршоая, но не нова. см. cryptography.ru
> Б) Есть формула ПРИБЛИЖЕННОГО вычисления факториала.
> называется формула Стерлинга (стрилинга). См. Д. Кнут
> "Исскуство программирования". Формула в одну строчку, без
> рядов и рекурсий.
> Есть одна проблема - приближенное. Боюсь приближенность
> (читай неточность) вычисленного факториала будет намного
> выше, чем само число N.
> Если интересно пиши.

Пишу, вот. Придумать формулу для приближенного вычисления факториала не проблема. Причем чем проще формула, тем меньше точность.
Мало того, она не будет применима для вычисления факториала килобитного числа - размерность результата астрономическая.
Так что Стерлинг здесь не применим.
Поиск по сайту ничего приличного не дал. Облазить все форумы, ЧАВО, научные статьи, обзоры, заметки, рефераты времени не хватит.
Поиск по поисковикам на тему быстрого вычисления факториала по модулю ничего не дал.
Вспомнил я про вычисления суммы арифметической прогрессии. Там используется свертка пополам для получения ряда одинаковых значений. Сумма вычисляется легко значение умножается на длину свернутого ряда.
Хотел то же самое для факториала придумать. Связь просматривается: там сумма, здесь произведение; там произведение, здесь возведение в степень; по модулю перемножать и возводить в степень не проблема.
Попробовал - свернул кусок натурального ряда по принципу первый умножаем на последний, второй на предпоследний. Хотел как у арифметической прогрессии получить что-то постоянное, тогда просто бы в степень возвел и все. Увы - только вторая или третья "производная" обнулилась. Свернул еще пополам уже свернутый ряд - следующая "производная" обнулилась.
Под "производной" я имею в виду приращение значения. Приращение аргумента здесь равно единицы. О пределах пока речи не ведем.
Одно пока понял: десяток раз свернем - сам ряд в тысячу раз сократится, два десятка - в милион. Для вычисления факториала достаточно получить первых N значений и вычислить N-1 приращений, N-2 приращений приращений, ... и так до нулевых приращений. Тогда для получения очередного значения сначала вычисляет N-1 производную прибавляя к ее предыдущему значению Nую производную, потом новую N-2, прибавив к ее старому значению новую N-1, ... и так N раз до получения нового значения свернутого ряда. Итого N сложений. Разумеется полученный член ряда умножаем на произведение всех предыдущих, а храним только остаток от деления.
Короче мне думается, что быстрое вычисление факториала по модулю реально и находится где-то в этом направлении.
<theory> Поиск 








Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2020 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach