воскресенье, 11 октября 2015 г.

Вычисление постоянных Бруна (ч.1)

В предыдущем посте писал о поиске ("просеивании") простых чисел в заданном интервале. Сегодня могу рассказать для чего это было сделано, какие проблемы возникают и как их будем решать в дальнейшем. 
Речь пойдет о вычислении с некоторой точностью постоянной Бруна. В Википедии говорят что это число крайне трудно вычислимо. Если смотреть на определение, то это сходящийся ряд. Говоря математическим языком, можно описать трудности вычисления как медленно сходящийся ряд. Крайне медленно.

В школах и вузах многие писали программы, которые вычисляют суммы некоторых рядов с заданной точностью. Давайте, посчитаем какой-нибудь ряд. Мы не будем оценивать скорость роста знаменателей, мы все знаем что рост экспоненциальный и, значит, ряд из обратных величин будет сходиться довольно быстро. Но раз мы не оцениваем, то как мы можем сказать когда мы посчитали наше значение с нужной точностью? Для этого можно просто взять и оценить слагаемое - если оно меньше нашей требуемой точности, а в силу экспоненциальности роста знаменателей последующие слагаемые будут ещё меньше, то можно остаток бесконечного ряда просто отбросить. 

Если запустить такую программу, отработав пару секунд она выдаст значение 3.359885666243177553172011302918927179688905133731968486495553815325130318996683383615416216456790085 с точностью, до 100 знаков и число обработанных слагаемых 475. Собственно, для вычисления 475 слагаемых нам совершенно не надо заботиться о скорости вычисления - точность ставим во главу и потом используем Fraction и лишь в конце преобразуем результат в Decimal для пущей сохранности точности.

Итак, чтобы посчитать с 100-значной точностью данную постоянную мы были вынуждены перед этим посчитать 475 чисел Фибоначчи. Так как нам всё равно они были нужны все, считали мы по определению через суммы, что облегчило процесс вычисления. Но давайте посмотрим на постоянную Бруна. В отличие от чисел Фибоначчи, здесь используются в суммирование простые числа. Никакой закрытой формы для их вычисления нет - можно находить лишь по определению. К тому же, это ведь не просто обычные простые числа - а простые с дополнительными свойствами - близнецы. И вот тут нас подстерегает неприятный сюрприз - ряд из обратных простым числам-близнецам величин сходится ужасно медленно - линейно или "чуть-чуть" быстрее и потому очень трудно отбросить бесконечный хвост из-за того, что сложно его оценить. При вычислениях мы будем использовать тот же прием с Fraction потому, что для постоянных Бруна (о да, мы сразу посчитаем три постоянные: для близнецов, для простых четверок и для простых чисел-кузенов) потеря точности весьма критична. Кроме всего прочего, мы задействуем ещё и многоядерность современных процессоров для большей эффективности вычисления.
Результаты многих прогонов программы и долгих часов вычислений позволило собрать такие данные: И что же мы видим? При увеличении числа слагаемых на порядок (!) точность лишь слегка возрастает: обработав по 1млрд слагаемых (на самом деле это верхняя граница просеивания - реальных слагаемых меньше), мы нигде не смогли обеспечить точность даже порядка 0.01. Поистине ряд сходится медленно! И видно, что действовать по определению в математике далеко не всегда выгодно для вычислений.

Сейчас мы строго показали, что
B2 > 1.7747359576,
B4_c > 1.069621337,
B4_q > 0.8699668564.

В следующем посте мы попытаемся несколько ускорить данную программу и, возможно, добавим данные для 10 и 100млрд слагаемых, а так же поговорим о других методах вычисления этих постоянных.

3 комментария:

  1. Этот комментарий был удален администратором блога.

    ОтветитьУдалить
  2. Этот комментарий был удален администратором блога.

    ОтветитьУдалить
  3. Этот комментарий был удален администратором блога.

    ОтветитьУдалить