Gute rationale Näherungen von pi

22

Schreiben Sie ein Programm, das alle guten rationalen Näherungen von pi mit einem Nenner <1000000 in aufsteigender Nennerreihenfolge ausgibt. a/bist eine "gute rationale Approximation" von pi, wenn es näher an pi liegt als jedes andere Rationale mit einem Nenner, der nicht größer ist als b.

Die Ausgabe sollte insgesamt 167 Zeilen enthalten und wie folgt beginnen und enden:

3/1
13/4
16/5
19/6
22/7
179/57
...
833719/265381
1146408/364913
3126535/995207

Kürzeste Sendung gewinnt.

Keith Randall
quelle

Antworten:

23

Golfscript, 71 70 69 Zeichen

2\!:^2^..292^15.2/3]{(.)2/.9>+{\+.((}*;.}do;;]-1%{^0@{2$*+\}/"/"\n}/;

(Angenommen, Sie geben nichts an stdin weiter)

Ich möchte von Leuten, die keine eingebauten Konstanten für pi haben, kein Surren mehr hören. Ich habe nicht einmal Gleitkommazahlen!

Informationen zum Hintergrund finden Sie unter http://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations .

# No input, so the stack contains ""
2\!:^2^..292^15.2/3]
# ^ is used to store 1 because that saves a char by allowing the elimination of whitespace
# Otherwise straightforward: stack now contains [2 1 2 1 1 1 292 1 15 7 3]
# Pi as a continued fraction is 3+1/(7+1/(15+1/(...)))
# If you reverse the array now on the stack you get the first 10 continuants followed by 2
# (rather than 3)
# That's a little hack to avoid passing the denominator 1000000

{
    # Stack holds: ... [c_n c_{n-1} ... c_0]
    (.)2/.9>+
    # Stack holds ... [c_{n-1} ... c_0] c_n (1+c_n)/2+((1+c_n)/2 > 9 ? 1 : 0)
    # (1+c_n)/2 > 9 is an ad-hoc approximation of the "half rule"
    # which works in this case but not in general
    # Let k = (1+c_n)/2+((1+c_n)/2 > 9 ? 1 : 0)
    # We execute the next block k times
    {
        # ... [c_{n-1} ... c_0] z
        \+.((
        # ... [z c_{n-1} ... c_0] [c_{n-1} ... c_0] z-1
    }*
    # So we now have ... [c_n c_{n-1} ... c_0] [(c_n)-1 c_{n-1} ... c_0] ...
    #                    [(c_n)-k+1 c_{n-1} ... c_0] [c_{n-1} ... c_0] c_n-k
    ;
    # Go round the loop until the array runs out
    .
}do

# Stack now contains all the solutions as CFs in reverse order, plus two surplus:
# [2 1 2 1 1 1 292 1 15 7 3] [1 2 1 1 1 292 1 15 7 3] ... [6 3] [5 3] [4 3] [3] [2] []
# Ditch the two surplus ones, bundle everything up in an array, and reverse it
;;]-1%

# For each CF...
{
    # Stack holds ... [(c_n)-j c_{n-1} ... c_0]
    # We now need to convert the CF into a rational in canonical form
    # We unwind from the inside out starting with (c_n)-j + 1/infinity,
    # representing infinity as 1/0
    ^0@
    # ... 1 0 [c_n-j c_{n-1} ... c_0]
    # Loop over the terms of the CF
    {
        # ... numerator denominator term-of-CF
        2$*+\
        # ... (term-of-CF * numerator + denominator) numerator
    }/

    # Presentation
    "/"\n
    # ... numerator "/" denominator newline
}/

# Pop that final newline to avoid a trailing blank line which isn't in the spec
;
Peter Taylor
quelle
1
Nun, technisch gesehen hat GolfScript sowohl Gleitkommazahlen als auch Konstanten für PI. Es heißt "#{Math.PI}".
Konrad Borowski
2
@GlitchMr, inwiefern ist ein String eine Gleitkommazahl?
Peter Taylor
Ich würde das wirklich gerne mit Kommentaren sehen.
Primo
Tolle. Die allererste Zeile 2\!:^2^..292^15.2/3]hat mich schon umgehauen.
Primo
@PeterTaylor Gebunden . Können wir es besser machen?
Eelvex
11

Mathematica, 67, 63

Das wird nicht schnell gehen, aber ich glaube, es ist technisch korrekt.

Round[π,1/Range@1*^6]//.x_:>First/@Split[x,#2≥#&@@Abs[π-{##}]&]

Round[π, x]gibt den nächsten Bruch zu π in Schritten von an x. Dies ist "auflistbar", dies Round[π,1/Range@1*^6]gilt auch für alle Brüche 1/10^6in der angegebenen Reihenfolge. Die resultierende Liste mit vielen "schlechten" rationalen Approximationen wird dann wiederholt ( //.) verarbeitet, indem alle Elemente entfernt werden, die weiter von π entfernt sind als das vorhergehende.

Mr.Wizard
quelle
Ziemlich cool, aber ich kann es nicht testen, weil ich kein Mathematica habe.
Keith Randall
@ Keith, hier ist die Logik. Round[Pi, x]gibt den nächsten Bruch Piin Schritten von an x. Dies ist "auflistbar", dies Round[Pi,1/Range@1*^6]gilt auch für alle Brüche bis hinunter zu 1/10 ^ 6 in der Reihenfolge. Die resultierende Liste mit vielen "schlechten" rationalen Approximationen wird dann wiederholt ( //.) verarbeitet, indem alle Elemente entfernt werden, die weiter von pi entfernt sind als das vorhergehende.
Mr.Wizard
Mathematica schlägt GolfScript. Ordentlich.
Rechtschreibung:
In 61: Select[Round[f=Pi,1/Range@1*^6],If[#<f,f=#;True]&@Abs[#-Pi]&]... aber angesichts der vorherrschenden
Tendenz
Yarr, Matie. In diesem Code bist du magisch.
Michael Stern
7

Perl, 77 Zeichen

$e=$p=atan2 0,-1;($f=abs$p-($==$p*$_+.5)/$_)<$e&&($e=$f,say"$=/$_")for 1..1e6

Eine kleine Herausforderung ist, dass Perl keine eingebaute π- Konstante zur Verfügung hat, also musste ich sie zuerst als berechnen atan2(0,-1). Ich bin sicher, dass dies von Sprachen übertroffen wird, die besser für den Job geeignet sind, aber es ist nicht schlecht für eine Sprache, die hauptsächlich für die Textverarbeitung entwickelt wurde.

Ilmari Karonen
quelle
1
Sie könnte sich ändern , 999999um 1e63 Zeichen speichern.
Toto
@ M42: Danke! Bis zu 82 Zeichen jetzt.
Ilmari Karonen
Wirklich nett, $ = Integer zu bekommen. Entschuldigung, ich kann nicht zweimal upvoten.
Toto
Ich kann das nicht zum Laufen bringen:String found where operator expected at prog.pl line 1, near "say"$=/$_""
Keith Randall
@KeithRandall: Sie benötigen den -M5.01Schalter (und Perl 5.10.0 oder höher) für den sayBefehl. Entschuldigung, dass ich das nicht erwähne.
Ilmari Karonen
5

Python, 96 93 89 Zeichen

a=b=d=1.
while b<=1e6:
 e=3.14159265359-a/b;x=abs(e)
 if x<d:print a,b;d=x
 a+=e>0;b+=e<0

Python, 95 93 Zeichen, anderer Algorithmus

p=3.14159265359;d=1
for a in range(3,p*1e6):
 b=round(a/p);e=abs(p-a/b)
 if e<d:print a,b;d=e

Hinweis: Es waren weniger Zeichen zu schreiben p=3.14159265359;als from math import*. Verdammt diese wortreichen Importe!

Steven Rumbalski
quelle
1
Einige Kürzungen: 1.0-> 1., 10**6->1e6
Keith Randall
Ich habe mit Ihren Verbesserungen aktualisiert. Vielen Dank.
Steven Rumbalski
@KeithRandall, aber die zweite davon führt dazu, dass die Ausgabe die Spezifikation verletzt.
Peter Taylor
Im zweiten Ansatz ist die Variable p nicht erforderlich. Das sind 4 Zeichen.
Ante
@ PeterTaylor: Ich verstehe nicht. Wie verstößt es gegen die Spezifikation?
Steven Rumbalski
4

JS (95 Zeichen)

for(i=k=1,m=Math;i<1e6;i++)if((j=m.abs((x=m.round(m.PI*i))/i-m.PI))<k)k=j,console.log(x+'/'+i)

Es werden 167 Zeilen gedruckt.

JiminP
quelle
4

Ruby 1.9, 84 Zeichen

m=1;(1..1e6).map{|d|n=(d*q=Math::PI).round;k=(n-q*d).abs/d;k<m&&(m=k;puts [n,d]*?/)}
Howard
quelle
@ Peter Taylor Du hast recht. Sie müssen Ruby 1.9 verwenden.
Howard
4

C99, 113 Zeichen

main(d,n){double e=9,p=2*asin(1),c,a=1;for(;n=d*p+.5,c=fabsl(p-a*n/d),d<1e6;++d)c<e&&printf("%d/%d\n",n,d,e=c);}

Müssen kompilieren -lmund wahrscheinlich voller undefinierter Verhalten, aber es funktioniert bei mir.

Thomas
quelle
2

Scala - 180 Zeichen

import math._
def p(z:Int,n:Int,s:Double):Unit=
if(n==1e6)0 else{val q=1.0*z/n
val x=if(abs(Pi-q)<s){println(z+"/"+n)
abs(Pi-q)}else s
if(Pi-q<0)p(z,n+1,x)else p(z+1,n,x)}
p(3,1,1)

// ungolfed: 457

val pi=math.Pi
@annotation.tailrec
def toPi (zaehler: Int = 3, nenner: Int = 1, sofar: Double=1): Unit = {
  if (nenner == 1000000) () 
  else {
    val quotient = 1.0*zaehler/nenner
    val diff = (pi - quotient)
    val adiff= math.abs (diff)
    val next = if (adiff < sofar) {
      println (zaehler + "/" + nenner) 
      adiff 
    }
    else sofar
    if (diff < 0) toPi (zaehler, nenner + 1, next) 
    else toPi (zaehler + 1, nenner, next) 
  }  
}

Die Tailrec-Annotation ist nur eine Überprüfung, um sicherzustellen, dass sie rekursiv ist, was häufig eine Leistungsverbesserung darstellt.

Benutzer unbekannt
quelle
Ich kann das nicht zum Laufen bringen:pi.scala:1 error: not found: value math
Keith Randall
Verwenden Sie Scala 2.8?
Benutzer unbekannt
Meine Waage sagt "unbekannte Version", komisch. Auf ideone.com verwenden sie 2.8.0 und ich erhalte immer noch Fehler.
Keith Randall
Probieren Sie es einfach unter simplyscala.com aus - funktioniert bei mir. Für scala-2.8 kann das Ersetzen mathdurch Mathausreichend sein. Ich habe simplyscala auf diesem Metakopf erwähnt, falls Sie noch einmal danach suchen: meta.codegolf.stackexchange.com/a/401/373
Benutzer unbekannt
OK, das funktioniert.
Keith Randall
2

Mathematica 18 17 Zeichen

Ich habe mich dafür entschieden, die Anzahl der Terme in einer fortgesetzten Bruchdarstellung von π als Maß für "das Beste" zu verwenden. Nach diesem Kriterium sind die besten rationalen Näherungen für π die Konvergenten.

Es gibt 10 Konvergenten von π mit einem Nenner von weniger als einer Million. Dies ist weniger als die angeforderten 167 Begriffe, aber ich beziehe es hier ein, weil es für andere von Interesse sein kann.

Convergents[π, 10] 

(* out *)
{3, 22/7, 333/106, 355/113, 103993/33102, 104348/33215, 208341/66317,
312689/99532, 833719/265381, 1146408/364913}

Wenn Sie den Nenner für die erste Konvergenz wirklich sehen möchten, kostet dies zusätzlich 11 Zeichen:

Convergents[π, 10] /. {3 -> "3/1"}
(* out *)
{"3/1", 22/7, 333/106, 355/113, 103993/33102, 104348/33215,
208341/66317, 312689/99532, 833719/265381, 1146408/364913}

Für diejenigen, die interessiert sind, zeigt das Folgende die Beziehungen zwischen den Konvergenten, Teilquotienten und der fortgesetzten Bruchexpression von Konvergenten von π:

Table[ContinuedFraction[π, k], {k, 10}]
w[frac_] := Row[{Fold[(#1^-1 + #2) &, Last[#], Rest[Reverse[#]]] &[Text@Style[#, Blue, Bold, 14] & /@ ToString /@ ContinuedFraction[frac]]}];
w /@ FromContinuedFraction /@ ContinuedFraction /@ Convergents[π, 10]

fortgesetzte Fraktionen

Bitte entschuldigen Sie die inkonsistente Formatierung der fortgesetzten Brüche.

DavidC
quelle
Das ist ungefähr die Hälfte einer Lösung, aber die einfachste Hälfte. Meine GolfScript-Lösung codiert eine geeignete Darstellung des fortgesetzten Bruchs in nur 2 weiteren Zeichen.
Peter Taylor
Aber Sie haben keine fortgesetzten Brüche für Ihre Lösung dieser Frage verwendet, oder?
DavidC
Ja. Es war der offensichtliche Weg, dies zu tun.
Peter Taylor
Dies ist nicht nur übersichtlich, sondern auch viel schneller als die meisten oder alle anderen Lösungen, die veröffentlicht wurden.
Michael Stern
1

C # 140 129 Zeichen

double n=3,d=1,e=d;while(n<4e5){double w=n/d-Math.PI,a=Math.Abs(w);if(a<e){e=a;Console.WriteLine(n+"/"+d);}if(w>0)d++;else n++;}

Nicht komprimierter Code

var numerator = 3d;
var denominator = 1d;
var delta = 4d;
while (numerator < 4e5) 
{
    var newDelta = (numerator / denominator) - Math.PI;
    var absNewDelta = Math.Abs(newDelta);
    if (absNewDelta < delta)
    {
        delta = absNewDelta;
        Console.WriteLine(string.Format("{0}/{1}", numerator, denominator));
    }

    if (newDelta > 0)
    {
        denominator++;
    }
    else
    {
        numerator++;
    }
}
Jader Dias
quelle
2
varist nicht immer dein Freund. Wenn Sie es zu Ihren Gunsten entfernen, können Sie doubleDeklarationen zusammenführen, müssen keine doppelten Literale mehr verwenden und können 16 Zeichen sparen. OTOH die Frage fragt nach einem Programm, so dass Sie ein paar verlieren, um eine Klassendeklaration und eine MainMethode hinzuzufügen .
Peter Taylor
1

J 69, 65

Neu

]`,@.(<&j{.)/({~(i.<./)@j=.|@-l)@(%~(i:3x)+<.@*l=.1p1&)"0>:_i.1e3

Immer noch ein Brute-Force-Ansatz, aber viel schneller und ein bisschen kürzer.

Alt

Eine einfache "Brute Force":

(#~({:<<./@}:)\@j)({~(i.<./)@j=.|@-l)@(%~(i:6x)+<.@*l=.1p1&)"0>:i.1e3

mache eine Liste von a/bs und verwerfe dann diejenigen, die für einige weiter von π entfernt sind b'<b.

Hinweis: Wechseln Sie 1e3zu, 1e6um die vollständige Liste anzuzeigen. Mach etwas anderes und kehre später zurück.

Eelvex
quelle