Вычисление числа Пи методом «краника»

Однажды, от нечего делать, я решил попробовать реализовать какой-нибудь интересный алгоритм из области вычислительной математики, уж очень хотелось совместить бесполезное с познавательным, а заодно хоть как-то привыкнуть к новому (на тот момент) для себя языку программирования (который еще и достаточно низкоуровневый, несмотря на некоторые вольности).

Но, к сожалению, в момент возникновения мысли об апробации на собственной шкуре вычислительного алгоритма, идей относительно того, что именно посчитать не появилось …

Однако, чтение Habrhabr положительно сказалось на раздумьях после чего и появилась идея о вычислении числа Пи с огромным количеством точных знаков после запятой. Тут и скрывался подвох: я не знаю ни одного такого алгоритма, который бы позволил провернуть всю эту затею со сверхточными расчетами, кроме того, поиск информации приводил к таким вещам, которые мне как не программисту, очень трудно понять, а тем более и использовать. Словом, возникла ситуация, когда нужно применить нечто простое и оригинальное, которое тем не менее доступно для реализации с моими скромными способностями и познаниями в создании программ.

Тут меня выручил Habrhabr, в котором нашлась вот эта замечательная статья.

Ох, чтобы я без нее делал, а ?!

Изложенная в статье информация оказалась очень простой для понимания, однако, я не был настроен на то, чтобы потратить время на дотошное ее изучение, хотя все-таки стоило бы это сделать. Но даже из такого положения дел, когда хочется что-нибудь рассчитать по-быстрому, есть свой и надо сказать весьма оригинальный выход, который в моем случае, практически не потребовал значительных усилий.

Уважаемые читатели, я решил сделать порт алгоритма. То есть, мне пришлось рискнуть поработать переводчиком с одного языка на другой: в конце той статьи был алгоритм на Java (честное слово, Java я не знаю!), а мне был нужен алгоритм на D.

И я взялся за работу…

Уж не знаю, каким образом до меня дошло сразу, как работает StringBuilder, но факт был в том, что я практически сразу понял чем заменить его. Но это не самый интересный момент, который был в процессе переписывания с Java на D: мне пришлось столкнуться с тем, что в D у массивов нет некоторых методов. А это значит (правильно) что пришлось придумать, чем их заменить — и в итоге, было создано несколько забавных функций (а вот тут сюрприз: это мой первый опыт в применении шаблонов !) по работе с массивами.

Собственно, о процессе я немного рассказал и теперь самое время привести код (а за дополнительной информацией обращайтесь по ссылке на хабровскую статью из этого поста):

import std.stdio : writeln;
import std.conv : to;

void main()
{
    string p = piSpigot(1000);
    writeln(p);
}

string piSpigot(int n)
{
    int[] pi;
    int boxes = n * 10 / 3;
    int[] reminders = new int[boxes];
    reminders[] = 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;
        }
        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 = pi[i - k];
                if (replaced == 9)
                {
                    replaced = 0;
                }
                else
                {
                    replaced++;
                }
                pi = delete_item(pi,i - k);
                pi = insert_item(pi, replaced, i - k);
            }
            heldDigits = 1;
        }
        else
        {
            heldDigits = 1;
        }
        pi ~= q;
    }
    auto tmp = "";
    foreach(elem; pi[1..$])
    {
        tmp ~= to!string(elem);
    }
    return "3." ~ tmp;
}

pure T[] delete_item(T)(T[] x,int n)
{
    return x[0..n] ~ x[n+1..$];
}

/**
 * Insert element into dynamic array.
 * Returns: dynamic array.
 *
 * Params:
 *       x - dynamic array;
 *       y - element for insert;
 *       n - position for insertation of element;
 */
pure T[] insert_item(T)(T[] x,T y,int n)
{
    T[] tmp;
    tmp = x[0..n] ~ y ~ x[n..$];
    return tmp;
}

Приведенный код после компиляции и выполнения выведет 1 000 знаков числа Пи, что достаточно круто при том, что это дело занимает около 30 секунд на моем нетбуке (с большим количеством знаков я не пытался извращаться).  :)

Не судите, пожалуйста, строго  это мой первый раз в переносе кода из достаточно высокоуровневого языка в язык системного программирования.

Но помимо забавного процесса написания программы здесь был и еще один позитивный опыт: если вы обратите внимание на комментарии в коде, то увидите неплохое описание его поведения, а это описание было использовано для испытания генератора документации встроенного  компилятор dmd.

Но об этом как-нибудь в другой раз …

Добавить комментарий