ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergey Kovalev                       2:5020/400     20 Oct 2001  09:21:50
 To : Max Alekseyev
 Subject : Re: Огромные числа
 -------------------------------------------------------------------------------- 
 

 
 "Max Alekseyev" <Max.Alekseyev@f60.n5015.z2.fidonet.org> wrote in message
 news:1003503875@f60.n5015.z2.ftn...
 []
 
 >
 >  SS>  Если твое число из 100 десятичных цифр, то точного ответа от решета
 >  SS> Эратосфена ты будешь ждать несколько лет. А Рабин-Миллер даст тебе
 >  SS> ответ с вероятностью 2^(-N), где N задаешь ты сам. Думаю 2^-100 будет
 >  SS> достаточно ;)
 >
 > Точнее 4^(-N), где N - число раундов.
 
 Должан сразу сказать, что с этим алгоритмом знаком
 весьма поверхностно и специальной литературы на эту тему не читал.
 Поэтому следующие вопросы могут быть весьма "чайниковыми".
 1. Почему 4^(-N) ? Для независимых событий более естественно
 выглядит что-нибудь типа 1-(1-1/4)**N.
 2. Hе очень понятно, какой физический смысл этой вероятности,
 когда она становиться сильно меньше чем 1/(проверяемое число).
 SK
 SPb
 --- ifmail v.2.15dev5
  * Origin: HOME (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Огpомные числа   Victor Anikeev   20 Oct 2001 01:41:30   Re: Огpомные числа   Sergey Kovalev   19 Oct 2001 19:40:09   Огpомные числа   Stanislav Shwartsman   19 Oct 2001 18:35:21   Re: Огpомные числа   Sergey Kovalev   19 Oct 2001 23:39:47   Огpомные числа   Stanislav Shwartsman   19 Oct 2001 22:59:08   Огромные числа   Max Alekseyev   19 Oct 2001 15:03:12   Re: Огромные числа   Sergey Kovalev   20 Oct 2001 09:21:50   Re: Огромные числа   Sergey Kovalev   20 Oct 2001 09:34:03   Огромные числа   Dovlet Tatlok   20 Oct 2001 11:30:53   Огpомные числа   Andrew Plyako   21 Oct 2001 01:00:10   Re: Огpомные числа   Zapadinsky Anatoly \\(ZAB\\)   19 Oct 2001 22:00:03   Огpомные числа   Victor Anikeev   20 Oct 2001 10:06:56   Огpомные числа   Stanislav Shwartsman   20 Oct 2001 10:04:24   Огpомные числа   Victor Anikeev   20 Oct 2001 22:13:36   Огpомные числа   Stanislav Shwartsman   20 Oct 2001 14:20:12   Огpомные числа   Ilia Kantor   20 Oct 2001 22:32:38   Пpизнаки делимости   Ilia Kantor   21 Oct 2001 00:28:00   Делимость на 7 Re: Огpомные числа   Sergei Zubkov   20 Oct 2001 23:40:57