5 Detik untuk Menemukan Kue

11

Pi kali e (atau Pai jika Anda suka notasi ambigu) ke 100 tempat desimal adalah:

8.5397342226735670654635508695465744950348885357651149618796011301792286111573308075725638697104739439...

( OIES A019609 ) ( argumen untuk kemungkinan irasionalitas )

Tugas Anda adalah menulis sebuah program yang menghasilkan bilangan bulat positif N, dan menghasilkan Pi * e yang terpotong ke N tempat desimal. misal jika N = 2, maka output seharusnya 8.53.

Ini adalah masalah optimisasi, sehingga pengiriman yang dapat memberikan output yang benar untuk nilai N tertinggi akan menang.

Untuk memastikan semua kiriman dinilai menggunakan kekuatan komputasi yang sama, kode Anda harus dijalankan pada ideone , menggunakan bahasa apa pun yang mereka dukung. Menurut faq ideone , ada batas waktu 5 detik untuk pengguna yang tidak masuk. Batas 5 detik ini adalah yang harus Anda gunakan, bukan batas 15 detik untuk pengguna yang masuk. (Lihat faq untuk batas lain seperti memori, ukuran kode, dll.)

Khususnya, siapa pun yang tidak masuk ke ideone harus dapat menjalankan program Anda pada ideone untuk semua nilai N dari 1 hingga beberapa Nmax maksimum, dan melihat output yang benar hampir sepanjang waktu . tanpa kesalahan Time limit exceededatau Memory limit exceeded, dll. Pengajuan dengan Nmax terbesar akan menang.

(Apakah waktu sebenarnya yang diperlukan adalah smidge lebih dari 5 detik tidak masalah asalkan ideone tidak memberikan kesalahan. " Hampir sepanjang waktu " didefinisikan sebagai lebih dari 95% waktu untuk setiap N. tertentu)

Detail

  • Anda dapat menggunakan metode matematika apa pun yang Anda suka untuk menghitung Pi * e, tetapi Anda tidak dapat meng-hardcode output di luar selusin digit pertama dari Pi, e atau Pi * e .
    • Program Anda harus dapat bekerja untuk N apa pun, mengingat sumber daya tidak terbatas.
    • Anda dapat menggunakan konstanta built in Pi atau e jika bahasa Anda kebetulan memilikinya.
  • Anda tidak boleh mengakses situs web atau sumber daya di luar kode Anda (jika ideone bahkan mengizinkan ini).
  • Di luar hardcoding dan mengakses sumber daya eksternal, apa pun yang memungkinkan ideone hampir pasti baik-baik saja.
  • Input dan output Anda harus (jelas) bekerja dengan apa pun yang disediakan ideone untuk i / o (hanya stdin / stdout). Tidak apa-apa jika Anda perlu tanda kutip di sekitar input N atau outputnya seperti ans = ..., dll.
  • Harap sertakan tautan ke cuplikan ideone kode Anda dengan Nmax Anda sebagai masukan.
  • Jika ada ikatan (kemungkinan hanya jika banyak pengiriman mencapai batas karakter keluaran 64kB) jawaban suara tertinggi menang.
Hobi Calvin
sumber
3
Mmm ... kue ambigu.
Dennis
Ini bisa dengan mudah menjadi kode-golf dan lebih suka lebih menyenangkan jika itu.
Pengoptimal
2
@Optimizer Ini bisa berupa kode-golf tetapi kemudian akan cukup banyak seperti setiap kode generasi-golf lainnya. Saya ingin mencoba kontes berbasis waktu yang dapat diverifikasi secara online. (Meskipun masalah yang lebih kompleks secara komputasional mungkin lebih baik.)
Calvin's Hobbies
jika ini kode golf APL mungkin akan menang (minus bagian presisi yang berubah-ubah)
TwiNight
1
Saya menduga bahwa program-program ini akan sepenuhnya IO terikat mencoba untuk menulis digit ke stdout. Lima detik adalah waktu yang lama untuk sesuatu seperti y-cruncher .
Will

Jawaban:

12

Python - 65535

http://ideone.com/knKRhn

from math import exp, log

def divnr(p, q):
  """
    Integer division p/q using Newton-Raphson Division.
    Assumes p > q > 0.
  """

  sp = p.bit_length()-1
  sq = q.bit_length()-1
  sr = sp - sq + 1

  s = []
  t = sr
  while t > 15:
    s = [t] + s
    t = (t>>1) + 1
  # Base-case division
  r = (1 << (t<<1)) / (q >> sq-t)

  for u in s:
    r = (r << u-t+1) - (r*r * (q >> sq-u) >> (t<<1))
    t = u
  return (r * (p >> sq)) >> sr

def pibs(a, b):
  if a == b:
    if a == 0:
      return (1, 1, 1123)
    p = a*(a*(32*a-48)+22)-3
    q = a*a*a*24893568
    t = 21460*a+1123
    return (p, -q, p*t)
  m = (a+b) >> 1
  p1, q1, t1 = pibs(a, m)
  p2, q2, t2 = pibs(m+1, b)
  return (p1*p2, q1*q2, q2*t1 + p1*t2)

def ebs(a, b):
  if a == b:
    if a == 0:
      return (1, 1)
    return (1, a)
  m = (a+b) >> 1
  p1, q1 = ebs(a, m)
  p2, q2 = ebs(m+1, b)
  return (p1*q2+p2, q1*q2)

if __name__ == '__main__':
  n = input()

  pi_terms = int(n*0.16975227728583067)

  # 10^n == e^p
  p = n*2.3025850929940457

  # Lambert W_0(p/e) a la Newton
  k = log(p) - 1
  w = k - (k-1)/(k+1)
  while k > w:
    k = w
    w -= (k - p*exp(-k-1))/(k+1)

  # InverseGamma(e^p) approximation
  e_terms = int(p / w)

  pp, pq, pt = pibs(0, pi_terms)
  ep, eq = ebs(0, e_terms)

  z = 10**n
  p = 3528*z*ep*abs(pq)
  q = eq*abs(pt)

  pie = divnr(p, q)
  print pie,

Ideone tampaknya tidak gmpy2diinstal, yang sangat disayangkan karena setidaknya dua alasan. Satu, karena itu akan membuat perhitungan jauh lebih cepat, dan dua, karena itu membuat formula apa pun yang membutuhkan akar kuadrat presisi yang sewenang-wenang tidak praktis.

Rumus saya gunakan untuk π telah terdaftar oleh Ramanujan sebagai Formula (39):

yang konvergen pada tingkat ~ 5,89 digit per term. Sepengetahuan saya, ini adalah seri konvergen tercepat dari jenisnya yang tidak memerlukan evaluasi dari akar kuadrat presisi arbitrer. Formula (44) di koran yang sama (tingkat konvergensi ~ 7.98 digit per istilah) yang paling sering disebut sebagai the Formula Ramanujan.

Rumus yang saya gunakan untuk e adalah jumlah faktorial terbalik. Jumlah istilah yang diperlukan dihitung sebagai Γ -1 ( 10 n ), menggunakan perkiraan yang saya temukan pada mathoverflow . Komponen Lambert W 0 ditemukan menggunakan Metode Newton.

Perhitungan masing-masing penjumlahan ini dilakukan melalui Fast E-function Evalution (lebih dikenal sebagai binary-splitting), yang awalnya dirancang oleh Karatsuba. Metode ini mengurangi penjumlahan ke n istilah menjadi nilai rasional tunggal p / q . Kedua nilai ini kemudian dikalikan untuk menghasilkan hasil akhir.

Pembaruan:
Pembuatan profil mengungkapkan bahwa lebih dari separuh waktu yang dibutuhkan untuk perhitungan dihabiskan di divisi akhir. Hanya sebagian besar log 2 (10 n ) bit q yang diperlukan untuk mendapatkan presisi penuh, jadi saya memotong beberapa sebelumnya. Kode sekarang mengisi buffer output Ideone dalam 3,33s .

Pembaruan 2:
Karena ini adalah tantangan , saya memutuskan untuk menulis rutin divisi saya sendiri untuk memerangi kelambatan CPython. Implementasi di divnratas menggunakan Divisi Newton-Raphson . Gagasan umum adalah menghitung d = 1 / q · 2 n menggunakan Metode Newton, di mana n adalah jumlah bit yang dibutuhkan oleh hasil, dan menghitung hasilnya sebagai p · d >> n . Runtime sekarang 2.87s - dan ini bahkan tanpa memotong bit sebelum perhitungan; itu tidak perlu untuk metode ini.

primo
sumber
4

PARI / GP: 33000

Ini pada dasarnya adalah program yang diberikan di OEIS , dimodifikasi untuk mengambil input dan memformat output dengan benar. Ini harus berfungsi sebagai garis dasar untuk dikalahkan, jika tidak ada yang lain.

Saya menganggap ini akurat. Saya memeriksanya pada 100 dan 20k melawan OEIS, dan cocok untuk keduanya. Cukup sulit menemukan digit lebih lanjut daring untuk diperiksa.

Untuk 33.000 dibutuhkan sekitar 4,5s, jadi mungkin bisa sedikit menabrak. Saya baru saja bosan mengutak-atik input dan lambat-ass loop / assile / run loop ideone.

{ 
    m=eval(input());
    default(realprecision, m+80); 
    x=Pi*exp(1);
    s="8.";
    d=floor(x);
    x=(x-d)*10;
    for (n=1, m, d=floor(x); 
         x=(x-d)*10; 
         s=Str(s,d));
    print(s);
}

Tautan Ideone.com

Geobit
sumber
Digit Anda cocok dengan milik saya, jadi saya akan mengambil risiko dan mengatakan mereka mungkin benar.
Primo
Program ini pada dasarnya menghabiskan seluruh waktunya dalam lingkaran, menghasilkan angka satu per satu. Jika Anda hanya mengambilnya Str(floor(frac(x)*10^m)berjalan ratusan / ribuan kali lebih cepat.
Charles
2

Python 3

Karena built in pi dan e tidak memiliki angka yang cukup, saya memutuskan untuk menghitung sendiri.

import decimal
import math
decimal.getcontext().prec=1000000
decimal=decimal.Decimal;b=2500
print(str(sum([decimal(1/math.factorial(x)) for x in range(b)])*sum([decimal(1/16**i*(4/(8*i+1)-2/(8*i+4)-1/(8*i+5)-1/(8*i+6))) for i in range(b)]))[0:int(input())+2])

Tautan IDEOne

Output untuk STDIN = 1000:

8.5397342226735669504281233688422467204743749305568824722710929852470173635361001388261308713809518841081669216573834376992066672804294594807026609638293539437286935503772101801433821053915371716284188665787967232464763808892618434263301810056154560438283877633957941572944822034479453916753507796910068912594560500836608215235605783723340714760960119319145912948480279651779184356994356172418603464628747082162475871780202868607325544781551065680583616058471475977367814338295574582450942453416002008665325253385672668994300796223139976640645190237481531851902147391807396201201799703915343423499008135819239684881566321559967077443367982975103648727755579256820566722752546407521965713336095320920822985129589997143740696972018563360331663471959214120971348584257396673542429063767170337770469161945592685537660073097456725716654388703941509676413429681372333615691533682226329180996924321063261666235129175134250645330301407536588271020457172050227357541822742441070313522061438812060477519238440079
Peluruhan Beta
sumber
Nmax adalah nilai input terbesar yang dapat Anda berikan pada program Anda sebelum ideone tidak lagi menjalankannya.
Calvin Hobbies
1
@ CalvinHobbies Saya berpikir bahwa nmax adalah arbitrrary besar sekalipun ...
Beta Decay
1
ideone tidak memberi Anda kekuatan komputasi yang tak terbatas. Apa nilai input terbesar yang bisa dijalankan oleh program Anda di ideone? (Meskipun sebenarnya program Anda tidak mengikuti should be able to work for any N, given unlimited resourcesaturan. Sebagian besar hasilnya nol di sekitar N = 10000.)
Calvin Hobbies
Itu tidak python3: NameError: name 'xrange' not defined.
Bakuriu
2

Scala - 1790

IDEOne di http://ideone.com/A2CIto .

Kami menggunakan rumus Wetherfield untuk π (dan kode rumus Machin diangkut secara kasar dari sini ). Kami menghitung e menggunakan seri daya biasa.

object Main extends App {
  import java.math.{BigDecimal => JDecimal}
  import java.math.RoundingMode._
  import scala.concurrent.Future
  import scala.concurrent.Await
  import scala.concurrent.ExecutionContext.Implicits._
  import scala.concurrent.duration._
  val precision = 1800

  def acotPrecision(numDigits: Int)(x: BigDecimal) = {
    val x1 = x.underlying
    val two = JDecimal.valueOf(2)
    val xSquared = x1 pow 2
    val unity = JDecimal.ONE.setScale(numDigits, HALF_EVEN)
    var sum = unity.divide(x1, HALF_EVEN)
    var xpower = new JDecimal(sum.toString)
    var term = unity

    var add = false

    var n = JDecimal.valueOf(3).setScale(numDigits)
    while (term.setScale(numDigits, HALF_EVEN).compareTo(JDecimal.ZERO) != 0) {
      xpower = xpower.divide(xSquared, HALF_EVEN)
      term = xpower.divide(n, HALF_EVEN)
      sum = if (add) sum add term else sum subtract term
      add = !add
      n = n add two
    }
    sum
  }

  def ePrecision(numDigits: Int) = {
    val zero = JDecimal.ZERO
    var sum = zero
    var term = JDecimal.ONE.setScale(numDigits, HALF_EVEN)
    var n = JDecimal.ONE.setScale(numDigits, HALF_EVEN)
    while(term.setScale(numDigits, HALF_EVEN).compareTo(zero) != 0) {
      sum = sum add term
      term = term.divide(n, HALF_EVEN)
      n = n add JDecimal.ONE
    }
    sum
  }

  val acot = acotPrecision(precision) _

  def d(x: Int) = JDecimal.valueOf(x)

  def piFuture = Future(d(4) multiply (
    (d(83) multiply acot(107)) add (d(17) multiply acot(1710)) subtract (d(22) multiply acot(103697))
    subtract (d(24) multiply acot(2513489)) subtract (d(44) multiply acot(18280007883L))
   add (d(12) multiply acot(7939642926390344818L))
   add (d(22) multiply acot(BigDecimal("3054211727257704725384731479018")))
  ))

  def eFuture = Future(ePrecision(precision))

  Await.result(
    for (pi <- piFuture;
         e <- eFuture) yield println((pi multiply e).setScale(precision - 10, DOWN))
  , 5 seconds) 
}
James_pic
sumber