В википедии есть очень симпатичный алгоритм, N=100 цифр можно вычислить за S=6 шагов, а N=1000 за S=9. Из сложных операций на каждом шаге требуется одно умножение и корень. Еще одно умножение и деление нужно чтобы получить Пи, и один корень для инициализации. То есть требуется одно деление, S+1 умножение и S+1 корень. Что касается деления, то его можно заменить умножением на обратную величину вычисляемую по итеративной формуле типа x=x*(2-x*y) за log(N) шагов. Начинать можно с некоторого приближения x0, на каждой итерации количество верных цифр будет удваиваться, полное умножение NxN потребуется только на последнем шаге, а все предыдущие итерации по времени выполнения примерно равны еще одному умножению. То есть финальное деление примерно эквивалентно 4 умножениям. Что касается корней, то 1/корень можно вычислить используя итеративную формулу x=x*(3-x*x*y). Здесь три умножения, добавив еще 1.5 на предыдущие итерации, и 1 чтобы получить корень, получим что корень эквивалентен 5.5 умножениям, в итоге получается что для 100 цифр требуется примерно 50 умножений, а для 1000 примерно 70. Возможно что для деления и корня есть и более простые варианты. Хорошо бы конечно делать умножения методом Карацубы, но 100 и 1000 десятичных цифр занимают не очень круглое количество байт и не факт, что дробление блоков и лишние проверки не дадут фору какому-либо более примитивному алгоритму.
