[Mini-Challenge Basic #7] : Pi

[pierrotdu18]

Bonjour à tous

Comme je ne sais pas quoi faire je vous propose un nouveau défi !

Ce dernier consiste à trouver les 500 premières décimales de

$mathjax$\pi$mathjax$

.

Règles :

• Le programme devra s'appeler getPi()
• Il devra renvoyer une string qui contiendra les chiffres de
  $mathjax$\pi$mathjax$
  , cette chaîne doit commencer par "3.14" et non par "314"
• Il est interdit d'utiliser une LUT (ou une "LUS" Adriweb... ), tous les chiffres du premier au dernier devront être générés par votre algorithme
• Il est interdit de se servir de commandes ou de constantes proposées par la calculatrice pour pouvoir générer les premiers chiffres
• Les appels aux fonctions nécessitant le CAS sont autorisées

Évaluation :

• Le programme que vous proposerez vous vaudra un résultat qui devra être le plus petit possible
• Ce résultat sera égal au temps d’exécution de votre programme multiplié par la longueur de son code en caractères
• Les caractères seront comptés à partir de "Prgm" jusqu'à "EndPrgm" exclus
• Les retours à la ligne ainsi que TOUS les espaces ne sont pas comptabilisés
• Les tests de vitesse se feront sur ma calculatrice (TI-Nspire CX CAS 3.6 Ndlessée, non overclockée)

Bonne programmations à vous et n'hésitez pas à me dire si mes règles sont trollables (même si j'ai essayé d'éviter le plus gros... )

PS: Vous m'enverrez votre code par MP, et j'annoncerai publiquement vos résultats (temporaires ou pas). Vous pouvez envoyer autant de participations que vous voudrez, seul la meilleure sera retenue.


Le défi se terminera le 15 juillet à 12h00

[Adriweb]

Mon algorithme est simple, il renvoie un string contenant ce qu'on veut, même pas besoin de LUT

Code: Select all

Return "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989"

[pierrotdu18]

Non, non, non, non, non, non, non

Par LUT je restreins à toutes les chaînes de caractères qui te permettraient de troller

[Bisam]

Bon, je pensais au départ que c'était vraiment trop pour les capacités de la calculette, mais finalement, c'est largement faisable, même si l'algo que j'ai pour l'instant mettrait environ 1h15 pour calculer les 1000 décimales.

J'ai pour l'instant une solution en 300 caractères environ qui met 10 secondes pour 50 décimales et 43 secondes pour 100 décimales.
(Mince, j'ai fait une fonction "calculpi" au lieu d'un programme "getPi" mais bon, je ne crois pas qu'on m'en tiendra rigueur...)

[pierrotdu18]

Ah cool !
J'espère que tu iras en dessous de 1h

En tout cas quand tu auras une version "officielle" tu me l'enverras par MP

[Bisam]

Je progresse...
Je suis à 12 secondes pour 300 décimales et 47 secondes pour 500 décimales.

[Edit] À présent, 7 secondes pour 300 décimales et 26 secondes pour 500 décimales. Je pense que les 1000 décimales sont maintenant facilement atteignables... si je n'ai pas un dépassement de ressources !

[Adriweb]

GG
Hâte de voir ce fameux algo optimisé

[Bisam]

J'ai un bug...
Je n'obtiens que 792 décimales... et ensuite, j'ai des "iPart(undef)".
Pour l'instant, je ne sais pas trop d'où ça vient, mais je soupconne un dépassement de capacité.

[Bisam]

Bon, j'ai beau tourner le problème dans tous les sens, je ne vois pas comment faire mieux que ces 792 décimales... à moins de changer encore d'algorithme.
Le problème est que les entiers que j'utilise dépassent la valeur maximale d'un entier sur Nspire (à savoir 2^3296-1, soit environ 10^992)
Le seul moyen de m'en sortir serait de faire une gestion des nombres entiers plus grands... j'y viendrai peut-être plus tard.

Voici le 1er code que j'avais avec l'algorithme compte-gouttes :

Code: Select all

Define calculpi(n)=
Func
Local m,p,r,s,ret,i,j,st
n+1→n
newList(n)→p
intDiv(10n,3)+4→m
20+newList(m+1)→r
0→ret
For i,1,n
  For j,m,1,-1
    r[j+1]+ret→s
    mod(s,2j+1)→r[j+1]
    intDiv(s,2j+1)*j→ret
  EndFor
  r[1]+ret→s
  If s>99 Then
    p[i-1]+intDiv(s,100)→p[i-1]
    mod(s,100)→s
  EndIf
  mod(s,10)→r[1]
  intDiv(s,10)→p[i]
  10r→r
EndFor
"3,"→st
For i,2,n
  st&string(p[i])→st
EndFor
EndFunc

Mais ce code n'était pas très performant car quadratique (mais ne manipulant que de petits nombres...)

J'ai donc trouvé un autre algorithme (qui fait en fait les mêmes calculs, mais différemment) et je l'ai traduit pour utiliser pleinement les possibilités de la calculette :

Code: Select all

Define getpi(n)=
Func
Local m,p,q,d,st
[[4,12][1,4]]→m
1→p
3→q
""→st
While n>=0
  p+q→p
  q+2→q
  m*[[0,p][1,q]]→m
© Ici, j'ai dû rajouter ces simplifications pour dépasser 300 décimales
  If max(mat▶list(m))>10^100
    m/gcd(gcd(gcd(m[1,1],m[1,2]),m[2,1]),m[2,2])→m
© Fin des simplifications rajoutées
  intDiv(m[1],m[2])→d
  While d[1,1]=d[1,2] and n>=0
    st&string(d[1,1])→st
    n-1→n
    10mod(m[1],m[2])→m[1]
    intDiv(m[1],m[2])→d
  EndWhile
EndWhile
"3,"&mid(st,2)
EndFunc

Les simplifications rajoutées permettent d'atteindre 787 décimales exactes en un peu moins de 2 minutes... et ensuite, plus rien car on dépasse les capacités de la calculette comme expliqué plus haut.

[Excale]

J'ai fait une version qui atteint 1000 chiffres.*

Mais!
C'est de moi, donc c'est du troll. Qui a dit en base 10?

Code: Select all

Define getPi()=
Func
Local s,i
s:="3.14_"
For i,0,250
  s:=s&{"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001","1010","1011","1100","1101","1110","1111"}[iPart(16*fPart(∑(16^(i-k)*(((4)/(8*k+1))-((2)/(8*k+4))-((1)/(8*k+5))-((1)/(8*k+6))),k,0,i+11)))+1]
EndFor
EndFunc

(le "3.14_" c'est pour respecter la règle..., ça ne sert à rien)

Encore plus troll:

Code: Select all

Define getPi()=
Func
"3.14256789"
EndFunc

Oui, ça contient tous les chiffres de Pi, et en base 10.

*Je suis intéressé par un cross checking, je n'ai trouvé sur internet que les ~10 premières décimales.