Однажды, от нечего делать, я решил попробовать реализовать какой-нибудь интересный алгоритм из области вычислительной математики, уж очень хотелось совместить бесполезное с познавательным, а заодно хоть как-то привыкнуть к новому (на тот момент) для себя языку программирования (который еще и достаточно низкоуровневый, несмотря на некоторые вольности).
Но, к сожалению, в момент возникновения мысли об апробации на собственной шкуре вычислительного алгоритма, идей относительно того, что именно посчитать не появилось …
Однако, чтение 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.
Но об этом как-нибудь в другой раз …