Rechercher : dans
Par :

Euh... "O(x²)?"?

Dernière réponse le 17 oct 2008 à 23:13:06 Yuku, le 17 oct 2008 à 21:14:21 
 Signaler ce message aux modérateurs

Bonjour à tous,

Je suis en train de créer un programme qui calcule la puissance, l'exponentielle, le cosinus et le sinus de deux nombres x et n, à partir de quelques formules.

La formule de l'exponentielle est la suivante :

exp(x) = 1 + (x/1!) + (x^2/2!) + (x^3/3!) + ... + (x^n/n!) + O(x^n)

Tout va bien pour la majorité du calcul, j'ai bien déclaré x et n, et un compteur, etc etc...

Mais qu'est ce que c'est que ce O(x^n)??

Voilà, tout d'abord qu'est-ce-que c'est, et surtout comment le déclarer dans mon programme ?!

Merci d'avance ! :)

Configuration: Windows Vista
Firefox 3.0.3

Meilleures réponses pour « Euh... "O(x²)?"? » dans :
Serveur X sous Windows VoirIl est possible d'installer un serveur X sous Windows afin d'utiliser les applications X-Windows (Gnome, KDE, etc.) sous Windows (par exemple à travers une connexion ssh). La méthode suivante n'utilise pas Cygwin. Dans l'exemple ci-dessous,...
[X-Window] Démarrer plusieurs serveurs X VoirDémarrer 2 serveur X Principe Mise en oeuvre Note : Switcher d'une console à l'autre Principe Lancer 2 serveurs X en parallèle, comme par exemple travailler en mode graphique sous "root" (vivement déconseillé) sans clore sa session...
Télécharger NTFS for Mac OS X VoirAccès total en lecture et en écriture vers des volumes NTFS NTFS for Mac® OS X fournit un accès total (lecture ou écriture, formatage) vers des partitions NTFS. Compatible avec toutes les versions de NTFS Toutes les versions NTFS sont prises en...
Télécharger O&O Defrag 12 VoirLe point fort de O&O Defrag, c'est sa rapidité, il est clairement beaucoup plus rapide que l'outil Windows, et que de ses autres concurrents. Par ailleurs, un planificateur de tâche intégré permet de lancer une défragmentation automatique à...

1

toto, le 17 oct 2008 à 21:34:25
  • +2

Bonsoir

Sans entrer dans les détails, ça veut simplement dire un terme négligeable. Donc tu n'as pas à t'en soucier.
Mais pour appliquer ce genre de formule, il faut être capable de calculer le 'n' c'est à dire le nombre de termes à utiliser pour atteindre la précision voulue dans la réponse.

Répondre à toto

2

Yuku, le 17 oct 2008 à 21:37:24

Mais justement, j'incrémente un Compteur qui remplace n et se répète le nombre de fois nécessaires pour faire ce calcul...
Cela signifie donc que je n'ai pas à me soucier de ce O(x^n)??

Répondre à Yuku

3

Sacabouffe, le 17 oct 2008 à 21:54:48
  • +3

Salut
Ben...
O(x^n), c'est une fonction, cette notation, c'est une des notations de Landau :
http://fr.wikipedia.org/wiki/Notations_de_Landau

En fait, on note O(x^n) (ici on devrait préciser pour x→+∞), toute fonction f telle que f(x)/x^n est bornée (ici en l'occurrence quand x→+∞).

On note o(x^n) (dans le cas qui nous intéresse, pour x→+∞), toute fonction f telle que lim (f(x)/x^n) = 0 (et donc ici, quand x→+∞).

Ta formule est pas fausse mais on peut la raffiner un peu.
exp(x) = 1 + (x/1!) + (x^2/2!) + (x^3/3!) + ... + (x^n/n!) + O(x^(n+1))
Ou
exp(x) = 1 + (x/1!) + (x^2/2!) + (x^3/3!) + ... + (x^n/n!) + o(x^n)

Bref, ici donc, ton O(x^(n+1)) ou ton o(x^n), c'est
(x^(n+1)/(n+1)!) + (x^(n+2)/(n+2)!) + (x^(n+3)/(n+3)!) + ... (jusqu'à +∞)

Parce qu'en fait, la formule que t'as écrite, c'est juste une écriture moins précise de
exp(x) = 1 + (x/1!) + (x^2/2!) + (x^3/3!) + ... + (x^n/n!) + ... (jusqu'à +∞)

Du coup pour ton programme tu t'en occupes pas trop. Tu choisis un n assez grand et tu calcules ta somme jusqu'à n.
Tu peux améliorer le programme en choisissant le n en fonction de x. En effet, un n qui va te donner des résultats très précis pour un x pas trop grand, va donner des résultats beaucoup moins satisfaisants pour un x plus grand. Du coup, tu peux sommer jusqu'à ce que le premier terme du reste ((x^(n+1)/(n+1)!)) soit inférieur à un petit nombre donné.

Par contre, si tu vas jusqu'à des n relativement grands, pense à utiliser une exponentiation rapide.
http://fr.wikipedia.org/wiki/Exponentiation_rapide
Sinon ça va ramer...

Et dernière chose, je pense que si t'essaies de calculer l'exponentielle d'un grand nombre de cette manière (Quel sera exactement "grand" ? Ben je sais pas trop...), tu vas rapidement avoir des soucis. En effet, x^n→+∞) (tout au moins pour x > 1) et n!→+∞.
En théorie (x^n/n!)→+0 mais numériquement, tu vas avoir à évaluer le quotient de deux grands nombres et t'auras des erreurs numériques monstrueuses. Et en plus, passé n=170, le résultat du calcul de n! sera tout simplement +∞.

Voilà... Amuse-toi bien ! ;-) Thought I heard a rumbling, calling to my name
Two hundred million guns are loaded, Satan cries "Take aim!"

Répondre à Sacabouffe

4

Yuku, le 17 oct 2008 à 22:02:33

Alors merci beaucoup, c'est nettement plus clair !

Si je veux donc stocker des très grandes variables, qu'est-ce-que je devrais utiliser?

J'utilise actuellement des double...

Répondre à Yuku

5

Sacabouffe, le 17 oct 2008 à 22:05:31
  • +2

Ben de rien ;-)

Si tu veux faire un calcul précis, le mieux c'est effectivement des doubles. De toute façon, t'as pas à en stocker une quantité industrielle, juste 3 ou 4, pas de quoi fouetter un chat, tu risques pas d'avoir des soucis d'espace mémoire avec ça :-D Thought I heard a rumbling, calling to my name
Two hundred million guns are loaded, Satan cries "Take aim!"

Répondre à Sacabouffe

6

Yuku, le 17 oct 2008 à 22:07:18

Ça marche ! Juste une petite question encore, c'est quoi la différence entre un double et un long double ?

Répondre à Yuku

7

Sacabouffe, le 17 oct 2008 à 22:11:22
  • +2

C'est là :
http://www.commentcamarche.net/contents/c/ctype.php3
Un double a une taille de 8 octets et un long double a une taille de 10 octets.
Tu peux essayer avec un long double aussi pour ton code si tu veux. Thought I heard a rumbling, calling to my name
Two hundred million guns are loaded, Satan cries "Take aim!"

Répondre à Sacabouffe

8

Yuku, le 17 oct 2008 à 22:15:15

Par contre là je vais avoir besoin d'un petit coup de pouce ><

Pour l'exponentiel c'était assez facile, la formule était :

exp(x) = 1 + (x/1!) + (x^2/2!) + (x^3/3!) + ... + (x^n)/n!

Mais pour le sinus c'est :

x - x3/3! + x5/5! - x7/7! + ... + (-1)^n ((x^2n+1/(2n+1)!)


Comment faire pour passer de +3 à -5 puis +7...??

Je sais comment faire pour incrémenter 1 à chaque fois, mais là... :S

Répondre à Yuku

9

Sacabouffe, le 17 oct 2008 à 22:18:00
  • +2

Tu fais une boucle où t'incrémentes n de 1, mais dans pour la formule t'utilises 2n+1, et voili voilou...8-) Thought I heard a rumbling, calling to my name
Two hundred million guns are loaded, Satan cries "Take aim!"

Répondre à Sacabouffe

10

Yuku, le 17 oct 2008 à 22:19:04

Euh... Perso j'ai pas trop compris là =S

Répondre à Yuku

11

fiddy, le 17 oct 2008 à 22:26:26
  • +1

-5 7 -9, ça sonne comme un incrément de deux avec changement de signes.
Donc si c'est négatif tu multiplies par -1 et t'ajoutes 2. Sinon tu multiplies par -1 et tu soustrais 2 ;)

coeff=coeff>0?-coeff-2:-coeff+2;

Cdlt
Google is your friend

Répondre à fiddy

12

Yuku, le 17 oct 2008 à 22:28:05

J'ai jamais fait ça, selon les changements de signes donc bon ^^ pas évident...

Répondre à Yuku

13

Sacabouffe, le 17 oct 2008 à 22:32:38
  • +2

Si tu veux t'arrêter à 43 par exemple (43=2*21+1)

sinx= 0;
for (n=0; n<=21; n++) {
        fact=factorielle(2*n+1);
	sinx = sinx + ((-1)^n)*(x^(2*n+1))/fact;

}
factorielle sera ta fonction pour calculer ta factorielle bien évidemment... (^_^) Thought I heard a rumbling, calling to my name
Two hundred million guns are loaded, Satan cries "Take aim!"

Répondre à Sacabouffe

14

Yuku, le 17 oct 2008 à 22:49:26

Ah ouais je vois, ok !

J'avais sinon pensé à créer une boucle do...while dans laquelle j'insère deux if, le premier calculant n+2 et le deuxième calculant (-n+2), avec à chaque fois pour condition que le compteur < n...

Répondre à Yuku

15

Sacabouffe, le 17 oct 2008 à 22:55:47
  • +3

Oui aussi.
Sinon, une autre manière, tu peux calculer en deux fois.
Si tu veux calculer la somme jusqu'à 4*N+3N est donné.

sinx= 0;
for (n=0; n<=N; n++) {
        fact=factorielle(4*n+1);
	sinx = sinx + (x^(4*n+1))/fact;

}
for (n=0; n<=N; n++) {
        fact=factorielle(4*n+3);
	sinx = sinx - (x^(4*n+3))/fact;

}
Thought I heard a rumbling, calling to my name
Two hundred million guns are loaded, Satan cries "Take aim!"

Répondre à Sacabouffe

16

Yuku, le 17 oct 2008 à 22:56:35

Ouais c'est un peu comme ça que je pensais !

Mais j'ai du mal avec la boucle for...

Répondre à Yuku

17

Sacabouffe, le 17 oct 2008 à 22:58:53

OK !
Enfin voilà... je vais pouvoir t'aider beaucoup plus, ça fait une éternité que j'ai pas touché du C++ :-( Thought I heard a rumbling, calling to my name
Two hundred million guns are loaded, Satan cries "Take aim!"

Répondre à Sacabouffe

18

Yuku, le 17 oct 2008 à 22:59:29

C'est déjà beaucoup ! :)

Répondre à Yuku

19

Sacabouffe, le 17 oct 2008 à 23:02:03

Si tu le dis... 8-)
Si t'as un problème plus pointu à résoudre, fais un nouveau sujet, parce que là, je serai vite dépassé. Et dans un sujet qu'a déjà reçu des réponses, je suis pas sûr que quelqu'un de compétent vienne y mettre son nez :-D Thought I heard a rumbling, calling to my name
Two hundred million guns are loaded, Satan cries "Take aim!"

Répondre à Sacabouffe