Пользователь
0,0
рейтинг
2 августа 2013 в 18:45

Разработка → «Краник», или алгоритм для поиска цифр числа Пи из песочницы

Привет, Хабр! Недавно столкнулся с задачей подсчёта числа Пи до знака, номер которого будет выбирать пользователь. Сразу полез на Википедию, почитать, что за зверь такой, это Пи, и как его находить с заданной точностью. Формул, описывающих число Пи, уйма. Но для решения моей задачи всё в этих формулах упирается либо в точность и длину базовых типов языка (я выбрал Java), либо (для решения предыдущей проблемы) в длинную арифметику, которую мне реализовывать не очень-то хотелось. Хотелось найти какой-то алгоритм, позволяющий найти число Пи вплоть до заданного знака, причём ровно до этого знака, а не находить длиннющее число, а потом обрезать его, чтобы отдать пользователю то, что он просил.

И я нашёл такой алгоритм, тот самый алгоритм «краника». Слово краник звучит здесь странно, но я не нашёл лучшего способа перевести название этого алгоритма с английского, как перевести дословно. Вообще, в оригинале это звучит как «A Spigot Algorithm for the Digits of Pi». Авторами алгоритма и его нарицателями являются американские математики Стенли Рабинович (Stanley Rabinowitz) и Стен Вэгон (Stan Wagon). Создали свой алгоритм для нахождения цифр числа Пи эти два товарища в 1995 году. Сама же идея алгоритма вышла из-под пера некого Сейла (Sale) ещё в 1968 году, и предназначался тот алгоритм для нахождения цифр числа e.

Вообще, англо-русские словари дают перевод слова spigot как “втулка”. Этот перевод ясности не даёт никакой. Поэтому я перевёл это слово как «краник», так как spigot в английском языке описывается как механизм, регулирующий поток жидкости. Идея же алгоритма в том и заключается, что за одну итерацию мы получаем ровно одну цифру числа Пи и потом её не используем. То есть цифры как бы вытекают из алгоритма, как вода из крана.

Теперь сам алгоритм. Я не буду вдоваться во всю математику (чего я, собственно, и не делал, разбирая алгоритм), подробнее о нём вы можете почитать здесь. К слову, по этой ссылке, есть и реализация алгоритма для поиска 1000 цифр числа Пи на Паскале, которой я по своей лени и решил сразу же воспользоваться. Переписал на Java, ан нет — не заработало. Выводило какую-то непонятную мне белиберду. Я это дело и бросил, так как отлаживать код, которого не понимаешь, сами знаете, как тушить горящее масло водой. Поэтому решил-таки разобраться с алгоритмом самолично.
Для нахождения n знаков числа Пи, понадобится массив длиной [10 * n / 3]. Причём целых чисел. Особенность алгоритма в том, что используется только целочисленная арифметика. Инициализируем все ячейки массива числом 2.

image

Далее, чтобы найти одну цифру числа Пи, необходимо пройтись по всем ячейкам массива с конца к началу и выполнить несложные действия. На примере таблицы, рассмотрим всё по порядку. Допустим, мы хотим найти 3 цифры числа Пи. Для этого нам необходимо зарезервировать 3 * 10 / 3 = 10 ячеек целого типа. Заполняем их все числом 2. Теперь приступим к поиску первой цифры…

Начинаем с конца массива. Берём последний элемент (под номером 9, если начинать счёт с 0. Этот же номер будем называть числителем, а тот, что под ним в таблицу – знаменателем) — он равен 2. Умножаем его на 10 (2 * 10 = 20). К получившемуся числу 20 прибавляем число из ячейки «Перенос» – число, которое переносится из более правой операции. Разумеется, правее мы ничего не считали, поэтому это число равно 0. Результат записываем в «сумму». В «остаток» записываем остаток от деления суммы на знаменатель: 20 mod 19 = 1. А сейчас считаем «перенос» для следующего шага. Он будет равен результату деления суммы на знаменатель, умноженному на числитель: (20 / 19) * 9 = 9. И записываем полученное число в ячейку с «переносом», стоящую левее от текущего столбца. Проделываем те же действия с каждым элементом массива (умножить на 10, посчитать сумму, остаток и перенос на следующий шаг), пока не дойдём до элемента с номером 0. Здесь действия немного отличаются. Итак, посмотрим, что у нас в таблице. Под нулём – элемент массива, равный 2, и перенос из предыдущего шага, равный 10. Как и в предыдущих шагах, умножаем элемент массива на 10 и прибавляем к нему перенос. В сумме получили 30. А сейчас делим сумму не на знаменатель, а на 10 (!). В итоге получаем 30 / 10 = 3 + 0 (где 0 – остаток). Полученное число 3 и будет той заветной первой цифрой числа Пи. А остаток 0 записываем в отведённую ему ячейку. Для чего были остатки? Их нужно использовать в следующей итерации – чтобы найти следующую цифру числа Пи. Поэтому разумно сохранять остатки в наш изначальный массив размером 10 * n / 3. Таким образом, видно, что возможности алгоритма упираются именно в размер этого массива. Поэтому число найденных цифр ограничивается доступной памятью компьютера либо языком, на котором вы реализуете алгоритм (конечно, языковые ограничения можно обойти).

Но это не всё. Есть один нюанс. В конце каждой итерации может возникать ситуация переполнения. Т.е. в нулевом столбце в «сумме» мы получим число, большее, чем 100 (эта ситуация возникает довольно редко). Тогда следующей цифрой Пи получается 10. Странно, да? Ведь цифр в десятичной системе счисления всего от 0 до 9. В этом случае вместо 10 нужно писать 0, а предыдущую цифру увеличивать на 1 (и стоящую перед последней, если последняя равна 9, и т.д.). Таким образом, появление одной десятки, может изменить одну и больше найденных ранее цифр. Как отслеживать такие ситуации? Необходимо найденную новую цифру первоначально считать недействительной. Для этого достаточно завести одну переменную, которая будет считать количество недействительных цифр. Нашли одну цифру – увеличили количество недействительных цифр на 1. Если следующая найденная цифра не равна ни 9, ни 10, то начинаем считать найденные ранее цифры (и помеченные как недействительные) действительными, т.е. сбрасываем количество недействительных цифр в 0, а найденную новую цифру начинаем считать недействительной (т.е. можно сразу сбрасывать в 1). Если следующая найденная цифра равна 9, то увеличиваем количество недействительных цифр на 1. Если же следующая цифра 10, то увеличиваем все недействительные цифры на 1, вместо 10 записываем 0 и этот 0 считаем недействительным. Если эти ситуации не отслеживать, то будут появляться единичные неверные цифры (или больше).

Вот и весь алгоритм, который авторы сравнили с краном. Ниже привожу код метода, реализованного на Java, который возвращает строку с числом Пи.

public static String piSpigot(final int n) {
    // найденные цифры сразу же будем записывать в StringBuilder
    StringBuilder pi = new StringBuilder(n);
    int boxes = n * 10 / 3;	// размер массива
    int reminders[] = new int[boxes]; 
    // инициализируем масив двойками
    for (int i = 0; i < boxes; i++) {
        reminders[i] = 2;
    }
    int heldDigits = 0;    // счётчик временно недействительных цифр
    for (int i = 0; i < n; i++) {
        int carriedOver = 0;    // перенос на следующий шаг
        int sum = 0; 
        for (int j = boxes - 1; j >= 0; j--) {
            reminders[j] *= 10;
            sum = reminders[j] + carriedOver;
            int quotient = sum / (j * 2 + 1);   // результат деления суммы на знаменатель
            reminders[j] = sum % (j * 2 + 1);   // остаток от деления суммы на знаменатель
            carriedOver = quotient * j;   // j - числитель
        }
        reminders[0] = sum % 10;            
        int q = sum / 10;	// новая цифра числа Пи
        // регулировка недействительных цифр
        if (q == 9) {
            heldDigits++;
        } else if (q == 10) {
            q = 0;
            for (int k = 1; k <= heldDigits; k++) {
                int replaced = Integer.parseInt(pi.substring(i - k, i - k + 1));
                if (replaced == 9) {
                    replaced = 0;
                } else {
                    replaced++;
                }
                pi.deleteCharAt(i - k);
                pi.insert(i - k, replaced);
            }
            heldDigits = 1;
        } else {
            heldDigits = 1;
        }
        pi.append(q);	// сохраняем найденную цифру
    }
    if (pi.length() >= 2) {
        pi.insert(1, '.');	// добавляем в строчку точку после 3
    }
    return pi.toString();
}


Ради интереса провёл тест производительности алгоритма в зависимосты от величины n (количество цифр, которые нужно найти). Получился вот такой график:

image

Для нахождения миллиона цифр понадобилось больше восьми с половиной часов. Тесты я проводил без печати результатов и использовал не StringBuilder, а байтовый массив.

Итак, подытожим. Главными достоинствами алгоритма являются его простота (посчитать можно без проблем и руками), а также использование только целочисленной арифметики, что ускоряет процесс вычислений и добавляет точности. Главным же недостатком я считаю ограниченность алгоритма (памятью).

P. S.: Алгоритм на основе формулы Bailey–Borwein–Plouffe из разряда «краниковых» ранее обсуждался на Хабре в этой статье.

http://en.wikipedia.org/wiki/Pi
http://en.wikipedia.org/wiki/Spigot_algorithm
http://www.mathpropress.com/stan/bibliography/spigot.pdf
http://www.pi314.net/eng/goutte.php
http://en.wikipedia.org/wiki/Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula
http://habrahabr.ru/post/179829/
@yahorfilipcyk
карма
8,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (22)

  • +1
    Интересно, откуда резкий скачок на 200000?
    • 0
      Спасибо за вопрос. Я сам в это раньше верил. Оказывается ошибка в делениях оси была, поэтому резкий скачок получился. Исправил
  • +8
    Википедия говорит, что spigot — это не отдельный алгоритм, а категория алгоритмов. Метафора с капающей из крана водой взята потому, что извлеченные знаки не используются (не требуются) для вычисления последующих знаков. Собственно, это и есть определение этого типа алгоритмов.

    Автор использует безымянный алгоритм авторства Stan Wagon и Stanley Rabinowitz, первый из найденных «краниковых» алгоритмов для числа Пи. Этот алгоритм требует на входе указания количества знаков, которые необходимо вычислить.

    Для полноты картины приведу другой алгоритм: «BBP» (назван по именам авторов: David H. Bailey, Peter Borwein и Simon Plouffe). Его уникальной особенностью является то, что он позволяет начинать вычисление с произвольного места, а не с начала. Таким образом можно за секунды вычислить любой знак числа Пи по желанию (сложность вычислений возрастает с увеличением порядкового номера знака). Этот алгоритм незаменим для проверки на верность рекордов вычисления числа пи, устанавливаемых более быстрыми алгоритмами. Алгоритм вычисляет знаки в шестнадцатеричной системе счисления. Для вычисления знаков в десятичной системе приходится переводить из шестнадцатеричной. Существуют вариации алгоритма и для других систем счисления, но только кратных двойке.

    Вот тут BBP реализован на браузерном JavaScript (автор Andrew Collins). Вычисление 1'939'372-го десятичного знака на моем ноутбучном i7-3520M в Chrome заняло примерно десять секунд.
    • +1
      Согласен насчёт категории алгоритмов.
      Есть отдельная статья Spigot algorithm на Википедии. Там упоминается, что название, судя по всему, было придумано Рабиновичем и Вэгоном.
    • +4
      Кстати, про «ВВР» был пост на Хабре.
      Ещё есть формула Белларда, которая работает на 43% быстрее ВВР (она же является модификацией ВВР).
    • +3
      Благодаря хабраэффекту мы помогли Эндрю Коллинзу вычислить ещё 4 тысячи знаков за один день! На что же способен целый пост, посвященный распределенным вычислениям на чьем-нибудь сервере?
  • +5
    а не проще было найти где нить число ПИ до энцатого знака, с запасом, а потом просто выдавать от него сколько надо?
    • +4
      Гораздо проще. И гораздо скучнее.
    • +1
      И написать сервис, предоставляя возможность брать всему миру из кеша уже посчитаные числа.
  • НЛО прилетело и опубликовало эту надпись здесь
    • +1
      Добавил.
  • 0
    Как-то очень медленно у Вас считается. Реализовывал когда-то в рамках лаб.работы параллельный расчет числа PI до n-цатого знака. Там все было гораздо веселее. На i3 процессоре 50 000 знаков считалось что-то около 8-ми секунд. Правда на фоне рекорда в 2.7 триллиона знков — моя программа считала бы их 13 лет (мдяяя...)

    Если хотите могу дать исходник. Правда на C++ + MPI + gmp. Ууухх ну и связочка :-)
    • +1
      А какой Вы алгоритм использовали? Может в нём дело. Не думаю, что описанный мною алгоритм может претендовать на имя самого быстрого.
      • 0
        Честно говоря я уже не помню. Помню что основано на расчете бесконечного ряда.
  • 0
    длинную арифметику, которую мне реализовывать не очень-то хотелось

    Вы же знаете про BigInteger, не правда ли?
    • 0
      Многие алгоритмы по вычислению числа пи используют не целочисленную длинную арифметику, а заморачиваться с учетом количества знаков после запятой, как это делается в BigDecimal тоже не всегда удобно.
  • 0
    Кстати, есть ли аналогичная статья в русскоязычной википедии?
  • 0
    Опытным путем заметил что после ввода количества знаков больше 100 000 резко падает скорость вычисления. Те. если ввожу 100, то считает мнгновенно, если ввожу 1 000 000, то теде первые 100 считает намного медленнее.
    В связи с эим вопрос:
    1) Это только у меня так, либо нет? Если у всех, то с чем это связано? Опять же если у всех, то второй вопрос.
    2) Я так понимаю результаты на графике сделаны из одного эксперимента (с вводом 1 000 000). интересно былобы понаблюдать зависимость скорости подсчета первой тысячи относительно входных данных.

    upd: AMD FX 4100, Quad 3.62. 8Gb
    • 0
      Сорри, прочитал внимательнее, понял глупость своего комментария. Но
      интересно былобы понаблюдать зависимость скорости подсчета первой тысячи относительно входных данных.
      остается в силе. Ввести нейкую «удельную скорость» подсчета в зависимости от n.
      • 0
        Результаты на графике именно с разных экспериментов. Самые большие результаты как раз таки на значениях n, больших 200 000. До этого график как-то неуверенно идёт вверх.
        Всё верно, скорость вычисления тех же цифр при значительном возрастании n должна падать, потому что для нахождения одной цифры нужно пройтись по массиву размером n*10 / 3. Соответственно, чем больш n, тем больше времени уходит на вычисление одной цифры.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.