Итерации Бэйли – Борвейна – Плуффа
Мы видели несколько проблем с пи-пиком в PPCG, но ни одна из них не определяла алгоритм, который вы должны использовать. Я хотел бы видеть реализации алгоритма Бэйли-Борвейна-Плуффа на любом языке вплоть до итерации n. Формула выглядит следующим образом:
Ваш алгоритм должен выводить каждую итерацию до n, показывая промежуточные суммы, а также конечный результат, чтобы сформировать «столбик». Вы также можете использовать сокращенную полиномиальную форму алгоритма, показанного на странице википедии. Пример выполнения для n=50показан ниже:
3
3.1
3.14
3.141
3.1415
3.14159
3.141592
3.1415926
3.14159265
3.141592653
3.1415926535
3.14159265358
3.141592653589
3.1415926535897
3.14159265358979
3.141592653589793
3.1415926535897932
3.14159265358979323
3.141592653589793238
3.1415926535897932384
3.14159265358979323846
3.141592653589793238462
3.1415926535897932384626
3.14159265358979323846264
3.141592653589793238462643
3.1415926535897932384626433
3.14159265358979323846264338
3.141592653589793238462643383
3.1415926535897932384626433832
3.14159265358979323846264338327
3.141592653589793238462643383279
3.1415926535897932384626433832795
3.14159265358979323846264338327950
3.141592653589793238462643383279502
3.1415926535897932384626433832795028
3.14159265358979323846264338327950288
3.141592653589793238462643383279502884
3.1415926535897932384626433832795028841
3.14159265358979323846264338327950288419
3.141592653589793238462643383279502884197
3.1415926535897932384626433832795028841971
3.14159265358979323846264338327950288419716
3.141592653589793238462643383279502884197169
3.1415926535897932384626433832795028841971693
3.14159265358979323846264338327950288419716939
3.141592653589793238462643383279502884197169399
3.1415926535897932384626433832795028841971693993
3.14159265358979323846264338327950288419716939937
3.141592653589793238462643383279502884197169399375
3.1415926535897932384626433832795028841971693993751
3.14159265358979323846264338327950288419716939937510
Точность каждой итерации должна равняться той, nчто передается алгоритму, то есть каждая итерация должна вычислять число пи до пройденного nдля всех k.
Правила:
- Встроенные модули не допускаются, и
piвы не должны использовать формулу. - Вы должны поддерживать
nмаксимум, что позволяет ваш язык с точки зрения расчета16^n. Если ввод вызывает арифметическое переполнение во время вычислений послеx<nвыполнения, потому что ваш язык поддерживает только десятичные дроби до2^32-1, это нормально. Любые другие предположенияnне подходят. - Вы ДОЛЖНЫ предоставить объяснение того, как вы получили выходные данные, если это не очевидно. Например, если вы публикуете на языке игры в гольф, разбивка на 100% обязательна. Это сделано для того, чтобы убедиться, что вы используете указанный алгоритм.
- Стандартные петли не допускаются.
- Это код-гольф, здесь побеждает наименьшее количество байт.
Ссылочный код (код, использованный для создания примера):
public static void main(String[] args) {
(0..50).each {
n->
def x=(0..n).collect {
j->
def k=new BigDecimal(j)
def s={it.setScale(n)}
def a=s(1.0g).divide(s(16.0g)**s(k))
def b=s(4.0g)/(s(8.0g)*s(k)+s(1.0g))
def c=s(2.0g)/(s(8.0g)*s(k)+s(4.0g))
def d=s(1.0g)/(s(8.0g)*s(k)+s(5.0g))
def e=s(1.0g)/(s(8.0g)*s(k)+s(6.0g))
def f=a*(b-c-d-e)
}.sum()
println(n + "\t" + x.setScale(n, BigDecimal.ROUND_DOWN))
}
}
Эта реализация ограничена на n=255, вы можете ограничиться на меньше или больше.
Эта реализация была сделана в Groovy.
Calculate foo via x methodпроблемами.Ответы:
05AB1E ,
635250 байтФормула специализации
Попробуйте онлайн!
Формула BBP
Попробуйте онлайн!
источник
Python 2,
109108 байтПроверьте это на Ideone .
источник
Python 2, 174 байта
Чувак, это время, когда я хотел бы, чтобы у Python был какой-то более простой способ сохранить бесконечную точность для десятичных дробей. Возможно, реализация собственного типа точности бесконечной точности для этой задачи короче, но я не могу себе представить, как. Формула написана дословно.
Пример вывода для
n=100(с некоторыми добавленными номерами строк):Похоже, это работает для больших чисел,
n=1000запускается за пару секунд иn=10000, похоже, пока не дает мне никаких ошибок!источник
Haskell,
101100 байтСпасибо @nimi за байт.
Простая реализация. Вычисляет
nдо 15 цифр (стандартная двойная точность).источник
l<-[8*fromIntegral k]вместо того, чтобыlet ...сохранить байт.J,
736462 байтаЭто выводит каждое приближение к n цифр в виде отформатированной строки. Это использует полиномиальное упрощение формулы и получает первые n цифр, умножая сумму на степень 10, суммируя ее и деля на ту же степень 10.
Входные данные воспринимаются как расширенное целое число, означающее, что при делении используются рациональные числа, которые сохраняют точные результаты.
использование
Это вывод для n = 100, показывающий кумулятивные суммы для k в [0, 100].
объяснение
Сначала сделайте диапазон [0, n ], показанный для n = 5
Умножьте каждое на 8
Сформируйте таблицу сложения между
[1, 4, 5, 6]и продуктами с 8Разделите каждый ряд на
[4, 2, -1, 1]Затем уменьшите столбцы снизу вверх, используя вычитание
Разделите каждые 16 k для k в [0, n ] на каждый результат
Найти кумулятивные суммы
Вычислите 10 k для k в [0, n ] и умножьте его на каждое
Затем пол каждого из продуктов
Разделите его на ту же степень 10, чтобы получить результаты
источник
PARI / GP, 86 байт
Или без десятичной точки в 69 байтах :
Вместо деления на 16 k для каждой итерации предыдущее значение p вместо этого умножается на 16 . Этаж p ÷ (8/5) k - это значение π, усеченное до правильного количества цифр.
Образец использования
источник
C GCC, 118 байт
Golfed:
Ungolfed:
Чтобы изменить n, просто измените while (k <15) на while (k <n)
выход:
максимальная точность 15 знаков после запятой, я могу увеличить до любого значения с помощью gmp, но, возможно, на следующий день пи: P
с красивым принтом, 143 байта
Golfed:
Ungolfed:
выход:
источник
IBM / Lotus Notes Formula, 125 байт
Формула в вычисляемом поле с другим полем, называемым «а» для ввода.
В основном порт алгоритма из ответа Python от @shebang. Вычисляет до 15 цифр, после чего он усекается из-за ограничения языка (см. Вывод). Нужно было потратить 12 байтов с оператором @If в конце, чтобы избавиться от. после 3 в начале: - /
Ungolfed
источник
C #, 183 байта
Golfed:
Ungolfed:
источник
3.14159265358979для печатиn >= 14из-за двойной точности?APL (NARS), 206 символов, 412 байтов
Это находит все аппроксимации в больших рациональных, чем использовать одну функцию, которая преобразует большие рациональные в числовую строку ... test:
источник