Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Извини, не правильно понял. 27.03.05 23:48 Число просмотров: 4536
Автор: Searcher Статус: Незарегистрированный пользователь
|
> Суть то не в том, что можно чуть быстрее сворачивать. Все
> равно весь ряд сворачивать не надо.
Извини, не правильно понял.
Я думал про арифметическую прогрессию, где основное свойство ряда а
а(x-1)-a(x)=a(x)-a(x+1)=dx.
откуда а(x-1)+a(x+1)=2а(х) и а(x-y)+a(x+y)=2а(х).
поэтому я и рассматривал проивзедение (x+y)(x-y)=x*x-y-y.
Я просто хотел попробовать "свернуть" часть ряда, чтобы быстрее его вычислить. Надеялся, что если свернуть 8 членов можно будет выиграть еще операций. В теории,
если бы удалось для них получить многочлен вида x^8+k1*x^4+k2*x^2+k3. То был бы дополнительный выигрыш. И если бы тенденция сохранилась, то 2^m членов свернулось бы к полиному m-ой степени. :)
Не получается. :( :)
>Для десятикратного
> сворачивания достаточно получить десяток значений. Пусть
> для этого потребуется даже десять тысяч перемножений и пять
> тысяч вычитаний для вычисления приращений. Главное потом
> для вычисления очередного значения свернутого ряда
> достаточно будет десяток сложений и членов ряда будет
> меньше в тысячу раз.
> Однако этот метод хоть и может быть более быстрым, но не
> годится для нахождения факториала по модулю для килобитных
> чисел. Максисум для 64 битных, поскольку для сокращения
> ряда в миллион раз потребуется хранить в оперативке два-три
> десятка восьмимегабайтных чисел. Количество перемножений
> хоть и сократится в милион раз, все равно останется 18
> трилионов. Нужно что-то упрощать.
??? не понял, это про сворачивание, или про то, что я предложил?
> Над приближенным вычислением подумаю, им тоже можно
> воспользоваться.
Один из вариантов - если иметь приближенное значение, то можно пытаться искать тот самый НОД в некотором диапазоне от числа. Главное, чтобы приближение было в разумных пределах, а не районе корня (N).:)
Кстати, ты ничего не слышал о
"Дэниэл Бернстайн (Daniel Bernstein) опубликовал статью, где описал новый метод вычисления факториалов больших чисел"
http://www.pcsamara.ru/news.phtml?n=3&day=13&m=4&y=2002&mode=prev
И о формуле Стирлинга
http://ru.wikipedia.org/wiki/Формула_Стирлинга#.D0.A4.D0.BE.D1.80.D0.BC.D1.83.D0.BB.D0.B0_.D0.A1.D1.82.D0.B8.D1.80.D0.BB.D0.B8.D0.BD.D0.B3.D0.B0
ее "неприменимость" определяется,как мне кажется ,кроме неточности,
вычислением степени т.е. (n/e)^n, однако, если учесть, что нам нужно
значение факториала по модулю, то
можно было бы рассчитать (n/e)^n mod n. Как поделить (n/e)^n на n - ясно - это
(n/e)^(n-log по основанию n/e от n). Неясно, как остаток получить. :)
|
|
|
подробно о проекте
Анализ криптографических сетевых...
