Algorithme de Chudnovsky

L' algorithme de Chudnovsky est une méthode rapide de calcul des chiffres de π , basée sur les formules de π de Ramanujan . Publié par les frères Chudnovsky en 1988, il a été utilisé pour calculer π à un milliard de décimales.

Il a été utilisé dans les calculs du record du monde de 2,7 billions de chiffres de π en décembre 2009, 10 billions de chiffres en octobre 2011, 22,4 billions de chiffres en novembre 2016, 31,4 billions de chiffres en septembre 2018-janvier 2019, 50 billions de chiffres le 29 janvier 2020, 62,8 billions de chiffres le 14 août 2021, 100 billions de chiffres le 21 mars 2022, 105 billions de chiffres le 14 mars 2024, et 202 billions de chiffres le 28 juin 2024.

Algorithme

L'algorithme est basé sur le nombre de Heegner nié , la fonction j et sur la série hypergéométrique généralisée rapidement convergente suivante : Une preuve détaillée de cette formule peut être trouvée ici : ${\displaystyle d=-163 <semantics> <mrow> <mstyle> <mi>d</mi> <mo>=</mo> <mo>−</mo> <mn>163</mn> </mstyle> </mrow> <annotation>{\displaystyle d=-163}</annotation> </semantics> </math><img src=$ ${\displaystyle j\left({ frac {1+i{\sqrt {163}}}{2}} ight)=-640320^{3 <semantics> <mrow> <mstyle> <mi>j</mi> <mrow> <mo>(</mo> <mrow> <mstyle> <mfrac> <mrow> <mn>1</mn> <mo>+</mo> <mi>je</mi> <mrow> <msqrt> <mn>163</mn> </msqrt> </mrow> </mrow> <mn>2</mn> </mfrac> </mstyle> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mo>−</mo> <msup> <mn>640320</mn> <mrow> <mn>3</mn> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle j\gauche({ frac {1+i{\sqrt {163}}}{2}}\droite)=-640320^{3}}</annotation> </semantics> </math><img src=$ ${\displaystyle {\frac {1}{\pi }}=12\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k+3/2 <semantics> <mrow> <mstyle> <mrow> <mfrac> <mn>1</mn> <mi>π</mi> </mfrac> </mrow> <mo>=</mo> <mn>12</mn> <munderover> <mo>∑</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>∞</mi> </mrow> </munderover> <mrow> <mfrac> <mrow> <mo>(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo>)</mo> <mrow> <mi>k</mi> </mrow> </msup> <mo>(</mo> <mn>6</mn> <mi>k</mi> <mo>)</mo> <mo>!</mo> <mo>(</mo> <mn>545140134</mn> <mi>k</mi> <mo>+</mo> <mn>13591409</mn> <mo>)</mo> </mrow> <mrow> <mo>(</mo> <mn>3</mn> <mi>k</mi> <mo>)</mo> <mo>!</mo> <mo>(</mo> <mi>k</mi> <mo>!</mo> <msup> <mo>)</mo> <mrow> <mn>3</mn> </mrow> </msup> <mo>(</mo> <mn>640320</mn> <msup> <mo>)</mo> <mrow> <mn>3</mn> <mi>k</mi> <mo>+</mo> <mn>3</mn> <mrow> <mo>/</mo> </mrow> <mn>2</mn> </mrow> </msup> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\frac {1}{\pi }}=12\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k+3/2}}}}</annotation> </semantics> </math><img src=$

Cette identité est similaire à certaines formules de Ramanujan impliquant π , et est un exemple d'une série de Ramanujan–Sato .

La complexité temporelle de l'algorithme est de . ${\displaystyle O\left(n(\log n)^{3} ight) <semantics> <mrow> <mstyle> <mi>O</mi> <mrow> <mo>(</mo> <mrow> <mi>n</mi> <mo>(</mo> <mi>enregistrer</mi> <mo>⁡</mo> <mi>n</mi> <msup> <mo>)</mo> <mrow> <mn>3</mn> </mrow> </msup> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle O\gauche(n(\log n)^{3}\droite)}</annotation> </semantics> </math><img src=$

Optimisations

La technique d'optimisation utilisée pour les calculs du record du monde est appelée fractionnement binaire .

Division binaire

Un facteur de peut être retiré de la somme et simplifié en ${ extstyle 1/{640320^{3/2 <semantics> <mrow> <mstyle> <mn>1</mn> <mrow> <mo>/</mo> </mrow> <mrow> <msup> <mn>640320</mn> <mrow> <mn>3</mn> <mrow> <mo>/</mo> </mrow> <mn>2</mn> </mrow> </msup> </mrow> </mstyle> </mrow> <annotation>{ extstyle 1/{640320^{3/2}}}</annotation> </semantics> </math><img src=$ ${\displaystyle {\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k <semantics> <mrow> <mstyle> <mrow> <mfrac> <mn>1</mn> <mi>π</mi> </mfrac> </mrow> <mo>=</mo> <mrow> <mfrac> <mn>1</mn> <mrow> <mn>426880</mn> <mrow> <msqrt> <mn>10005</mn> </msqrt> </mrow> </mrow> </mfrac> </mrow> <munderover> <mo>∑</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>∞</mi> </mrow> </munderover> <mrow> <mfrac> <mrow> <mo>(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo>)</mo> <mrow> <mi>k</mi> </mrow> </msup> <mo>(</mo> <mn>6</mn> <mi>k</mi> <mo>)</mo> <mo>!</mo> <mo>(</mo> <mn>545140134</mn> <mi>k</mi> <mo>+</mo> <mn>13591409</mn> <mo>)</mo> </mrow> <mrow> <mo>(</mo> <mn>3</mn> <mi>k</mi> <mo>)</mo> <mo>!</mo> <mo>(</mo> <mi>k</mi> <mo>!</mo> <msup> <mo>)</mo> <mrow> <mn>3</mn> </mrow> </msup> <mo>(</mo> <mn>640320</mn> <msup> <mo>)</mo> <mrow> <mn>3</mn> <mi>k</mi> </mrow> </msup> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k}}}}</annotation> </semantics> </math><img src=$

Soit , et substituez-le dans la somme. ${\displaystyle f(n)={\frac {(-1)^{n}(6n)!}{(3n)!(n!)^{3}(640320)^{3n <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> <mo>=</mo> <mrow> <mfrac> <mrow> <mo>(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo>)</mo> <mrow> <mi>n</mi> </mrow> </msup> <mo>(</mo> <mn>6</mn> <mi>n</mi> <mo>)</mo> <mo>!</mo> </mrow> <mrow> <mo>(</mo> <mn>3</mn> <mi>n</mi> <mo>)</mo> <mo>!</mo> <mo>(</mo> <mi>n</mi> <mo>!</mo> <msup> <mo>)</mo> <mrow> <mn>3</mn> </mrow> </msup> <mo>(</mo> <mn>640320</mn> <msup> <mo>)</mo> <mrow> <mn>3</mn> <mi>n</mi> </mrow> </msup> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle f(n)={\frac {(-1)^{n}(6n)!}{(3n)!(n!)^{3}(640320)^{3n}}}}</annotation> </semantics> </math><img src=$ ${\displaystyle {\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}\sum _{k=0}^{\infty }{f(k)\cdot (545140134k+13591409) <semantics> <mrow> <mstyle> <mrow> <mfrac> <mn>1</mn> <mi>π</mi> </mfrac> </mrow> <mo>=</mo> <mrow> <mfrac> <mn>1</mn> <mrow> <mn>426880</mn> <mrow> <msqrt> <mn>10005</mn> </msqrt> </mrow> </mrow> </mfrac> </mrow> <munderover> <mo>∑</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow> <mi>∞</mi> </mrow> </munderover> <mrow> <mi>f</mi> <mo>(</mo> <mi>k</mi> <mo>)</mo> <mo>⋅</mo> <mo>(</mo> <mn>545140134</mn> <mi>k</mi> <mo>+</mo> <mn>13591409</mn> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}\sum _{k=0}^{\infty }{f(k)\cdot (545140134k+13591409)}}</annotation> </semantics> </math><img src=$

${\displaystyle {\frac {f(n)}{f(n-1) <semantics> <mrow> <mstyle> <mrow> <mfrac> <mrow> <mi>f</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> </mrow> <mrow> <mi>f</mi> <mo>(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\frac {f(n)}{f(n-1)}}}</annotation> </semantics> </math><img src=$ ${\displaystyle {\frac {-(6n-1)(2n-1)(6n-5)}{10939058860032000n^{3 <semantics> <mrow> <mstyle> <mrow> <mfrac> <mrow> <mo>−</mo> <mo>(</mo> <mn>6</mn> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mo>(</mo> <mn>2</mn> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mo>(</mo> <mn>6</mn> <mi>n</mi> <mo>−</mo> <mn>5</mn> <mo>)</mo> </mrow> <mrow> <mn>10939058860032000</mn> <msup> <mi>n</mi> <mrow> <mn>3</mn> </mrow> </msup> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\frac {-(6n-1)(2n-1)(6n-5)}{10939058860032000n^{3}}}}</annotation> </semantics> </math><img src=$ ${\displaystyle f(n)=f(n-1)\cdot {\frac {-(6n-1)(2n-1)(6n-5)}{10939058860032000n^{3 <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> <mo>=</mo> <mi>f</mi> <mo>(</mo> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mo>⋅</mo> <mrow> <mfrac> <mrow> <mo>−</mo> <mo>(</mo> <mn>6</mn> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mo>(</mo> <mn>2</mn> <mi>n</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mo>(</mo> <mn>6</mn> <mi>n</mi> <mo>−</mo> <mn>5</mn> <mo>)</mo> </mrow> <mrow> <mn>10939058860032000</mn> <msup> <mi>n</mi> <mrow> <mn>3</mn> </mrow> </msup> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle f(n)=f(n-1)\cdot {\frac {-(6n-1)(2n-1)(6n-5)}{10939058860032000n^{3}}}}</annotation> </semantics> </math><img src=$

${\displaystyle f(0)=1 <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <mn>0</mn> <mo>)</mo> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle f(0)=1}</annotation> </semantics> </math><img src=$ ${\displaystyle f <semantics> <mrow> <mstyle> <mi>f</mi> </mstyle> </mrow> <annotation>{\displaystyle f}</annotation> </semantics> </math><img src=$ ${\displaystyle f(n)=\prod _{j=1}^{n}{\frac {-(6j-1)(2j-1)(6j-5)}{10939058860032000j^{3 <semantics> <mrow> <mstyle> <mi>f</mi> <mo>(</mo> <mi>n</mi> <mo>)</mo> <mo>=</mo> <munderover> <mo>∏</mo> <mrow> <mi>j</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow> <mi>n</mi> </mrow> </munderover> <mrow> <mfrac> <mrow> <mo>−</mo> <mo>(</mo> <mn>6</mn> <mi>j</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mo>(</mo> <mn>2</mn> <mi>j</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mo>(</mo> <mn>6</mn> <mi>j</mi> <mo>−</mo> <mn>5</mn> <mo>)</mo> </mrow> <mrow> <mn>10939058860032000</mn> <msup> <mi>j</mi> <mrow> <mn>3</mn> </mrow> </msup> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle f(n)=\prod _{j=1}^{n}{\frac {-(6j-1)(2j-1)(6j-5)}{10939058860032000j^{3}}}}</annotation> </semantics> </math><img src=$

Cette définition de n'est pas définie pour , donc calculez le premier terme de la somme et utilisez la nouvelle définition de ${\displaystyle f <semantics> <mrow> <mstyle> <mi>f</mi> </mstyle> </mrow> <annotation>{\displaystyle f}</annotation> </semantics> </math><img src=$ ${\displaystyle n=0 <semantics> <mrow> <mstyle> <mi>n</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation>{\displaystyle n=0}</annotation> </semantics> </math><img src=$ ${\displaystyle f <semantics> <mrow> <mstyle> <mi>f</mi> </mstyle> </mrow> <annotation>{\displaystyle f}</annotation> </semantics> </math><img src=$ ${\displaystyle {\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}{\Bigg (}13591409+\sum _{k=1}^{\infty }{{\Bigg (}\prod _{j=1}^{k}{\frac {-(6j-1)(2j-1)(6j-5)}{10939058860032000j^{3}}}{\Bigg )}\cdot (545140134k+13591409)}{\Bigg ) <semantics> <mrow> <mstyle> <mrow> <mfrac> <mn>1</mn> <mi>π</mi> </mfrac> </mrow> <mo>=</mo> <mrow> <mfrac> <mn>1</mn> <mrow> <mn>426880</mn> <mrow> <msqrt> <mn>10005</mn> </msqrt> </mrow> </mrow> </mfrac> </mrow> <mrow> <mrow> <mo>(</mo> </mrow> </mrow> <mn>13591409</mn> <mo>+</mo> <munderover> <mo>∑</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow> <mi>∞</mi> </mrow> </munderover> <mrow> <mrow> <mrow> <mo>(</mo> </mrow> </mrow> <munderover> <mo>∏</mo> <mrow> <mi>j</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow> <mi>k</mi> </mrow> </munderover> <mrow> <mfrac> <mrow> <mo>−</mo> <mo>(</mo> <mn>6</mn> <mi>j</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mo>(</mo> <mn>2</mn> <mi>j</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mo>(</mo> <mn>6</mn> <mi>j</mi> <mo>−</mo> <mn>5</mn> <mo>)</mo> </mrow> <mrow> <mn>10939058860032000</mn> <msup> <mi>j</mi> <mrow> <mn>3</mn> </mrow> </msup> </mrow> </mfrac> </mrow> <mrow> <mrow> <mo>)</mo> </mrow> </mrow> <mo>⋅</mo> <mo>(</mo> <mn>545140134</mn> <mi>k</mi> <mo>+</mo> <mn>13591409</mn> <mo>)</mo> </mrow> <mrow> <mrow> <mo>)</mo> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}{\Bigg (}13591409+\sum _{k=1}^{\infty }{{\Bigg (}\prod _{j=1}^{k}{\frac {-(6j-1)(2j-1)(6j-5)}{10939058860032000j^{3}}}{\Bigg )}\cdot (545140134k+13591409)}{\Bigg )}}</annotation> </semantics> </math><img src=$

Soit et , donc ${\displaystyle P(a,b)=\prod _{j=a}^{b-1}{-(6j-1)(2j-1)(6j-5) <semantics> <mrow> <mstyle> <mi>P</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> <mo>=</mo> <munderover> <mo>∏</mo> <mrow> <mi>j</mi> <mo>=</mo> <mi>un</mi> </mrow> <mrow> <mi>b</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mrow> <mo>−</mo> <mo>(</mo> <mn>6</mn> <mi>j</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mo>(</mo> <mn>2</mn> <mi>j</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mo>(</mo> <mn>6</mn> <mi>j</mi> <mo>−</mo> <mn>5</mn> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle P(a,b)=\prod _{j=a}^{b-1}{-(6j-1)(2j-1)(6j-5)}}</annotation> </semantics> </math><img src=$ ${\displaystyle Q(a,b)=\prod _{j=a}^{b-1}{10939058860032000j^{3 <semantics> <mrow> <mstyle> <mi>Q</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> <mo>=</mo> <munderover> <mo>∏</mo> <mrow> <mi>j</mi> <mo>=</mo> <mi>un</mi> </mrow> <mrow> <mi>b</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mrow> <mn>10939058860032000</mn> <msup> <mi>j</mi> <mrow> <mn>3</mn> </mrow> </msup> </mrow> </mstyle> </mrow> <annotation>{\displaystyle Q(a,b)=\prod _{j=a}^{b-1}{10939058860032000j^{3}}}</annotation> </semantics> </math><img src=$ ${\displaystyle {\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}{\Bigg (}13591409+\sum _{k=1}^{\infty }{{\frac {P(1,k+1)}{Q(1,k+1)}}\cdot (545140134k+13591409)}{\Bigg ) <semantics> <mrow> <mstyle> <mrow> <mfrac> <mn>1</mn> <mi>π</mi> </mfrac> </mrow> <mo>=</mo> <mrow> <mfrac> <mn>1</mn> <mrow> <mn>426880</mn> <mrow> <msqrt> <mn>10005</mn> </msqrt> </mrow> </mrow> </mfrac> </mrow> <mrow> <mrow> <mo>(</mo> </mrow> </mrow> <mn>13591409</mn> <mo>+</mo> <munderover> <mo>∑</mo> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow> <mi>∞</mi> </mrow> </munderover> <mrow> <mrow> <mfrac> <mrow> <mi>P</mi> <mo>(</mo> <mn>1</mn> <mo>,</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo>)</mo> </mrow> <mrow> <mi>Q</mi> <mo>(</mo> <mn>1</mn> <mo>,</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo>)</mo> </mrow> </mfrac> </mrow> <mo>⋅</mo> <mo>(</mo> <mn>545140134</mn> <mi>k</mi> <mo>+</mo> <mn>13591409</mn> <mo>)</mo> </mrow> <mrow> <mrow> <mo>)</mo> </mrow> </mrow> </mstyle> </mrow> <annotation>{\displaystyle {\frac {1}{\pi }}={\frac {1}{426880{\sqrt {10005}}}}{\Bigg (}13591409+\sum _{k=1}^{\infty }{{\frac {P(1,k+1)}{Q(1,k+1)}}\cdot (545140134k+13591409)}{\Bigg )}}</annotation> </semantics> </math><img src=$

Laisser et ${\displaystyle S(a,b)=\sum _{k=a}^{b-1}{{\frac {P(a,k+1)}{Q(a,k+1)}}\cdot (545140134k+13591409) <semantics> <mrow> <mstyle> <mi>S</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> <mo>=</mo> <munderover> <mo>∑</mo> <mrow> <mi>k</mi> <mo>=</mo> <mi>un</mi> </mrow> <mrow> <mi>b</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mrow> <mrow> <mfrac> <mrow> <mi>P</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo>)</mo> </mrow> <mrow> <mi>Q</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo>)</mo> </mrow> </mfrac> </mrow> <mo>⋅</mo> <mo>(</mo> <mn>545140134</mn> <mi>k</mi> <mo>+</mo> <mn>13591409</mn> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation>{\displaystyle S(a,b)=\sum _{k=a}^{b-1}{{\frac {P(a,k+1)}{Q(a,k+1)}}\cdot (545140134k+13591409)}}</annotation> </semantics> </math><img src=$ ${\displaystyle R(a,b)=Q(a,b)\cdot S(a,b) <semantics> <mrow> <mstyle> <mi>R</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> <mo>=</mo> <mi>Q</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> <mo>⋅</mo> <mi>S</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle R(a,b)=Q(a,b)\cdot S(a,b)}</annotation> </semantics> </math><img src=$ ${\displaystyle \pi ={\frac {426880{\sqrt {10005}}}{13591409+S(1,\infty ) <semantics> <mrow> <mstyle> <mi>π</mi> <mo>=</mo> <mrow> <mfrac> <mrow> <mn>426880</mn> <mrow> <msqrt> <mn>10005</mn> </msqrt> </mrow> </mrow> <mrow> <mn>13591409</mn> <mo>+</mo> <mi>S</mi> <mo>(</mo> <mn>1</mn> <mo>,</mo> <mi>∞</mi> <mo>)</mo> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \pi ={\frac {426880{\sqrt {10005}}}{13591409+S(1,\infty)}}}</annotation> </semantics> </math><img src=$

${\displaystyle S(1,\infty ) <semantics> <mrow> <mstyle> <mi>S</mi> <mo>(</mo> <mn>1</mn> <mo>,</mo> <mi>∞</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle S(1,\infty )}</annotation> </semantics> </math><img src=$ ${\displaystyle S(1,n) <semantics> <mrow> <mstyle> <mi>S</mi> <mo>(</mo> <mn>1</mn> <mo>,</mo> <mi>n</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle S(1,n)}</annotation> </semantics> </math><img src=$ ${\displaystyle n <semantics> <mrow> <mstyle> <mi>n</mi> </mstyle> </mrow> <annotation>{\displaystyle n}</annotation> </semantics> </math><img src=$ ${\displaystyle \infty <semantics> <mrow> <mstyle> <mi>∞</mi> </mstyle> </mrow> <annotation>{\displaystyle \infty }</annotation> </semantics> </math><img src=$ ${\displaystyle \pi <semantics> <mrow> <mstyle> <mi>π</mi> </mstyle> </mrow> <annotation>{\displaystyle \pi }</annotation> </semantics> </math><img src=$ ${\displaystyle \pi =\lim _{n o \infty }{\frac {426880{\sqrt {10005}}}{13591409+S(1,n) <semantics> <mrow> <mstyle> <mi>π</mi> <mo>=</mo> <munder> <mo>Lim</mo> <mrow> <mi>n</mi> <mo>→</mo> <mi>∞</mi> </mrow> </munder> <mrow> <mfrac> <mrow> <mn>426880</mn> <mrow> <msqrt> <mn>10005</mn> </msqrt> </mrow> </mrow> <mrow> <mn>13591409</mn> <mo>+</mo> <mi>S</mi> <mo>(</mo> <mn>1</mn> <mo>,</mo> <mi>n</mi> <mo>)</mo> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \pi =\lim _{n o \infty }{\frac {426880{\sqrt {10005}}}{13591409+S(1,n)}}}</annotation> </semantics> </math><img src=$

D'après la définition originale de , ${\displaystyle R <semantics> <mrow> <mstyle> <mi>R</mi> </mstyle> </mrow> <annotation>{\displaystyle R}</annotation> </semantics> </math><img src=$ ${\displaystyle S(a,b)={\frac {R(a,b)}{Q(a,b) <semantics> <mrow> <mstyle> <mi>S</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> <mo>=</mo> <mrow> <mfrac> <mrow> <mi>R</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> </mrow> <mrow> <mi>Q</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle S(a,b)={\frac {R(a,b)}{Q(a,b)}}}</annotation> </semantics> </math><img src=$ ${\displaystyle \pi =\lim _{n o \infty }{\frac {426880{\sqrt {10005}}\cdot Q(1,n)}{13591409Q(1,n)+R(1,n) <semantics> <mrow> <mstyle> <mi>π</mi> <mo>=</mo> <munder> <mo>Lim</mo> <mrow> <mi>n</mi> <mo>→</mo> <mi>∞</mi> </mrow> </munder> <mrow> <mfrac> <mrow> <mn>426880</mn> <mrow> <msqrt> <mn>10005</mn> </msqrt> </mrow> <mo>⋅</mo> <mi>Q</mi> <mo>(</mo> <mn>1</mn> <mo>,</mo> <mi>n</mi> <mo>)</mo> </mrow> <mrow> <mn>13591409</mn> <mi>Q</mi> <mo>(</mo> <mn>1</mn> <mo>,</mo> <mi>n</mi> <mo>)</mo> <mo>+</mo> <mi>R</mi> <mo>(</mo> <mn>1</mn> <mo>,</mo> <mi>n</mi> <mo>)</mo> </mrow> </mfrac> </mrow> </mstyle> </mrow> <annotation>{\displaystyle \pi =\lim _{n o \infty }{\frac {426880{\sqrt {10005}}\cdot Q(1,n)}{13591409Q(1,n)+R(1,n)}}}</annotation> </semantics> </math><img src=$

Calculer les fonctions de manière récursive

Considérons une valeur telle que ${\displaystyle m <semantics> <mrow> <mstyle> <mi>m</mi> </mstyle> </mrow> <annotation>{\displaystyle m}</annotation> </semantics> </math><img src=$ ${\displaystyle a<m <mrow> <mstyle> <mi>un</mi> <mo><</mo> <mi>m</mi> <mo><</mo> <mi>b</mi> </mstyle> </mrow> <annotation>{\displaystyle a<m<b}</annotation> </semantics> </math><img src=$

${\displaystyle P(a,b)=P(a,m)\cdot P(m,b) <semantics> <mrow> <mstyle> <mi>P</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> <mo>=</mo> <mi>P</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>m</mi> <mo>)</mo> <mo>⋅</mo> <mi>P</mi> <mo>(</mo> <mi>m</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle P(a,b)=P(a,m)\cdot P(m,b)}</annotation> </semantics> </math><img src=$

${\displaystyle Q(a,b)=Q(a,m)\cdot Q(m,b) <semantics> <mrow> <mstyle> <mi>Q</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> <mo>=</mo> <mi>Q</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>m</mi> <mo>)</mo> <mo>⋅</mo> <mi>Q</mi> <mo>(</mo> <mi>m</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle Q(a,b)=Q(a,m)\cdot Q(m,b)}</annotation> </semantics> </math><img src=$
${\displaystyle S(a,b)=S(a,m)+{\frac {P(a,m)}{Q(a,m)}}S(m,b) <semantics> <mrow> <mstyle> <mi>S</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> <mo>=</mo> <mi>S</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>m</mi> <mo>)</mo> <mo>+</mo> <mrow> <mfrac> <mrow> <mi>P</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>m</mi> <mo>)</mo> </mrow> <mrow> <mi>Q</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>m</mi> <mo>)</mo> </mrow> </mfrac> </mrow> <mi>S</mi> <mo>(</mo> <mi>m</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle S(a,b)=S(a,m)+{\frac {P(a,m)}{Q(a,m)}}S(m,b)}</annotation> </semantics> </math><img src=$
${\displaystyle R(a,b)=Q(m,b)R(a,m)+P(a,m)R(m,b) <semantics> <mrow> <mstyle> <mi>R</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> <mo>=</mo> <mi>Q</mi> <mo>(</mo> <mi>m</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> <mi>R</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>m</mi> <mo>)</mo> <mo>+</mo> <mi>P</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>m</mi> <mo>)</mo> <mi>R</mi> <mo>(</mo> <mi>m</mi> <mo>,</mo> <mi>b</mi> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle R(a,b)=Q(m,b)R(a,m)+P(a,m)R(m,b)}</annotation> </semantics> </math><img src=$

Cas de base pour la récursivité

Considérer ${\displaystyle b=a+1 <semantics> <mrow> <mstyle> <mi>b</mi> <mo>=</mo> <mi>un</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation>{\displaystyle b=a+1}</annotation> </semantics> </math><img src=$

${\displaystyle P(a,a+1)=-(6a-1)(2a-1)(6a-5) <semantics> <mrow> <mstyle> <mi>P</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>un</mi> <mo>+</mo> <mn>1</mn> <mo>)</mo> <mo>=</mo> <mo>−</mo> <mo>(</mo> <mn>6</mn> <mi>un</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mo>(</mo> <mn>2</mn> <mi>un</mi> <mo>−</mo> <mn>1</mn> <mo>)</mo> <mo>(</mo> <mn>6</mn> <mi>un</mi> <mo>−</mo> <mn>5</mn> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle P(a,a+1)=-(6a-1)(2a-1)(6a-5)}</annotation> </semantics> </math><img src=$
${\displaystyle Q(a,a+1)=10939058860032000a^{3 <semantics> <mrow> <mstyle> <mi>Q</mi> <mo>(</mo> <mi>un</mi> <mo>,</mo> <mi>un</mi> <mo>+</mo> <mn>1</mn> <mo>)</mo> <mo>=</mo> <mn>10939058860032000</mn> <msup> <mi>un</mi> <mrow> <mn>3</mn> </mrow> </msup> </mstyle> </mrow> <annotation>{\displaystyle Q(a,a+1)=10939058860032000a^{3}}</annotation> </semantics> </math><img src=$
${\displaystyle S(a,a+1)={\frac {P(a,a+1)}{Q(a,a+1)}}\cdot (545140134a+13591409) <semantics> <mrow> <mstyle> <mi>S</mi> <mo>(</mo> <mi>a</mi> <mo>,</mo> <mi>a</mi> <mo>+</mo> <mn>1</mn> <mo>)</mo> <mo>=</mo> <mrow> <mfrac> <mrow> <mi>P</mi> <mo>(</mo> <mi>a</mi> <mo>,</mo> <mi>a</mi> <mo>+</mo> <mn>1</mn> <mo>)</mo> </mrow> <mrow> <mi>Q</mi> <mo>(</mo> <mi>a</mi> <mo>,</mo> <mi>a</mi> <mo>+</mo> <mn>1</mn> <mo>)</mo> </mrow> </mfrac> </mrow> <mo>⋅</mo> <mo>(</mo> <mn>545140134</mn> <mi>a</mi> <mo>+</mo> <mn>13591409</mn> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle S(a,a+1)={\frac {P(a,a+1)}{Q(a,a+1)}}\cdot (545140134a+13591409)}</annotation> </semantics> </math><img src=$
${\displaystyle R(a,a+1)=P(a,a+1)\cdot (545140134a+13591409) <semantics> <mrow> <mstyle> <mi>R</mi> <mo>(</mo> <mi>a</mi> <mo>,</mo> <mi>a</mi> <mo>+</mo> <mn>1</mn> <mo>)</mo> <mo>=</mo> <mi>P</mi> <mo>(</mo> <mi>a</mi> <mo>,</mo> <mi>a</mi> <mo>+</mo> <mn>1</mn> <mo>)</mo> <mo>⋅</mo> <mo>(</mo> <mn>545140134</mn> <mi>a</mi> <mo>+</mo> <mn>13591409</mn> <mo>)</mo> </mstyle> </mrow> <annotation>{\displaystyle R(a,a+1)=P(a,a+1)\cdot (545140134a+13591409)}</annotation> </semantics> </math><img src=$

Code Python

#Remarque : pour les calculs extrêmes, un autre code peut être utilisé pour s'exécuter sur un GPU, ce qui est beaucoup plus rapide que celui-ci.
importer 
décimal
définition de 
binary_split ( a , 
b ):
si 
b 
== 
a 
+ 
1 :
Pab 
= 
- ( 6 * une 
- 
5 ) * ( 2 * une 
- 
1 ) * ( 6 * une 
- 
1 )
Qab 
= 
10939058860032000 
* 
a ** 3
Rab 
= 
Pab 
* 
( 545140134 * a 
+ 
13591409 )
autre :
m 
= 
( a 
+ 
b ) 
// 
2
Pam , 
Qam , 
Ram 
= 
fractionnement_binaire ( a , 
m )
Pmb , 
Qmb , 
Rmb 
= 
fractionnement_binaire ( m , 
b )
Pab 
= 
Pam 
* 
Pmb
Qab 
= 
Qam 
* 
Qmb
Rab 
= 
Qmb 
* 
Ram 
+ 
Pam 
* 
Rmb
retour 
Pab , 
Qab , 
Rab
déf 
chudnovsky ( n ):
« Algorithme de Chudnovsky »
P1n , 
Q1n , 
R1n 
= 
fractionnement_binaire ( 1 , 
n )
retour 
( 426880 
* 
décimal . Décimal ( 10005 ) . sqrt ( ) 
* 
Q1n ) 
/ 
( 13591409 * Q1n 
+ 
R1n )
imprimer ( f "1 = { chudnovsky ( 2 ) } " ) 
# 3.141592653589793238462643384
decimal . getcontext () . prec 
= 
100 
# nombre de chiffres de précision décimale
pour 
n 
dans 
la plage ( 2 , 10 ) :
print ( f " { n } = { chudnovsky ( n ) } " ) 
# 3.14159265358979323846264338...

Remarques

{\displaystyle e^{\pi {\sqrt {163}}}\approx 640320^{3}+743.99999999999925\dots <semantics> <mrow> <mstyle> <msup> <mi>e</mi> <mrow> <mi>π</mi> <mrow> <msqrt> <mn>163</mn> </msqrt> </mrow> </mrow> </msup> <mo>≈</mo> <msup> <mn>640320</mn> <mrow> <mn>3</mn> </mrow> </msup> <mo>+</mo> <mn>743.99999999999925</mn> <mo>…</mo> </mstyle> </mrow> <annotation>{\displaystyle e^{\pi {\sqrt {163}}}\approx 640320^{3}+743.99999999999925\dots }</annotation> </semantics> </math></span><img src=

{\displaystyle 640320^{3}/24=10939058860032000 <semantics> <mrow> <mstyle> <msup> <mn>640320</mn> <mrow> <mn>3</mn> </mrow> </msup> <mrow> <mo>/</mo> </mrow> <mn>24</mn> <mo>=</mo> <mn>10939058860032000</mn> </mstyle> </mrow> <annotation>{\displaystyle 640320^{3}/24=10939058860032000}</annotation> </semantics> </math></span><img src=

{\displaystyle 545140134=163\cdot 127\cdot 19\cdot 11\cdot 7\cdot 3^{2}\cdot 2 <semantics> <mrow> <mstyle> <mn>545140134</mn> <mo>=</mo> <mn>163</mn> <mo>⋅</mo> <mn>127</mn> <mo>⋅</mo> <mn>19</mn> <mo>⋅</mo> <mn>11</mn> <mo>⋅</mo> <mn>7</mn> <mo>⋅</mo> <msup> <mn>3</mn> <mrow> <mn>2</mn> </mrow> </msup> <mo>⋅</mo> <mn>2</mn> </mstyle> </mrow> <annotation>{\displaystyle 545140134=163\cdot 127\cdot 19\cdot 11\cdot 7\cdot 3^{2}\cdot 2}</annotation> </semantics> </math></span><img src=

{\displaystyle 13591409=13\cdot 1045493 <semantics> <mrow> <mstyle> <mn>13591409</mn> <mo>=</mo> <mn>13</mn> <mo>⋅</mo> <mn>1045493</mn> </mstyle> </mrow> <annotation>{\displaystyle 13591409=13\cdot 1045493}</annotation> </semantics> </math></span><img src=