Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
А можешь придумать сложную, но точность выше? (отступление... 24.03.05 16:45 Число просмотров: 4298
Автор: Searcher Статус: Незарегистрированный пользователь
Отредактировано 24.03.05 20:50 Количество правок: 1
|
> Пишу, вот. Придумать формулу для приближенного вычисления
> факториала не проблема. Причем чем проще формула, тем
> меньше точность.
А можешь придумать сложную, но точность выше? (отступление от темы)
> Вспомнил я про вычисления суммы арифметической прогрессии.
> Там используется свертка пополам для получения ряда
> одинаковых значений. Сумма вычисляется легко значение
> умножается на длину свернутого ряда.
Здесь невозможно получить одинаковые значения. 8(
> Для вычисления
> факториала достаточно получить первых N значений и
> вычислить N-1 приращений, N-2 приращений приращений, ... и
> так до нулевых приращений. Тогда для получения очередного
> значения сначала вычисляет N-1 производную прибавляя к ее
> предыдущему значению Nую производную, потом новую N-2,
> прибавив к ее старому значению новую N-1, ... и так N раз
> до получения нового значения свернутого ряда. Итого N
> сложений. Разумеется полученный член ряда умножаем на
> произведение всех предыдущих, а храним только остаток от
> деления.
Даже, если это будут только сложения, у тебя их слишком много получется.
> Короче мне думается, что быстрое вычисление факториала по
> модулю реально и находится где-то в этом направлении.
Это я понял. :) Осталось всего ничего.
Я попробовал начать сворачивать от середины. Если я правильно посчитал, то произведение четырех членов ряда можно получить за 2 умножения и 2 сложения.
Пусть нужно вычислить (x-a(x-(a-1))... (x-1x*(x+1)...(x+(a-1))x+a)
(x-a)*(x+a)=x*x-a*a,
аналогично
(x-(a-1)(x+(a-1))=x*x-(a-1)a-1),
получается "половинный" ряд
x*(x*x-1*1)*...(x*x-a*a) т.е "a" членов, вместо "2*а+1"
пусть b- число, ~ a/2, t - число от 1 до a/2
берем пару (x*x-(b-t(b-t))*(x*x-(b+t)b+t)) = (далее значком ^ обозначаем возведение в степень)
=x^4-x^2*((b-t)^2)-x^2*((b+t)^2)+((b+t)^2)*((b-t)^2)=
=x^4-x^2(b^2-2*b*t+t^2+b^2+2*b*t+t^2)+(b^2-t^2)^2=
=x^4-x^2(2*b^2+2*t^2)+b^4-2*b^2*t^2+t^4=
=x^4-x^2*2*b^2+b^4-x^2*2*t^2-2*b^2*t^2+t^4=
=x^4-x^2*2*b^2+b^4 + t^2*(t^2-2*x^2-2*b^2)=
const1 + t^2* (t^2 - const2)
итого две предварительных константы и
1 умножение t^2,
2 умножение t^2*(...)
и два сложения.
Вместо исходных трех (x-(b+t)(x+(b+t))*(x-(b-t))x+(b-t))
Ежели, конечно, я нигде не ошибся.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
