Имплементация алгоритма Бэйли—Боруэйна—Плаффа на Golang

    Pi
    Число Пи, скажу вам братцы,
    Легче так запоминать.
    Три четырнадцать пятнадцать
    Девять два, шесть пять, три пять.

    © Дмитрий Эйт


    Недавно мне потребовалось число Пи в шестнадцатиричном формате. Примерно 10000 знаков после запятой. Однако все публикации в сети как правило демонстрируют Пи в десятичном виде. Потыкавшись немного я нашёл Пи в двоичном виде, и это меня более чем устроило: простая конвертация решила поставленные задачи. Тут бы и закончить историю, но как говорится, «ложечка-то нашлась, а осадок остался». Ниже вы сможете посмотреть простую имплементацию библиотеки PiHex, генерирующей цифру, или последовательность цифр в любой позиции после запятой у числа Пи (правда, не более, чем 10,000,000).

    Итак, существует алгоритм «BBP», который позволяет вычислить в шестнадцатиричном Пи знак в любой позиции после запятой. Сам этот алгоритм из разряда «краниковых», подробней об этом семействе алгоритмов можно почитать в статье: «Краник», или алгоритм для поиска цифр числа Пи. Об имплементации алгоритма «BBP» на языке Си на хабре также была статья: Вычисление N-го знака числа Пи без вычисления предыдущих

    О алгоритме


    Описание алгоритма лучше всего прочитать в статье «The BBP Algorithm for Pi», опубликованной Дэвидом Бейли 17 сентября 2006 года: www.davidhbailey.com/dhbpapers/bbp-alg.pdf Кстати говоря, написана она вполне понятно, по крайней мере и не математик тоже может кое-что понять. Из статьи видно, что для расчёта используется не сильно сложная формула в виде:

    при этом Sj вычисляется как:

    в результате получается немного более громоздкая формула


    Реализация


    При переносе на Go имплементация была реализована с использованием горутин, чтобы распараллелить ресурсоёмкие вычисления Sj. Это позволило значительно ускорить вычисления, так как на современных компьютерах в процессоре обычно ядер больше, чем одно. Впрочем возможно, это не сильно и нужно, если требуется один знак, но если тысяча, скорость работы в любом случае будет важна.

    API


    Использовать библиотеку не просто, а очень просто, т.к. фактически она поддерживает лишь один метод. Пример ниже показывает, как подключить библиотеку и получить первые 20 знаков после запятой:

    package main
    
    import (
        "fmt"
        "github.com/claygod/PiHex"
    )
    
    func main() {
        pi := PiHex.New()
        fmt.Print("The first 20 digits of Pi (hexadecimal): ", pi.Get(0, 20))
    }
    


    Где пригодится библиотека PiHex


    Собственно, там, где нужно Пи, и при этом именно в шестнадцатиричном виде. Если требуются большие порядки, то возможно, имеет смысл заранее просчитать Пи и/или пользоваться уже вычисленными результатами, т.к. например на моём компьютере вычисление десяти знаков после 1,000,000 позиции заняло немного более десяти секунд. В связи с ограничением в 10,000,000 знаков после запятой библиотека PiHex никак не подойдёт для установки новых рекордов в вычислении Пи.

    Конфигурирование


    Реально менять можно только один параметр: STEP. Он указывает, сколько цифр может вычисляться за одну итерацию. По умолчанию стоит 9, и это максимально возможное число, позволяющее сохранить правильность вычисленного результата. Если есть сомнения, цифру можно уменьшать, что правда, уменьшит скорость работы библиотеки.

    Тестирование


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

    Ссылки


    Библиотека PiHex на Гитхабе
    Формула Бэйли — Боруэйна — Плаффа
    Статья Дэвида Бейли об алгоритме BBP

    Комментарии 7

      +1
      Я определенно не понимаю, о чем статья. Об алгоритме? — Нет, есть только ссылка на статью. Никаких интересных моментов, никаких доказательств, просто формула. Об интересном подходе к реализации алгоритма? — Нет, ни слова. Об интересном применении го? — Нет, кроме двух слов о горутинах, которые может и не нужны. Об оптимизации? — Тоже мимо, производительность алгоритма явно не очень.
        0
        Если бы требовалось вычислять всю последовательность знаков до того знака, который нужен, то производительность действительно была бы не ахти. Но тут предыдущие знаки вычислять не требуется, поэтому не самый быстрый способ вычисления всего Пи компенсируется удобством и скоростью расчёта конкретного знака.
          0
          не самый быстрый способ вычисления всего Пи

          Прям-таки всего? Ну и какая там последняя цифра?


          Ну и про бесполезность точного значения числа: https://geektimes.ru/post/272980/#comment_9110800

            0
            Прям-таки всего? Ну и какая там последняя цифра?

            К сожалению, я не смогу ответить на этот вопрос ))
            В предыдущем предложении там я написал «до того знака, который нужен», не хотелось повторяться.

            Ну и про бесполезность точного значения числа

            Мне оно нужно было не для того, чтобы так точно что-то вычислять, так что я вполне соглашусь с вашим доводом.
          0
          Что может быть за ситуация, в которой перевод из двоичной или десятичной систем в нужную оказывается недопустимо медленным и побуждает писать отдельную реализацию?
            0
            Если говорить про получение двоичных знаков, то я знаю только BBP, который можно использовать и для двоичных, и для шестнадцатиричных.
            –1
            Простите но даже я такое говно сюда не постил ;)

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

            Самое читаемое