Algorithme "géométrique" pour le calcul de pi

[sebsheep]

Bonjour,

Je cherchais un algo basé sur de la géométrie simple (je sais très bien qu'il existe une foultitude de méthodes basées sur fourrier ou autres techniques encore plus compliquées ...) pour calculer pi. Que pensez vous de mon idée ? Peut-on faire plus simple en conservant la même idée ?

L'idée est de calculer une approximation de la circonférence cercle. Grâce à ça, on aura 2piR, il suffira de diviser ce nombre par 2R pour avoir pi.

Je considère un cercle de rayon 1.Je pars du point D (0,1) (cf pj). Ensuite, je "monte vers le haut" en suivant un petit vecteur . Je normalise ensuite le en . Ainsi OD =1, D est sur le cercle. J'approxime la longueur de l'arc DD' par la longueur du segment DD'.

Puis je recommence : je pars de D'. Pour savoir quel vecteur suivre, je prend que je normalise de façon à avoir . Cela me donne donc le vecteur . Je normalise en , et encore une fois approxime l'arc D'D'' avec le segment D'D'' ...

ainsi de suite jusqu'à ce que l'abscisse de D'''' soit inférieure à d (en valeur absolue, bien sur). On aura ainsi calculé le quart du périmètre du cercle en sommant DD' + D'D'' + ... . Il suffira de multiplier par 2R = 2 pour avoir pi (ici R=1).

Voilà un code qui applique cet algo en python (à la reflexion, j'aurais mieux fait de faire ça en scilab-like, pour les vecteurs c'eut été plus facile) :

from math import *

def norm(v) :
	return sqrt( v[0]**2 + v[1]**2 )
	
def normalize(v):
	n = norm(v)
	return ( v[0]/n , v[1]/n)
	
def plus(v1,v2) :
	return (v1[0]+v2[0],v1[1]+v2[1])

def moins(v1,v2) :
	return (v1[0]-v2[0],v1[1]-v2[1])
	
def fois(a,v):
	return (a*v[0],a*v[1])
	
DA = (1.,0.)
OD  = (0.,1.)
d  = 0.0001
circ = 0.

while abs(OD[1]) > d :
	# calcul du nouveau vecteur OD (le calcul de OA est fait par le `plus(.,.)`
	new_OD = normalize( plus( OD , fois( d , DA ) ) )
	# calcul du nouveau vecteur DD'
	DDp  = moins(new_OD,OD)
	#Ajout a la circonference
	circ    += norm(DDp)
	
	#Preparation au passage a la prochaine etape
	DA=normalize(DDp)
	OD=new_OD
	
print 2*circ

-----

[sebsheep]

Aucun comm?

Est ce que vous pourriez au moins me dire si vous comprenez la méthode ?

[mx6]

Et si tu postes dans Mathématiques du Supérieur ? car la niveau collège et lycée, rare les gens pouvant t'aider!

[VegeTal]

en C++ je veux bien t'aider

[A voir en vidéo sur Futura]

[sebsheep]

merci, mais c'est pas une question de langages ... (au passage, va faire ce code en C++ ... c'est 4 fois plus long ) (mais c'est 100 fois plus rapide, ok ...)(le bon compromis serait le caml ... mais le sujet n'est pas là)

Pour revenir à l 'algo, j'ai trouvé quelque chose de beaucoup plus simple (desfois j'ai l'impression d'avoir des coups de génie alors que je fais des trucs qui servent à rien ...) :

L'idée est toujours de calculer la circonférence du cercle ; le principe : on par toujours de (0,1). puis on va augmenter y de d, et trouver x. c'est possible car on sait que x²+y²=1 (on est sur un cercle). Du coup (x>0, y>0) : .
Le nouveau point est alors : . On calcule la distance avec (0,1), et puis on recommence en repartant de et en calculant la distance avec le point et ainsi de suite jusqu'a arriver au point (1,0).

[invitea250c65c]

Salut !

Super intéressant comme sujet je trouve, c'est vrai qu'il existe des tonnes de grosses formules pour ça mais c'est sympa d'éssayer de faire simple et de se mettre à la place des anciens qui n'avaient pas Fourrier et compagnie à disposition (bon ok sympa jusqu'à l'étape calculs mais nous on a les ordis en plus ).

Si j'ai bien compris tes deux méthodes reviennent en gros au même, sauf qu'avec la première tu vas obtenir un algo, avec la deuxième tu vas obtenir une limite.
J'avais fait il y a quelques temps un truc qui ressemblait à ta deuxième méthode.
J'ai ainsi montré que , ca semblait bien converger vers mais c'était super lent (je crois qu'on arrivait à 6-7 décimales pour n=1 million).

Il y a peut-être moyen d'accélérer ça, mais il faudra changer de méthode à mon avis. Avis aux autres.

Autre possibilité : avec des aires. Ca revient à faire des sommes de Rieman sous un demi cercle, parce que si tu veux traiter une intégrale tu te retrouves avec un arcsinus donc tomber sur un truc du genre au final ça ne nous avance pas beaucoup, à moins de savoir calculer des arcsinus mais dans ce cas là le problème est règlé.
Si je me souviens bien on tombe sur quelque chose de plus simple et qui converge un peu plus vite. Je n'ai pas noté la formule mais ça se retrouve facilement (et puis j'ai eu ma dose de latex pour aujourd'hui ).

Sinon tu as la méthode d'Archimède (reprise et améliorée par un français aux alentours du XVème sciècle je crois) qui consiste à "entourrer" un cercle par des polygones intérieurs et extérieurs à n côtés et à faire tendre n vers l'infini. Il est ainsi possible d'obtenir deux suites récurrentes adjacentes qui convergent vers (dans les expressions de récurrence n'interviennent que les 4 opérations usuelles et des racines carrées si je me souviens bien). Ca c'est vraiment bien parce que d'une part la convergence est bien plus rapide qu'avec mes deux méthodes précédentes et d'autre part parce que tu obtiens un encadrement de à chaque itération.

Si quelqu'un a d'autres idées qui restent dans cette optique géométrique (pas fait exprès ) je suis également intéressé.

J'espère avoir pu t'aider.

A+

[sebsheep]

Mes 2 méthodes reviennent un peu au même, c'est vrai, même carrément. Les 2 sont des algos qui calculent une limite,pas l'un plus que l'autre. Tu pourrais aussi mettre mon premier algo sous une grosse somme, ca reviendrai à peu pres au même. Au passage, ma méthode "plus simple" ne converge pas ... c'est un mystère ... vais creuser un peu

calculer arcsin se fait très bien avec les développements limités :
(source: wiki)

Ce DL n'est pas très facile à calculer, celui de artan (pareil on a arctan(1)=Pi/2) est plus simple ... mais bon la on sort un peu du progm du lycée avec les DL...
(et au passage, pas besoin de calculer une intégrale pour savoir que arcsin(1)=pi )
Le coup de l'intégrale est pas mal aussi, je me demande pourquoi j'y avais pas pensé plus tot.

Après comme façon "marrante" on peut le faire avec du Monte Carlo : on tire alétoirement un couple de nombre (x,y) dans un carré [1,1]x[1,1]. Si la norme de (x,y) < 1, le coup est dans le cercle, on incrémente un compteur de 1. Sinon, on ne fait rien et on retire. A la fin on fait le rapport "coup dans le cercle/coup total", ca nous donne le rapport "aire cercle/aire carré" = pi*4. On a donc juste à diviser ce rapport par 4 pour avoir pi. Ca converge super lentement (et pas de manière déterministe), mais c'est vraiment pas dur à coder et à concevoir.

Je vais essayer de trouver les polygones d'Archimede. Tu dis les 2 suites récurentes, c'est des récurences croisées? (ca m'étonnerai mais bon) Ne me donne pas la solution, je veux trouver tout seul

[invitea250c65c]

ma méthode "plus simple" ne converge pas ... c'est un mystère ... vais creuser un peu

Curieux. J'essayerai ce week end si j'ai le temps.

calculer arcsin se fait très bien avec les développements limités [...] mais bon la on sort un peu du progm du lycée avec les DL...

Oui on s'éloigne de "l'algo géométrique" .

et au passage, pas besoin de calculer une intégrale pour savoir que 2arcsin(1)=pi

Oui c'est pour ça que le calcul de l'intégral n'est pas d'un grand intérêt il ne nous apprend rien de nouveau.

Après comme façon "marrante" on peut le faire avec du Monte Carlo : ...

J'avais lu quelque chose la dessus il y a quelques temps (moi c'était avec des grains de riz!), mais la pour le coup on s'éloigne un peu des maths (dans le sens "science exacte").

Je vais essayer de trouver les polygones d'Archimede. Tu dis les 2 suites récurentes, c'est des récurences croisées? (ca m'étonnerai mais bon)

Oui c'est ça, deux suites récurrentes croisées.

Bonne recherche (c'était un exo de TS ou 1ereS mais avec pas mal de questions intermédiaires donc ça ne doit pas être immédiat je pense).

Si je remets la main dessus je te fais signe (en spoiler bien sur ).

[bubulle_01]

Un truc que j'avais fait en première :
Le périmètre du demi cercle trigonométrique est
Si tu décomposes le demi-cercle en deux segments de même longeur, comme suit :

Dans un premier temps, tu as l'approximation (très mauvaise) :


Ensuite, en redécomposant en 2, tu as :


En réitérant cela n fois, on remarque que l'approximation est :
avec le nombre de racines carrées emboitées.

Et donc

Ceci n'est autre qu'une écriture différente de la formule de Viète découverte en 1593, donnée par :

[sebsheep]

Citation:
Après comme façon "marrante" on peut le faire avec du Monte Carlo : ...
J'avais lu quelque chose la dessus il y a quelques temps (moi c'était avec des grains de riz!), mais la pour le coup on s'éloigne un peu des maths (dans le sens "science exacte").

On est autant dans les maths qu'avec le calcul avec des DL ou polygones ou quoique ce soit!
Tous les algos qu'ont utilise converge plus ou moins bien,
Mmonte Carlo converge très mal, mais à l'infini il converge, c'est indéniable mathématiquement!

C'est quand même une méthode super utilisée en physique nucléaire, si elle était pas prouvée mathématiquement, ca serait grave