Вычисление N-го знака числа Пи без вычисления предыдущих

С недавних пор существует элегантная формула для вычисления числа Пи, которую в 1995 году впервые опубликовали Дэвид Бэйли, Питер Борвайн и Саймон Плафф:
image

Казалось бы: что в ней особенного — формул для вычисления Пи великое множество: от школьного метода Монте-Карло до труднопостижимого интеграла Пуассона и формулы Франсуа Виета из позднего Средневековья. Но именно на эту формулу стоит обратить особое внимание — она позволяет вычислить n-й знак числа пи без нахождения предыдущих. За информацией о том, как это работает, а также за готовым кодом на языке C, вычисляющим 1 000 000-й знак, прошу под хабракат.

Как же работает алгоритм вычисления N-го знака Пи?
К примеру, если нам нужен 1000-й шестнадцатеричный знак числа Пи, мы домножаем всю формулу на 16^1000, тем самым обращая множитель, стоящий перед скобками, в 16^(1000-k). При возведении в степень мы используем двоичный алгоритм возведения в степень или, как будет показано в примере ниже, возведение в степень по модулю. После этого вычисляем сумму нескольких членов ряда. Причём необязательно вычислять много: по мере возрастания k 16^(N-k) быстро убывает, так что, последующие члены не будут оказывать влияния на значение искомых цифр). Вот и вся магия — гениальная и простая.

Формула Бэйли-Борвайна-Плаффа была найдена Саймоном Плаффом при помощи алгоритма PSLQ, который был в 2000 году включён в список Top 10 Algorithms of the Century. Сам же алгоритм PSLQ был в свою очередь разработан Бэйли. Вот такой мексиканский сериал про математиков.
Кстати, время работы алгоритма — O(N), использование памяти — O(log N), где N — порядковый номер искомого знака.

Думаю, уместно будет привести код на языке Си, написанный непосредственно автором алгоритма, Дэвидом Бэйли:

/*  
    This program implements the BBP algorithm to generate a few hexadecimal
    digits beginning immediately after a given position id, or in other words
    beginning at position id + 1.  On most systems using IEEE 64-bit floating-
    point arithmetic, this code works correctly so long as d is less than
    approximately 1.18 x 10^7.  If 80-bit arithmetic can be employed, this limit
    is significantly higher.  Whatever arithmetic is used, results for a given
    position id can be checked by repeating with id-1 or id+1, and verifying 
    that the hex digits perfectly overlap with an offset of one, except possibly
    for a few trailing digits.  The resulting fractions are typically accurate 
    to at least 11 decimal digits, and to at least 9 hex digits.  
*/

/*  David H. Bailey     2006-09-08 */

#include <stdio.h>
#include <math.h>

int main()
{
  double pid, s1, s2, s3, s4;
  double series (int m, int n);
  void ihex (double x, int m, char c[]);
  int id = 1000000;
#define NHX 16
  char chx[NHX];

/*  id is the digit position.  Digits generated follow immediately after id. */

  s1 = series (1, id);
  s2 = series (4, id);
  s3 = series (5, id);
  s4 = series (6, id);
  pid = 4. * s1 - 2. * s2 - s3 - s4;
  pid = pid - (int) pid + 1.;
  ihex (pid, NHX, chx);
  printf (" position = %i\n fraction = %.15f \n hex digits =  %10.10s\n",
  id, pid, chx);
}

void ihex (double x, int nhx, char chx[])

/*  This returns, in chx, the first nhx hex digits of the fraction of x. */

{
  int i;
  double y;
  char hx[] = "0123456789ABCDEF";

  y = fabs (x);

  for (i = 0; i < nhx; i++){
    y = 16. * (y - floor (y));
    chx[i] = hx[(int) y];
  }
}

double series (int m, int id)

/*  This routine evaluates the series  sum_k 16^(id-k)/(8*k+m) 
    using the modular exponentiation technique. */

{
  int k;
  double ak, eps, p, s, t;
  double expm (double x, double y);
#define eps 1e-17

  s = 0.;

/*  Sum the series up to id. */

  for (k = 0; k < id; k++){
    ak = 8 * k + m;
    p = id - k;
    t = expm (p, ak);
    s = s + t / ak;
    s = s - (int) s;
  }

/*  Compute a few terms where k >= id. */

  for (k = id; k <= id + 100; k++){
    ak = 8 * k + m;
    t = pow (16., (double) (id - k)) / ak;
    if (t < eps) break;
    s = s + t;
    s = s - (int) s;
  }
  return s;
}

double expm (double p, double ak)

/*  expm = 16^p mod ak.  This routine uses the left-to-right binary 
    exponentiation scheme. */

{
  int i, j;
  double p1, pt, r;
#define ntp 25
  static double tp[ntp];
  static int tp1 = 0;

/*  If this is the first call to expm, fill the power of two table tp. */

  if (tp1 == 0) {
    tp1 = 1;
    tp[0] = 1.;

    for (i = 1; i < ntp; i++) tp[i] = 2. * tp[i-1];
  }

  if (ak == 1.) return 0.;

/*  Find the greatest power of two less than or equal to p. */

  for (i = 0; i < ntp; i++) if (tp[i] > p) break;

  pt = tp[i-1];
  p1 = p;
  r = 1.;

/*  Perform binary exponentiation algorithm modulo ak. */

  for (j = 1; j <= i; j++){
    if (p1 >= pt){
      r = 16. * r;
      r = r - (int) (r / ak) * ak;
      p1 = p1 - pt;
    }
    pt = 0.5 * pt;
    if (pt >= 1.){
      r = r * r;
      r = r - (int) (r / ak) * ak;
    }
  }

  return r;
}

Какие возможности это даёт? Например: мы можем создать систему распределённых вычислений, рассчитывающую число Пи и поставить всем Хабром новый рекорд по точности вычисления (который сейчас, к слову, составляет 10 триллионов знаков после запятой). Согласно эмпирическим данным, дробная часть числа Пи представляет собой нормальную числовую последовательность (хотя доказать это достоверно ещё не удалось), а значит, последовательности цифр из него можно использовать в генерации паролей и просто случайных чисел, или в криптографических алгоритмах (например, в хэшировании). Способов применения можно найти великое множество — надо только включить фантазию.

Больше информации по теме вы можете найти в статье самого Дэвида Бэйли, где он подробно рассказывает про алгоритм и его имплементацию (pdf);

И, похоже, вы только что прочитали первую русскоязычную статью об этом алгоритме в рунете — других я найти не смог.
Share post

Comments 95

    +5
    The Top Ten Algorithms of the Century
    5. the Fortran compiler, developed by a team lead by John Backus;
      0
      Вот, да, кстати.
      Буду признателен, если кто-нибудь расскажет, что в этом компиляторе такого особенного.
        +11
        Может это потому, что это был первый компилятор, в котором использовался анализатор на основе BNF, насколько я понимаю?
          0
          Спасибо. Заодно узнал, что такое BNF.
          Вполне заслуженно в топе находится.
          0
          Для своего времени компилятор был революционным. Как с точки зрения внутреннего устройства, так и с точки зрения пользователя. Насколько я помню, это был первый компилятор с «нормальными» сообщениям об ошибках в виде сообщения, а не номера, который нужно искать в мануале.
            +5
            Это первый компилятор языка высокого уровня. До этого были только ассемблеры.
          +1
          А этот алгоритм на другие иррациональные числа перекладывается?
            +2
            К примеру, в статье, ссылку на которую я приводил в конце топика, Бэйли начинает с вычисления n-го знака натурального логарифма двойки.
            Других упоминаний о подобном пока не встречал.
              0
              Да, если для них существует столь же удобная формула
              +14
              Отличное практическое применение вышеупомянутого алгоритма: πfs! Давно перенес на нее всю свою коллекцию фильмов.
                0
                Чёрт, мы пару дней назад взялись за реализацию подобного.
                А оказывается, всё уже придумали до нас!
                Практического применения этому, конечно, никакого, но весело!

                Если мы всё же доделаем свой вариант, имеет смысл статью об этом писать? Интересно будет? Или не очень?
                  +3
                  Пишите, конечно. Интересно будет почитать.
                    +5
                    В связи с ухудшающейся общемировой ситуацией, связанной с копирайтами и последствиями его нарушения, предлагаю simple yet brilliant идею — Offline Torrents Downloader!

                    Суть очень проста — для скачивания каждого блока достаточно просто найти последовательность в π с требуемым хэшем! Доступ к интернету? Зачем, ведь есть Offline Torrents Downloader — и пусть копираст докажет, что ты что-то откуда-то скачал!
                      +7
                      Собственно, это мы и реализовываем.
                      Coming soon, в общем :)
                    +2
                    Когда я последний раз изучал вопрос, скорость этой ФС еще не позволяла записывать туда фильмы. Это тонкий сарказм, или неожиданный прорыв в скорости поиска чанков?
                      +6
                      Да сарказм, очевидно же. Туда мегабайт будет «писаться» не один час на Core i7.
                      • UFO just landed and posted this here
                          +1
                          Это почему же на порядки больше? В среднем, того же объёма. Иногда больше, иногда меньше.
                          • UFO just landed and posted this here
                              +4
                              Согласен с вами до фразы «Почему-то я уверен». Это заблуждение сродни тому, что вероятность выигрыша лотерейного билета номер 123456 ниже, чем 593742.
                              Для иллюстрации попробуйте поискать в числе Пи, например, ABC и 7F3. Да и любые данные, которые выглядят более-менее осмысленными и сравните со «случайными».
                      +11
                      Обалдеть какая красивая формула
                        –33
                        Красивая? Женись.
                          +1
                          Действительно, редкой красоты формула. Вспомнилась, кстати сразу античная (!) 22/7
                            0
                            Да, красивая дробь, Архимедова. Только точность низкая.
                            Во времена Архимеда ещё не придумали арифметику с плавающей точкой. Так и жили, аппроксимированным делением интеджеров на интеджеры.
                              +2
                              … а равно как и в былые славные времена Z80, да и сейчас, во времена нынешних AVR со товарищи. Fixed-point рулит! Со времен античности.
                                0
                                Почему то вспомнился Integer Basic на ранних Apple I/II, который благодаря античным «интеджерам» накручивал популярность.
                              +1
                              А мне всегда намого больше нравилась 355/113. Чуть сложнее, а точность зато на 4 порядка больше.
                              0
                              Напомнило про визуализацию разрядов числа пи.
                              image
                              Взято отсюда.
                              0
                              > Учитывая, что Пи — это иррациональное число, то есть, в его записи каждая следующая цифра непредсказуема,…

                              Довольно сомнительный вывод. Что вы понимаете под непредсказуемостью, и как это следует из иррациональности?
                                0
                                Наверное, неправильно сформулировал.
                                Я имею в виду то, что любой случайно взятый знак дробной части числа Пи может с равной вероятностью оказаться любой цифрой от 0 до 9 (или, в случае с HEX-ом, от 0 до F).
                                  +3
                                  Да, неверно. Это — не непредсказуемость. И более того, совершенно не следует из иррациональности. Например, число 1.10100100010000100001 и т.д. иррациональное, хотя распределение цифр далеко от равномерного.
                                    0
                                    Спасибо, вы правы, отредактировал.
                                      0
                                      Если бы распределение в таких числах было хорошим, генераторы случайных чисел для криптографии были бы в разы проще.
                                        0
                                        Не факт. Допустим они абсолютно случайные.
                                        Берём 76352843-ю цифру числа Пи. С одной стороны она абсолютно случайная. С другой стороны, не более случайная чем 76352843.
                                        Ну и как такую случайность использовать в генераторе случайных чисел в криптографии?
                                          +2
                                          Вам достаточно было бы получить одно случайное число-ключ с медленного физического генератора, а не забирать с него всю последовательность, например. Естественно, это очень упрощенный пример.
                                            0
                                            хм. верно.
                                              +1
                                              С другой стороны такое может не подойти из-за вот этого требования

                                              Пусть генератор основывается на выводе бит какого-то представления числа Пи, начиная с какой то неизвестной точки. Такой генератор, возможно и пройдет «тест на следующий бит», так как ПИ, видимо, является случайной последовательностью (это было бы гарантированно, если доказать что Пи является нормальным числом). Однако этот подход не является критографически надежным — если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие биты.

                                              ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8_%D1%81%D1%82%D0%BE%D0%B9%D0%BA%D0%B8%D0%B9_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%82%D0%BE%D1%80_%D0%BF%D1%81%D0%B5%D0%B2%D0%B4%D0%BE%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB

                                              Т.е. если часть полученной последовательности скомпрометирована, (т.е. стал известен порядковый номер цифры числа), то и вся последовательность становится известной.
                                                0
                                                Если вы перехватили часть последовательности гаммы(потока бит числа Пи в данном случае), то это не дает вам возможность найти следующие биты. Данное условие направлено было исходя из того, что алгоритм генерации — конечный автомат и по N отсчетам (n1,n2...nN) можно найти текущее состояние генератора. В случае же числа Пи сколько угодно отсчетов можете взять и это не поможет: существует бесконечно много отсчетов вида (n1,n2...nN,l1,l2....lL), т.е. включающих в себя выбранный.
                                                Другими словами скомпрометированный кусок может продолжаться бесконечным числом способов.
                                                  0
                                                  Здесь речь про другое:
                                                  если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие биты.

                                                  если часть полученной последовательности скомпрометирована, (т.е. стал известен порядковый номер цифры числа)
                                                    0
                                                    Я как раз и отмечаю, что второе утверждение неверно: часть полученной последовательности не дает знания порядкового номера.
                                                      0
                                                      Здесь нигде не идёт речь про узнавание порядкового номера, с помощью полученной последовательности.

                                                      Речь просто про узнавание порядкового номера. Не важно каким путём.
                                                        +1
                                                        next-bit тест будет тем не менее пройден.
                                                        pS. вот бы для всех шифров так анализ происходил: для начала найдем секретный ключ. не важно каким путем.
                                                          0
                                                          Во первых это требование написано в википедии, не я его выдумал.

                                                          Ну вот в моём примере выше.
                                                          Берём 76352843-ю цифру числа Пи. С одной стороны она абсолютно случайная. С другой стороны, не более случайная чем 76352843.


                                                          на что Milfgard отвечает
                                                          Вам достаточно было бы получить одно случайное число-ключ с медленного физического генератора, а не забирать с него всю последовательность, например.


                                                          Итак, у нас есть последовательность в миллион «случайных» бит числа ПИ, полученная начиная с позиции 76352843

                                                          И вот — 76352843 можно просто угадать. Это легче чем угадать миллион случайных бит.
                                                            0
                                                            Когда вы получили эту последовательность у вас нет гарантии, что данная последовательность не повторяется «чуть» раньше или «чуть» позже: до данной позиции у вас еще примерно столько же, сколько и порядковый номер, последовательностей длины миллион. Об этом я и говорю выше: вы не сможете просто так угадать этот номер, ведь данная последовательность будет встречаться бесконечное множество раз в Пи.
                                                            Возможно, я непонятно объясняю… =(
                                                              0
                                                              Я понимаю что она бесконечно много раз встречается.
                                                              Но это не влияет на то что 76352843 можно просто угадать, и легче чем угадать миллион случайных бит.

                                                              76352843 влезает в 56 бит. Если мы решили из 76352843 сделать миллион случайных бит, «сэкономив» генератор настоящих случайных чисел («медленных физический генератор»).

                                                              То, злоумышленник, зная этот алгоритм, не будет угадывать миллон бит, он знает что исходное число влезало в 56 бит, и ему нужно брутфорсить 56 бит, а не миллион.
                                                                +1
                                                                У 76352843 уместится и в 32-битный int, что по сути ничего не меняет. Вы вслепую ссылаетесь на теорему Шеннона про идеальные шифры. Просто тогда и гамму надо как-то передавать по еще одному секретному каналу.
                                                                В том же RC4 когда ваш браузер безопасно соединяется вас же не смущает, что генерируется очень большая гамма из маленького начального ключа? Допустим, всего 128 бит?
                                                                  0
                                                                  Да, пардон, не 56 бит, а 56/2=28 бит.
                                                                    0
                                                                    В том же RC4 когда ваш браузер безопасно соединяется вас же не смущает, что генерируется очень большая гамма из маленького начального ключа? Допустим, всего 128 бит?

                                                                    Как раз таки по этому стойкость там считается как 128 бит, а не миллион бит.

                                                                    А если и этот начальный 128-битовый ключ генерировали бы из 28-битового индекса числа ПИ, то стойкость была бы 28 бит.
                                                                      0
                                                                      Тут довольно тонкий момент есть: 76352843 можно уместить и в 32-битное число, и в 128-битное и в 512-битное. Так вот в случае Пи это число бесконечно битное, просто старшие разряды нули. Или числа после некоего предела в последовательности Пи отбрасываются?
                                                                        0
                                                                        Тут довольно тонкий момент есть: 76352843 можно уместить и в 32-битное число, и в 128-битное и в 512-битное.

                                                                        Я называю 76352843 28-ми битным, потому что по легенде мы получили его из медленного физического генератора настоящих случайных чисел, и этот факт известен злоумышленнику. Ясно что медленный генератор генерирует маленькие числа, и какая именно разрядность — известно злоумышленнику, т.к. алгоритм не является секретом.
                                                                          0
                                                                          В начальной фазе инициализации сколько захотите, столько и будет стойкость: никто не запрещает использовать AES и для ключей длины 32 биты. В этом случае нам уже не интересно есть ли дальше уязвимости. Интерес в том не вносит ли алгоритм генерации гаммы других уязвимостей, о чем собственно и говорит тест next-bit.
                                      0
                                      оно не иррациональное, оно трансцендентное
                                        0
                                        Трасцендентное — да, но почему же не иррациональное?
                                          0
                                          ну просто потому что это более строгое определение ))
                                            0
                                            Более строгое определение? Иррациональное число — это не определение числа, это его принадлежность множеству иррациональных чисел. Так, что пи — рациональное число, пи — действительное число, это верные утверждения. А то, что пи — не иррациональное число, т.е. не принадлежит множеству иррациональных чисел — утверждение неверное.
                                            Хотели сказать, что трансцендентные числа — более узкое множество? Но, увы, число может быть:
                                            1) Не иррациональное, не трансцендентное. Например, 1.
                                            2) Иррациональное, не трансцендентное. Например, sqrt(2).
                                            3) Не иррациональное, трансцендентное. Например, pi * i.
                                            4) Иррациональное, трансцендентное, Например, pi.
                                              0
                                              вы в 4 пункте сами себе выше противоречите )))
                                              вероятно описание 3 и 4 перепутали?
                                              и я думаю мнимые единицы в данном контексте не сильно влияют на узость определения )))
                                              даже Вики в этом соглашается
                                                0
                                                В 3 и 4 — нет, выше действительно есть опечатка, следует читать:
                                                «Так, что пи — иррациональное число, пи — действительное число, это верные утверждения.»
                                                  0
                                                  Пи — иррациональное, трансцендентное, действительное число
                                                  Так не честно — вы комментарий уже исправили! )))
                                      +1
                                      извините, ошибся веткой
                                      • UFO just landed and posted this here
                                        • UFO just landed and posted this here
                                          • UFO just landed and posted this here
                                              +3
                                              Да вы — просто кладезь интересных ссылок!
                                                +2
                                                Между тем, я нашёл заметку Саймона Плаффа, где он рассказывает о том, как открыл эту формулу.
                                                Интересна следующая цитата:
                                                Величайшей ошибкой в моей жизни было то, что я позволил Боруэйну и Бэйли называться соавторами формулы, когда они не открыли ничего вообще.
                                                (ориг. This is where I made the biggest mistake in my life: To accept the collaboration of Peter Borwein and David H. Bailey as co-founders of that algorithm and formula when they have found nothing at all)

                                                • UFO just landed and posted this here
                                                  • UFO just landed and posted this here
                                              +3
                                              Про точку Фейнмана не знал, очень интересно, спасибо.
                                              Наверное, на днях займусь написанием статьи о формуле BBP для русской Википедии, учтя при этом замечания Хабра.
                                              • UFO just landed and posted this here
                                                  0
                                                  Напрямую — честно говоря, не знаю подходящих формул, из которых можно было бы что-нибудь подобное вывести.
                                                  А с промежуточным этапом в виде шестнадцатеричных знаков — с этим отлично справляется С-шный код, приведённый в статье.
                                                  А, значит, полагаю, и из формулы Белларда можно вывести, с промежуточным этапом в виде двоичных чисел.
                                              0
                                              И, похоже, вы только что прочитали первую русскоязычную статью об этом алгоритме в рунете — других я найти не смог.

                                              а вот cih.ru/a1/e79.html
                                                0
                                                Ну, там этот алгоритм только упоминается вскользь, даже краткого описания нет. Но всё равно спасибо — вспомнил, что такое Web 1.0
                                                  0
                                                  По мне так почти вся статья про этот алгоритм, но нет формулы и примера реализации.
                                              • UFO just landed and posted this here
                                                  +1
                                                  Саймон Плафф, как выяснилось, готов с вами поспорить.
                                                  Цитирую первые строчки:
                                                  We outline a method for computing the n'th decimal (or any other base) digit of Pi in
                                                  C*n^3*log(n)^3 time and with very little memory.
                                                  • UFO just landed and posted this here
                                                      0
                                                      А чему соответствует C?
                                                        0
                                                        Имеется в виду следующее:
                                                        «Существует такая константа C, для которой при любом сколь угодно большом N время выполнения алгоритма будет ниже, чем C*n^3*log(n)^3».
                                                        По-другому то же самое можно записать как T = О(n^3*log(n)^3)
                                                          0
                                                          Тогда правильно ли я понимаю, что время выполнения не зависит от основания системы счисления, даже если оно будет порядка (2**64)?

                                                          Если так, то можно значительно ускорить вычисления за счет VLIW/SIMD.
                                                            0
                                                            Когда основание системы счисления — степень двойки, время будет О(n), в других случаях — O(n^3*log(n)^3).
                                                              0
                                                              Ждем ASIC-ов.
                                                    +1
                                                    Согласно эмпирическим данным, дробная часть числа Пи представляет собой нормальную числовую последовательность (хотя доказать это достоверно ещё не удалось), а значит, последовательности цифр из него можно использовать в генерации паролей и просто случайных чисел, или в криптографических алгоритмах (например, в хэшировании). Способов применения можно найти великое множество — надо только включить фантазию.

                                                    Для генерации паролей, случайных чисел и другого есть более оптимальные и менее ресурсозатратные методы.
                                                      0
                                                      Был проект распределенных вычислений пи до миллиардного знака, как раз эту формулу использовал. Там был клинт, нужно было его скачать, чтобы сервер выдал ему диапазон для вычисления
                                                        0
                                                        Это все было или в конце 90х или в начале 2000х, проект шел параллельно с SETI@Home и кембриджским проектом поиска лекарств. То есть эта формула реально работала в параллельных вычислениях
                                                        0
                                                        Сомневаюсь в ценности формулы для распределенных вычислений большого количества цифр. Время вычисления n-го знака O(n), то есть на вычисление n цифр потратим O(n^2) времени, думаю есть более эффективные методы. Или нет?
                                                          0
                                                          Для вычисления всех цифр до n есть алгоритм со сложностью O(M(n)*log(n)), где M(n) — сложность перемножения двух чисел длиной n бит.
                                                            0
                                                            полагаю для n порядка 10^13 это значительно лучше квадрата.
                                                              0
                                                              Зависит от того, что такое M(n). Если «тупо» в столбик умножать, то M(n)=O(n^2), если с быстрым преобразованием Фурье — то M(n) = O(n log(n)).
                                                                0
                                                                Спасибо кэп. Речь шла о константе n (log n) ^ 2 лучше O(n^2) или нет. Замечу еще что умножение с быстрым преобразованием Фурье помимо прочего хорошо распараллеливается.
                                                          0
                                                          А каков геометрический смысл этой формулы? Встречались статьи на русском? Что она говорит про суть числа пи и прочих, считаемых подобными формулами? Как доказано, что ими вычисляется именно пи, а не лабуда какая-нибудь?
                                                            0
                                                            То, что это пи, доказывается без особого труда (доказательство где-то на полстранички). В сущности, формула говорит, что пи — это какой-то логарифм (или их линейная комбинация).
                                                            0
                                                            Что то не пойму и как из этого получить 10-ичную цифру, кто то может объяснить?
                                                            position = 6
                                                            fraction = 0.533289136557027
                                                            hex digits = 8885A308D3
                                                            0
                                                            Меня одного смущает вот этот цикл в коде: for (k = 0; k < id; k++)?
                                                            Получается, чтобы вычислить цифру числа PI начиная с позиции id, нам придется выполнить id итераций этого цикла. Получается, алгоритм имеет сложность O(n) для вычисления n-й цифры числа.

                                                            Честно говоря, по заголовку подумал, что, найдена формула, которая имеет сложность O(1) для конкретной цифры числа. Формула, безусловно, красивая. Но думаю, что генератор случайных чисел создать на её базе, увы, не получится: накладно.

                                                            Only users with full accounts can post comments. Log in, please.