информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Страшный баг в WindowsЗа кого нас держат?Где водятся 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
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Похоже, что все 308 и потребуются. 30.03.05 12:19  Число просмотров: 3328
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 30.03.05 12:50  Количество правок: 1
<"чистая" ссылка>
> Я понял. В этой формуле первые два члена "отвечают" за
> быстрое вычисление,
> а последний, то что я неправильно назвал полиномом,
> (1+12/n+1/(288n^2)...),
> "отвечает" за точность. Так если 4 члена обеспечивают
> точность в -4, то 308 членов могут обеспечить точность 308
> знаков? Тогда для искомого вычисления факториала
> неизвестными остаются только эти члены.

Похоже, что все 308 и потребуются. И столько же заранее навычислять коэффициентов. И желательно убедиться, чтоб коэффициенты стремились к константе. Но все равно коэффициенты уточнять надо. Эта формула для простоты, а в достаточно точной может измениться уже второй член - вместо 1/12n станет 1/12.0000001n, например.
А последний и последующие члены не указываются, а пишется, что они не превысят по абсолютному значению 10 в -4 степени. Причем точность приводится к значению. Хотя можно привести и к аргументу, но это менее актуально.

> К тому, что если вычислять факториал, то это эквивалент
> ряда 1*2*3*...*100. И его приближенное значение
> как 50^50 будет очень не точным (разница в пару десятков
> порядков).
> А если вычислять "частичный факториал" т.е. произведение,
> начинаемое не с 1, а с 101, и для "корректности сравнения",
> тоже из 100 членов, 101*102*...*200, то его приближенное
> значение в 150^50 будет существенно точнее.
> Возвращаясь к исх. задаче и приближенной формуле: Есть
> число N, надо найти k!, где k~корень(N), с учетом того, что
> один из множителей принадлежит диапазону от 1 до k. Так вот
> если значение k! приближенно расчитывать, как
> (k/2)^(k/2), то оно от реального будет отличаться на пару
> порядков.
> А если считать произведение от (k/4) до (k/2), то его
> значение приближенное значение как (k*3/4)^(k/4) будет
> существенно точнее. И цена за такое существенное увеличение
> будет "всего" вдвое уменьшение шансов.

Многие любят апроксимировать полиномом, поскольку им можно проапроксимировать что угодно и это сделать намного проще, особенно когда сама функция неизвестна.
В случае с факториалом все намного хуже, поскольку пока не придумана короткая аналитическая функция по которой можно было бы его вычислять. В добавок ко всему он слишком быстро "растет". Стало быть для достаточно точного вычисления значений больших аргументов потребуется большое количество членов полинома. Мало того, эти числа будут иметь большую разрядность. Трудоемкость задачи слишком возрастает.
Буду краток. Мне кажется то, о что вы пишете очень похоже на увеличение точности на том участке, где исходная функция ведет себя более похожим образом на (k/m)^(k/n). Ну да, либо точность будет выше, либо количество членов полинома можно уменьшить. А как быть, если потребуется вычислить значение от в милиарды раз бОльшего аргумента? Здесь о точности и речи быть не может.
Это похоже на такой вариант: Возмем большое число. Вычислим значение в этой и соседних точках. Проинтерполируем прямой (y=ax+b), а лучше параболой (y=ax^2+bx+c). И как легко и просто, а главное точно, будет вычислять значения, если аргумент не будет сильно отличаться от нашего первоначально выбранного, ведь короткий участок факториала будет очень похож на прямую, ну уж наверняка на параболу в области больших значений.
Можно, конечно вычислить коэффициенты для значений не очень сильно отстоящих друг от друга. Но сколько их будет на огромном интервале. Мало того, чтоб их вычислить, надо иметь несколько значений самой функции в этой области, а мы и одного значения никогда не получим.
Единственный вариант - некоторая простая функция с малым количеством коэффициентов, которая даст высочайшую точность на всем участке маленьких чисел. Тогда можно предположить, что и в области больших значений точность может быть в разумных пределах.
<theory> Поиск 








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


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