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