Bonnes approximations rationnelles de pi

22

Écrivez un programme qui imprime toutes les bonnes approximations rationnelles de pi avec un dénominateur <1000000, dans un ordre de dénominateur croissant. a/best une "bonne approximation rationnelle" de pi s'il est plus proche de pi que tout autre rationnel dont le dénominateur n'est pas plus grand que b.

La sortie doit avoir 167 lignes au total, et commencer et finir comme ceci:

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

Le programme le plus court gagne.

Keith Randall
la source

Réponses:

23

Golfscript, 71 70 69 caractères

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

(Suppose que vous ne passez rien sur stdin)

Je ne veux plus entendre de gémissements de la part de personnes qui n'ont pas de constantes intégrées pour pi. Je n'ai même pas de nombres à virgule flottante!

Voir http://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations pour l'arrière-plan.

# 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
la source
1
Eh bien, techniquement, GolfScript a à la fois des nombres à virgule flottante et une constante pour PI. Ça s'appelle "#{Math.PI}".
Konrad Borowski
2
@GlitchMr, en quoi une chaîne est-elle un nombre à virgule flottante?
Peter Taylor
J'aimerais vraiment voir cela déroulé avec des commentaires.
primo
Incroyable. La toute première ligne 2\!:^2^..292^15.2/3]m'a déjà époustouflé.
primo
@PeterTaylor Tied . Pouvons-nous faire mieux?
Eelvex
11

Mathematica, 67 63

Cela ne va pas être rapide, mais je pense que c'est techniquement correct.

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

Round[π, x]donne la fraction la plus proche de π par pas de x. Ceci est "listable", il en Round[π,1/Range@1*^6]va de même pour toutes les fractions 1/10^6dans l'ordre. La liste résultante avec de nombreuses "mauvaises" approximations rationnelles est ensuite //.traitée à plusieurs reprises ( ) en supprimant tous les éléments qui sont plus éloignés de π que le précédent.

Mr.Wizard
la source
Assez cool, mais je ne peux pas le tester car je n'ai pas Mathematica.
Keith Randall
@Keith, voici la logique. Round[Pi, x]donne la fraction la plus proche de Pipar pas de x. Ceci est "listable", il en Round[Pi,1/Range@1*^6]va de même pour toutes les fractions jusqu'à 1/10 ^ 6 dans l'ordre. La liste résultante avec de nombreuses "mauvaises" approximations rationnelles est ensuite répétée ( //.) en supprimant tous les éléments qui sont plus éloignés de pi que le précédent.
Mr.Wizard
Mathematica bat GolfScript. Soigné.
SpellingD
En 61: Select[Round[f=Pi,1/Range@1*^6],If[#<f,f=#;True]&@Abs[#-Pi]&]... mais inutile étant donné le biais dominant
Dr belisarius
Yarr, Matie. Soyez magique dans ce code.
Michael Stern
7

Perl, 77 caractères

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

Un défi mineur est que Perl n'a pas de constante π intégrée disponible, donc j'ai d'abord dû la calculer comme atan2(0,-1). Je suis sûr que cela sera battu par des langues plus adaptées à l'emploi, mais ce n'est pas mauvais pour une langue principalement conçue pour le traitement de texte.

Ilmari Karonen
la source
1
Vous pouvez changer 999999pour 1e6et sauver 3 caractères.
Toto
@ M42: Merci! Jusqu'à 82 caractères maintenant.
Ilmari Karonen
Vraiment sympa, $ = pour obtenir un entier. Désolé, je ne peux pas voter deux fois.
Toto
Je n'arrive pas à faire fonctionner ceci:String found where operator expected at prog.pl line 1, near "say"$=/$_""
Keith Randall
@KeithRandall: Vous avez besoin du -M5.01commutateur (et Perl 5.10.0 ou version ultérieure) pour la saycommande. Désolé de ne pas l'avoir mentionné.
Ilmari Karonen
5

Python, 96 93 89 caractères

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 caractères, algorithme différent

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

note: Il y avait moins de caractères à écrire p=3.14159265359;que from math import*. Darn ces importations verbeuses!

Steven Rumbalski
la source
1
Quelques raccourcissements: 1.0-> 1., 10**6->1e6
Keith Randall
J'ai mis à jour vos améliorations. Merci beaucoup.
Steven Rumbalski
@KeithRandall, mais le second de ceux-ci fait que la sortie viole les spécifications.
Peter Taylor
Dans la seconde approche, la variable p n'est pas nécessaire. C'est 4 caractères.
Ante
@PeterTaylor: Je ne comprends pas. Comment cela viole-t-il la spécification?
Steven Rumbalski
4

JS (95 caractères)

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)

Il imprime 167 lignes.

JiminP
la source
4

Ruby 1.9, 84 caractères

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
la source
@Peter Taylor Vous avez raison. Vous devez utiliser Ruby 1.9.
Howard
4

C99, 113 caractères

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);}

Besoin de compiler avec -lm, et probablement plein de comportements non définis, mais cela fonctionne pour moi.

Thomas
la source
2

Scala - 180 caractères

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)

// non golfé: 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) 
  }  
}

L'annotation tailrec n'est qu'une vérification, pour vérifier, qu'elle est récursive, ce qui est souvent une amélioration des performances.

Utilisateur inconnu
la source
Je n'arrive pas à faire fonctionner cela:pi.scala:1 error: not found: value math
Keith Randall
Utilisez-vous Scala 2.8?
utilisateur inconnu
Mon scala dit "version inconnue", bizarre. Sur ideone.com, ils utilisent 2.8.0 et je reçois toujours des erreurs.
Keith Randall
Essayez-le sur simplyscala.com - fonctionne pour moi. Pour scala-2.8, le remplacement mathpar Mathpeut être suffisant. J'ai mentionné simplyscala sur ce métathread, s'il vous arrive de le rechercher à nouveau: meta.codegolf.stackexchange.com/a/401/373
utilisateur inconnu
OK, ça marche.
Keith Randall
2

Mathematica 18 17 caractères

J'ai choisi d'utiliser, comme mesure du «meilleur», le nombre de termes dans une représentation de fraction continue de π. Selon ce critère, les meilleures approximations rationnelles de π sont ses convergentes.

Il existe 10 convergents de π avec un dénominateur inférieur à un million. C'est moins que les 167 conditions demandées, mais je l'inclus ici car cela peut intéresser les autres.

Convergents[π, 10] 

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

Si vous voulez vraiment voir le dénominateur du premier convergent, il vous en coûtera 11 caractères supplémentaires:

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}

Pour ceux qui sont intéressés, ce qui suit montre les relations entre les convergents, les quotients partiels et l'expression continue des fractions des convergents de π:

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]

fractions continues

Veuillez excuser la mise en forme incohérente des fractions continues.

DavidC
la source
C'est à mi-chemin d'une solution, mais c'est la moitié la plus simple. Ma solution GolfScript code en dur une représentation appropriée de la fraction continue en seulement 2 caractères supplémentaires.
Peter Taylor
Mais vous n'avez pas utilisé de fractions continues pour votre solution à cette question, n'est-ce pas?
DavidC
Oui. C'était la façon évidente de le faire.
Peter Taylor
En plus d'être concis, c'est beaucoup plus rapide que la plupart ou la totalité des autres solutions qui ont été publiées.
Michael Stern
1

C # 140 129 caractères

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++;}

Code non compressé

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
la source
2
varn'est pas toujours ton ami. En le supprimant en votre faveur, doublevous avez la possibilité de fusionner des déclarations, vous n'avez plus besoin d'utiliser des doubles littéraux et vous pouvez enregistrer 16 caractères. OTOH, la question demande un programme, vous en perdrez donc quelques uns en ajoutant une déclaration de classe et une Mainméthode.
Peter Taylor
1

J, 69 65

Nouveau

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

Toujours une approche brutale mais beaucoup plus rapide et un peu plus courte.

Vieux

Une simple "force brute":

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

faire une liste de a/bs puis éliminer ceux qui sont plus éloignés de π pour certains b'<b.

Remarque: passez 1e3à 1e6pour la liste complète. Allez faire autre chose et revenez plus tard.

Eelvex
la source