Пи раз е (или Пи, если вам нравятся неоднозначные обозначения) до 100 десятичных знаков:
8.5397342226735670654635508695465744950348885357651149618796011301792286111573308075725638697104739439...
( OIES A019609 ) ( аргумент в пользу возможной иррациональности )
Ваша задача - написать программу, которая принимает положительное целое число N и выводит Pi * e, укороченные до N десятичных знаков. например, если N = 2, то вывод должен быть 8.53
.
Это проблема оптимизации, поэтому выиграет представление, которое может дать правильный вывод для наибольшего значения N.
Чтобы гарантировать, что все представления оцениваются с использованием одной и той же вычислительной мощности, ваш код должен выполняться на ideone с использованием любого языка, который они поддерживают. Согласно ideone faq , для не авторизованных пользователей существует ограничение времени выполнения 5 секунд. Это 5-секундное ограничение, которое вы должны использовать, а не 15-секундное ограничение для зарегистрированных пользователей. (См. Faq для других ограничений, таких как память, размер кода и т. Д.)
В частности, любой, кто не вошел в ideone, должен иметь возможность запускать вашу программу на ideone для всех значений N от 1 до некоторого максимального Nmax и видеть корректный вывод почти все время . без каких- Time limit exceeded
либо Memory limit exceeded
ошибок. Представление с наибольшим Nmax выигрывает.
(Независимо от того, является ли фактическое время намазыванием более 5 секунд, не имеет значения, если ideone не дает ошибок. « Почти все время » определяется как более 95% времени для любого конкретного N.)
подробности
- Вы можете использовать любой математический метод для вычисления Pi * e, но вы не можете жестко закодировать вывод, кроме первых десятков цифр Pi, e или Pi * e .
- Ваша программа должна быть в состоянии работать для любого N, учитывая неограниченные ресурсы.
- Вы можете использовать встроенные константы Pi или e, если они есть в вашем языке.
- Вы не можете получить доступ к веб-сайтам или ресурсам, внешним по отношению к вашему коду (если ideone даже позволяет это)
- Помимо жесткого кодирования и доступа к внешним ресурсам, все, что позволяет ideone, почти наверняка подходит.
- Ваш ввод и вывод должны (очевидно) работать с тем, что ideone обеспечивает для ввода / вывода (только кажется, что stdin / stdout). Хорошо, если вам нужны кавычки вокруг ввода N или что-то в этом роде и
ans = ...
т. Д. - Пожалуйста, включите ссылку на фрагмент кода Ideone вашего кода с вашим Nmax в качестве входных данных.
- В случае совпадения (возможно только в том случае, если количество отправленных сообщений превысит ограничение на количество выходных символов 64 КБ), победит ответ с наибольшим количеством голосов.
источник
Ответы:
Python - 65535
http://ideone.com/knKRhn
Кажется, что Ideone не
gmpy2
установлен, что, к сожалению, по крайней мере по двум причинам. Во-первых, потому что это сделает расчет намного быстрее, и во-вторых, потому что делает любую формулу, требующую квадратного корня произвольной точности, непрактичной.Формула, которую я использую для π, была указана Рамануджаном как Формула (39):
который сходится со скоростью ~ 5,89 цифр за семестр. Насколько мне известно, это наиболее быстро сходящиеся серии в своем роде, которые не требуют оценки квадратного корня произвольной точности. Формула (44) в той же работе (скорость сходимости ~ 7.98 цифры в перспективу) наиболее часто упоминаются как в Рамануджане формулу.
Формула, которую я использую для е, является суммой обратных факториалов. Количество требуемых членов рассчитывается как Γ -1 ( 10 n ), используя приближение, которое я нашел для mathoverflow . Компонент Ламберта W 0 найден с использованием метода Ньютона.
Вычисление каждого из этих суммирований выполняется с помощью быстрой оценки E-функции (более широко известной как бинарное расщепление), первоначально разработанной Карацубой. Метод сводит суммирование до n слагаемых к единственному рациональному значению p / q . Эти два значения затем умножаются для получения окончательного результата.
Обновление:
профилирование показало, что более половины времени, необходимого для расчета, было потрачено в последнем разделе. Только самый верхний журнал 2 (10 л ) биты д необходимы для получения полной точности, поэтому обрезать несколько прочь заранее. Теперь код заполняет выходной буфер Ideone за 3,33 с .
Обновление 2:
Поскольку это задача оптимизации , я решил написать свою собственную процедуру деления для борьбы с медлительностью CPython. В реализации
divnr
вышеизложенного используется Ньютон-Рафсон Отдел . Общая идея состоит в том, чтобы вычислить d = 1 / q · 2 n, используя метод Ньютона, где n - количество битов, которое требуется для результата, и вычислить результат как p · d >> n . Время выполнения теперь составляет 2,87 с - и это даже без обрезания битов перед вычислением; это не нужно для этого метода.источник
PARI / GP: 33000
Это в основном программа, представленная в OEIS , модифицированная для правильного ввода и форматирования вывода. Это должно послужить базой, чтобы победить, если ничего больше.
Я полагаю, это точно. Я проверил это в 100 и 20 КБ против OEIS, и это соответствовало обоим. Довольно сложно найти дополнительные цифры в Интернете для проверки.
Для 33 000 это займет около 4,5 с, так что, вероятно, это может быть немного увеличено. Мне просто надоело возиться с вводом и медленным циклом отправки / компиляции / запуска ideone.
Ideone.com ссылка
источник
Str(floor(frac(x)*10^m)
это идет в сотни / тысячи раз быстрее.Python 3
Поскольку у встроенных пи и е недостаточно цифр, я решил вычислить свои собственные.
IDEOne ссылка
Выход для STDIN = 1000:
источник
should be able to work for any N, given unlimited resources
правилу. Большая часть выходных данных - это нули в районе N = 10000.)NameError: name 'xrange' not defined
.Скала - 1790
IDEOne на http://ideone.com/A2CIto .
Мы используем формулу Уэзерфилда для π (и код формулы Мачина, грубо перенесенный отсюда ). Мы вычисляем е, используя обычные степенные ряды.
источник