Aller au contenu
Kilterra

Calculons 1000 décimales de pi !

Messages recommandés

Salut à tous,
Pendant la période de confinement, j'ai décidé de relever certains défis de programmation et j'ai commencé par calculer pi avec skript (enfin les 1000 premières décimales). Je vais donc vous expliquer la méthode que j'ai utilisé.

Cependant, avant cela nous allons reprendre quelques bases.

 

I. La division en base B

Tout d'abord, avant de comprendre l'algorithme pour calculer pi il faut réussir à diviser un nombre sur une base donnée, voir la partie sur le calcul de pi pour en découvrir la raison. Le principe est très simple.

 

A. Premier rappel : Une base B.

Pour ceux qui ne connaissent pas le principe de l'écriture en base B, voici la définition de wikipédia.

Citation

En arithmétique, une base désigne la valeur dont les puissances successives interviennent dans l'écriture des nombres dans la numération positionnelle N-adique, ces puissances définissant l'ordre de grandeur de chacune des positions occupées par les chiffres composant tout nombre.

Concrètement l'écriture d'un nombre A dans une base B reviens à l'écriture comme :
A = x.Bn+ y.Bn-1 + z.Bn-2 + ...

Révélation

Dans la vie de tout les jours, on utilise la base 10. Donc les nombres vont de 0 à 10. Donc en reprenant la définition (fausse je vous le rappelle), un nombre N dans la base 10 s'écrit comme :
N = x.10n + y.10n-1 + z.10n-2


B. Expression littérale de la division

On veut diviser l'entier A par l'entier D dans la base B.
On a :
A = x.Bn+ y.Bn-1 + z.Bn-2 + ...


On effectue d'abord la division de x (première "tranche") par D :
x = Dqn + rn    : qn est le quotient et rn le reste de la division euclidienne de x par D.

D'où :

A = (Dqn + rn)Bn + yBn-1 + ...
 
En développant on a :
A = Dqn.Bn + (Brn + y)Bn-1 + ...

Le quotient commence donc par qn et on a regroupé rnBn + yBn-1 en (Brn + y)Bn-1 que l'on divise ("on abaisse la tranche suivante") de la même façon. Et ainsi de suite.
Le quotient s'écrira alors :

qnBn + qn-1Bn-1 + ...


C. L'algorithme de la division
 

Ici on veut diviser un nombre de 100 chiffres par un diviseur N. On procède par tranche de 4 chiffres, et comme 100/4 = 25, on a besoin de 25 chiffres et même 26 si on veut être sûr de la 100ème décimale.

T est une liste. T(i) correspond à i-ème valeur de la liste T.
T(0) contiendra la partie entière Q du quotient.
Le premier reste est R = T(0) - N*Q.
Nous le décalons dans la tranche suivante T(1) en le multipliant par B et nous procédons à sa division par N. Ainsi de suite jusqu'à la dernière tranche.

Contenu masqué

    Réagissez ou répondez à ce message afin de consulter le contenu masqué.

 

II. La multiplication en base B

Après, avoir étudié la division en base B, il va maintenant falloir étudier la multiplication en base B, alors commençons :

 

A. L'expression litérale de la multiplication en base B

Le multiplicande Z possède 100 décimales, le multiplicateur est un entier m. Si B est la base utilisée, Z est de la forme :

ToBn+ T1Bn-1+ ... + Tn-2B2 + Tn-1B + Tn

Les Ti , i variant de 0 au nombre de tranches, sont les chiffres de notre système à base B. On effectue la multiplication par m de "droite" à "gauche" :

Tn devient Tn.Z que l'on écrit sous la forme B.q + r en effectuant une division euclidienne. Par suite, le dernier "chiffre" est maintenant Tn = r;

on repousse alors B.q dans B.Tn-1 qui devient B(Tn-1 + q);

Tn-1 + q est multiplié par m que l'on écrit sous la forme Bq' + r';

B(Tn-1 + q) devient alors B(Bq' + r') = B2q' + Br'. Par suite l'avant dernier "chiffre" Tn-1 est maintenant r'

Et ainsi de suite...

Le cas de la multiplication de To est particulier : il doit être multiplié par m et hériter du dernier quotient q. Un problème se poserait si un risque de dépassement pouvait exister : To ne doit pas dépasser B inclus.
 

B. L'algorithme de la multiplication en base B

Ici on veut diviser un nombre de 100 chiffres par un multiplicateur m. On procède par tranche de 4 chiffres, et comme 100/4 = 25, on a besoin de 25 chiffres et même 26 si on veut être sûr de la 100ème décimale.

Contenu masqué

    Réagissez ou répondez à ce message afin de consulter le contenu masqué.

 

III. Calcul de pi

A. L'explication théorique

Pour calculer pi, nous allons utiliser les séries. Il en existe un très grand nombre utilisé pour calculer pi.

Beaucoup sont basé sur le développement de Arc Tangente, qui est :

Atan(x) = x - x3/3 + x5/5 - x7/7 + ... + (-1)n x2n+1/(2n+1) + ...
 
Or comme Atan(1) = pi/4, on a :
pi/4 = 1 - 1/3 + 1/5 - 1/7 + ... + (-1)n/(2n+1)
Cependant, cette série converge très lentement vers pi/4, et le risque d'erreur augmente donc d'autant plus.
Cependant, il existe une formule stable basé sur celle là qui utilise la convergence d'Euler (je n'expliquerai pas ici).
pi_1009.gif
 
Donc concrètement, si l'on prend une suite Un définie par récurrence par :
U0 = 2 et Un = Un-1.n/(2n+1)
Cette suite tend vers pi.

 
B. L'algorithme en lui même
 
Voici un algorithme qui permet de calculer avec exactitude les 100 premières décimales de pi et en comprenant le principe, on peut même calculer les 1000 premières décimales et ainsi de suite.
 

Contenu masqué

    Réagissez ou répondez à ce message afin de consulter le contenu masqué.

Et c'est bien pour cela que je vous ai appris à faire une division et une multiplication à plusieurs décimales, sinon, l'ordinateur aurait arrondu, et on aurai eu des risques d'erreur important.

 

IV. Et l'implémentation dans tout ça ?

Nous allons maintenant passer à l'implémentation des différents algorithmes et vous allez donc voir comment calculer pi avec 1000 décimales.
Mais avant cela, il faut encore que nous fassions quelques calculs :
Si l'on veut 1000 décimales rapidement, on va choisir une base B = 100 000, donc il va nous falloir :
1000 / 5 = 200 tranches pour obtenir les 999 décimales exactes et on en prend 201 pour avoir la 1000ème exacte au moins.

Dans les algorithmes suivants on a :
- {list::*} variable liste globale, ça nous évite de devoir retourner à chaque fonction une liste.

- {list::i} contient la i-ème tranche, et {list::1} contient la partie entière.

- {m} est le multiplicateur et {b} la base utilisé

 

J'aurai pu utilisé des variables locales mais cela aurait été moins compréhensible par tous et ce n'est pas le but.

 

A. L'algorithme de la multiplication

En se basant sur l'algorithme donné plus haut, l'implémentation est toute simple :
 

Contenu masqué

    Réagissez ou répondez à ce message afin de consulter le contenu masqué.

 

B. L'algorithme de la division

Contenu masqué

    Réagissez ou répondez à ce message afin de consulter le contenu masqué.

 

C. L'algorithme principal

Contenu masqué

    Réagissez ou répondez à ce message afin de consulter le contenu masqué.

 

Et maintenant, il ne nous reste plus qu'à appeller tout ça dans une commande par exemple :
 

Contenu masqué

    Réagissez ou répondez à ce message afin de consulter le contenu masqué.

 

Et c'est la fin de ce tutoriel. Vous avez bien appris à calculer les 1000 premières décimales de pi. Désolé si je n'ai pas été clair sur certains points, cependant, n'hésitez pas à faire vous mêmes des recherches sur internet ou à me demander si vous voulez que je réexplique certains passages.

Sur ce, je vous souhaite une bonne journée, n'oubliez pas de participez à l'évènement discord actuel, qui consiste en un concours de skript.

Ciao !

  • J'aime 1
  • Merci 2

Partager ce message


Lien à poster
Partager sur d’autres sites

Rejoindre la conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Invité
Répondre à ce sujet…

×   Collé en tant que texte enrichi.   Coller en tant que texte brut à la place

  Seulement 75 émoticônes maximum sont autorisées.

×   Votre lien a été automatiquement intégré.   Afficher plutôt comme un lien

×   Votre contenu précédent a été rétabli.   Vider l’éditeur

×   Vous ne pouvez pas directement coller des images. Envoyez-les depuis votre ordinateur ou insérez-les depuis une URL.


×
×
  • Créer...

Information importante

Nous avons placé des cookies sur votre appareil pour aider à améliorer ce site. Vous pouvez choisir d’ajuster vos paramètres de cookie, sinon nous supposerons que vous êtes d’accord pour continuer.