Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Было бы возможно, факториал любого числа равнялся бы... 24.03.05 19:57 Число просмотров: 4566
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 24.03.05 20:01 Количество правок: 1
|
> Здесь невозможно получить одинаковые значения. 8(
Было бы возможно, факториал любого числа равнялся бы возведению целого числа в целую степень 8(.
> Это я понял. :) Осталось всего ничего.
Кто знает...
> Я попробовал начать сворачивать от середины. Если я
> правильно посчитал, то произведение четырех членов ряда
> можно получить за 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))
> Ежели, конечно, я нигде не ошибся.
Суть то не в том, что можно чуть быстрее сворачивать. Все равно весь ряд сворачивать не надо. Для десятикратного сворачивания достаточно получить десяток значений. Пусть для этого потребуется даже десять тысяч перемножений и пять тысяч вычитаний для вычисления приращений. Главное потом для вычисления очередного значения свернутого ряда достаточно будет десяток сложений и членов ряда будет меньше в тысячу раз.
Однако этот метод хоть и может быть более быстрым, но не годится для нахождения факториала по модулю для килобитных чисел. Максисум для 64 битных, поскольку для сокращения ряда в миллион раз потребуется хранить в оперативке два-три десятка восьмимегабайтных чисел. Количество перемножений хоть и сократится в милион раз, все равно останется 18 трилионов. Нужно что-то упрощать.
Над приближенным вычислением подумаю, им тоже можно воспользоваться.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
