Передай Пи… точно

11

Вслед за оценкой Монте-Карло числа Pi эта задача состоит в том, чтобы создать кратчайший код для константы Pi. За исключением того, что здесь ваш код должен выводить последовательные цифры пи всегда.

Это кодовый гольф, поэтому выигрывает самое короткое представление (в байтах), за исключением того, что оно должно выводить первые 10000 цифр менее чем за 10 секунд на приемлемом ПК и никогда не прекращаться.

Вы не можете использовать какие-либо встроенные функции Pi или trig.


Убрано жесткое ограничение на размер кода.

Сообщество
источник
1
Под твитом вы подразумеваете, что код должен содержать не более 140 символов?
Ипныпн
5
Проблема сама по себе кажется сложной без ограничения характера.
BobTheAwesome
1
@BobTheAwesome Снято ограничение на количество символов по многочисленным просьбам.
1
@ mbomb007 Совершенно не очевидно, что десятичная точка должна быть напечатана или что цифры могут не разделяться пробелами. Задача состоит в том, чтобы просто «вывести последовательные цифры числа пи». Десятичная точка не является цифрой. 3141...это - последовательные цифры числа пи.
orlp
1
Было бы лучше, если бы напечатанное число было Pi, чтобы между цифрами не было пробела. Было бы еще лучше, если бы он включал десятичную точку.

Ответы:

7

CJam - 48

3.1o{1YAZ2*:Z#*{_2$*2$2*)/@)\}h*]:+sX2*:X>X<o1}g

Это вычисляет π как 2 * сумму (k! / (2k + 1) !!) с большей и большей точностью и на каждом шаге печатает набор цифр с того места, где он остановился.

Вы можете попробовать онлайн модифицированную версию, которая делает только 8 (внешний цикл) итераций и печатает 512 цифр, или использовать интерпретатор java для реальной вещи. На моем ноутбуке он достигает 16384 цифр за 6 секунд.

Примечание: эта программа очень требовательна к памяти; лучше ведет себя, но немного длиннее версия:

3.1o{T2AZ2*:Z#*1{@2$+@2$*2$2*)/@)1$}g;;sX2*:X>X<o1}g

Объяснение:

3.1o              print 3.1
{…1}g             repeat indefinitely
    1YA           push 1, 2 and 10 (Y=2, A=10)
    Z2*:Z         push Z*2 (Z=3 initially) and store back in Z
    #*            calculate 2*10^Z (2 from the formula and 10^Z for precision)
                  this is the term for k=0, and the earlier 1 represents k
    {…}h          do-while
                  at each iteration, the stack contains: terms, k, last-term
        _2$*      copy the previous term and k and multiply them
        2$2*)/    divide the previous number by 2*k+1
                  this is the current term of the series
        @)\       increment k and move it before the current term
                  the current term now serves as the loop condition
                  so the loop terminates when the term becomes 0
    *             multiply k and the last term (0), to get rid of k
    ]:+s          put all the terms in an array, add them and convert to string
                  we obtain an approximation of π*10^Z
    X2*:X         push X*2 (X=1 initially) and store back in X
    >X<o          print X digits starting from the X position
уйти, потому что SE это зло
источник
8

Python, 138 байт

q,r,t,i=1,180,60,2
while 1:u,y=27*i*(i+1)+6,(q*(27*i-12)+5*r)//(5*t);print(y,end="");q,r,t,i=10*q*i*(2*i-1),10*u*(q*(5*i-2)+r-y*t),t*u,i+1

Реализация http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf .

orlp
источник
Ударь меня до 5 минут ..... :)
Maltysen
Это здорово. Однако я надеялся, что все цифры будут в одной строке. Другими словами, что вывод будет выглядеть как Пи.
2
@Lembik Я изменил свой ответ - на 7 байт больше, но теперь все в одной строке.
orlp
5

GolfScript (81 символ)

1:i:^3{3i):i*(.(*3*.@*.5*3$27i*12-*+@^*:^5*/.print^*2$5i*2-*--\10*i*2i*(*\10*.}do

Демонстрация в Интернете (это намного медленнее, чем на обычном рабочем столе, и имеет тривиальные изменения кода, чтобы зацикливаться конечное число раз).

Я, конечно, использовал алгоритм spigot, который я упомянул в предыдущем комментарии, но мне потребовалось некоторое время, чтобы поиграть в него к моему удовольствию. Алгоритм, представленный в статье Гиббона, (псевдокод)

q = 1; r = 180; t = 60; i = 2
while (true) {
    u = 3*(3*i+1)*(3*i+2)
    y = (q*(27*i-12)+5*r) / (5*t)
    print y
    r += q*(5*i-2)-y*t
    r *= 10*u
    q *= 10*i*(2*i-1)
    t *= u
    i += 1
}

Приведенный выше код GolfScript эквивалентен (псевдокод)

t = i = q = 1; r = 3
while (true) {
    u = 3*(3*i+1)*(3*i+2)
    i += 1
    r *= u
    t *= u
    y = (q*(27*i-12)+5*r) / (5*t)
    print y
    r -= y*t - q*(5*i-2)
    q *= 10*i*(2*i-1)
    r *= 10
}

который сохраняет некоторые символы в инициализации и в управлении стеком.

Питер Тейлор
источник
4

Pyth - 87 85 байт

Еще один перевод http://www.cs.ox.ac.uk/jeremy.gibbons/publications/spigot.pdf . Я собирался сделать Python, но @orlp победил меня, поэтому я сделал Pyth. Достаточно маленький, чтобы поместиться в твит.

=H3=d1=bd=Gd#K+**hb27b6~b1=H*HK=d*dKJ/+*-*27b12G*5H*5d=H*T-H-*Jd*-*5b2G=G***GTbtybpkJ

Он выводит на стандартный вывод, хотя и с перерывами, из-за буфера печати, который задается настройкой end=""печати. В настоящее время я не печатаю десятичную точку, поскольку в спецификации написано "последовательные цифры". Это задания, которые убивают мой счет.

=H3                     Set H to 3
=d1                     Set d to 1
=bd                     Set b to d which is 1
=Gd                     Set G to d which is 1
#                       Infinte Loop
  K                     Set K to
    +**hb27b6           27*b*(b+1)+6
  ~b1                   b+=1
  =H*HK                 H*=K
  =d*dK                 d*=K
  J                     Set J to
    /                   Integer division
      +*-*27b12G*5H     G*(27*b-12)+5*H
      *5d               5*d
  =H                    Set H to
    *T-H-*Jd*-*5b2G     10*(H-(J*d -G*(5*b-2)))
  =G                    Set G to
    ***GTbtyb           G*10*b*(2*b-1)
  pkJ                   Print J with the end as "", not a newline

Попробуй это здесь . (Примечание: поскольку онлайн-интерпретатор дает только завершенные результаты, бесконечный цикл отключен, поэтому он печатает только первые 100, что увеличивает размер кода. Чтобы попробовать бесконечный, загрузите локальный интерпретатор.)

тайминг

На моем Google Cloud Compute Micro экземпляр, в соответствии с GNU время заняло: real: 0m2.062sтак что, очевидно, достаточно быстро.

Maltysen
источник
3

Scala, 599 байт

Приведенный ниже код является прямым портом кода Паскаля из Приложения 2 Алгоритма Spigot для цифр числа Пи . Очевидно, что очень мало игры в гольф было сделано. Код генерирует 10 000 цифр менее чем за 10 секунд, piSpigot(10000)и если у вас есть бесконечная память, можно параметризовать, чтобы генерировать много цифр, но не бесконечно. Я не уверен, что это соответствует ограничениям проблемы, поэтому, пожалуйста, оставьте отзыв.

def piSpigot(n: Int): Unit = {
  val len=10*n/3
  var nines=0
  var predigit=0
  val a=Array.fill(len)(2)
  (1 to n).foreach {_=>
    var q=0
    (1 to n).reverse.foreach{i=>
      var x=10*a(i)+q*i
      a(i)=x%(2*i-1)
      q=x/(2*i-1)
    }
    a(1)=q%10
    q/=10
    if (q==9) {
      nines+=1
    } else if (q==10) {
      print(predigit+1)
      1.to(nines).foreach(_=>print(0))
      predigit=0
      nines=0
    } else {
      print(predigit)
      predigit=q
      if (nines!=0) {
        1.to(nines).foreach(_=>print(9))
        nines=0
      }
    }
  }
  println(predigit)
}
piSpigot(10000)
Дейв Шварц
источник
5
Я думаю, что требование производить цифры до бесконечности означает, что вам нужно использовать алгоритм потоковой передачи, а не тот, который принимает параметр n. См. Например cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf
Питер Тейлор
Бесконечная память и бесконечное время должны давать бесконечное количество цифр.
1

Befunge-98 (PyFunge), 120 байт

cf*10p'<20p11>00p1+:30p:::*+39**6+:30g39**c-00g*10gv
>:2*1-*00g*a*^
^:p02*g02p01*a*-*g02\+g01*g00-2*5g03,+*86:/*5g02+*5<

Попробуйте онлайн!

Это границы с точки зрения сроков. 10 000 цифр на моем ноутбуке занимают около 11 секунд, но я уверен, что должен быть «разумный» ПК, который мог бы делать это быстрее, чем этот.

Однако, если вы попробуете это на TIO, обратите внимание, что он ничего не вернет, пока не достигнет 60-секундного ограничения времени, так как алгоритм разработан так, чтобы продолжать работать вечно. К тому времени у вас будет намного больше 10 000 цифр.

Я использую алгоритм spigot Джереми Гиббонс, который, я думаю, такой же, как и большинство других ответов здесь. Однако обратите внимание, что это зависит от интерпретатора, имеющего ячейки памяти произвольной точности, и единственная известная мне реализация, которая поддерживает это, - это PyFunge .

объяснение

cf*10p                     Initialise r to 180.
      '<20p                Initialise t to 60.
           11              Initialise i and q on the stack to 1.

>                          Start of the main loop.
 00p                       Save the current value of q in memory.
    1+:30p                 Increment i and save a copy in memory.      
          :::*+39**6+      Calculate u = 27*(i*i+i)+6.
                     :     Make a duplicate, since we'll need two copies later.

       30g39**c-00g*10gv   Calculate y = (q*(27*i-12)+5*r)/(5*t).
              /*5g02+*5<
        ,+*86:             Convert y to a character so we can output it.

*a*-*g02\+g01*g00-2*5g03   Calculate r = 10*u*(q*(i*5-2)+r-y*t)

         p01               Save the updated r.
     *g02                  Calculate t = t*u
  p02                      Save the updated t.

>:2*1-*00g*a*              Calculate q = 10*q*i*(i*2-1).
^:
             ^             Return to the start of the main loop.
Джеймс Холдернесс
источник