LES FONCTIONS DE MATH.H REPROGRAMMÉES

Commentaire de MoDDiB le 26/11/2003 20:40:43

Merci c'est pas con ton idée j'ai toujours voulu savoir comment il me trouver ca ce con ^^

Commentaire de Kirua le 27/11/2003 17:02:28

je n'ai pas regardé ton code, autant préciser.
pour les nombres premiers, c'est quoi (en français) ton algo?
en gros, moi je vois 3 possibilités:

1/ tester tous les nombres premiers inférieurs à la racine du nombre en question

2/ l'algo en 11 lignes des 3 étudiants indiens dont ils parlaient dans le Sciences & Vie Hors-Série Les Nombres Premiers :-P (oulà, dur ^^)

3/ générer une liste grâce au crible d'eratosthène jusqu'à avoir dépassé ou atteint le nombre cherché

à savoir qu'i lfaut qd meme utiliser le crible pour la méthode 1 donc... la 3 devient désuète, voir idiote lol :-P

c'est quoi ta manière de faire, si originale :-) :-)

Commentaire de garslouche le 27/11/2003 22:44:28

D'abord merci pour tous les compliments!

Pour Kirua ... oh la feignasse... t'aurais pu au moins jeter un coup d'oeil !
Mon algo n'a rien de bien sorcier! Sur le principe c'est effectivement tester tous les nombres impairs jusqu'à la racine de x; mais avant de passer à cette méthode radicale, je me sers d'une base de connaissance : les 100 plus petits nombres premiers. Le centième est qqc comme 541 il me semble et du coup vérifier un nombre inférieur à 541² = 292681 est quasiment immédiat! Bien sur plus la base de connaissances est grande pus l'algo est rapide pour les vérifier les grands nombres. Tu vois ça n'a rien de révolutionnaire mais je ne me souvient pas avoir déjà vu la combinaison de ces deux principes.
Sinon je ne connaissais pas l'alog des 3 indiens, tu pourrais me le filer que je regarde ça ?
Quant au crible d'érato c'est une méthode que je trouve très élégante mais pour être efficace elle demande bcp de mémoire ce qui la limite au petits nombres (elle devient donc sans interet). Pour mémoire (et pour ceux que ça interesse) je vais quand même décrire rapidement cette méthode. En gros on regarde si le nombre est multple de 2. Non ? Alors on retire tous les multiples de 2 de la liste des possiblités. Ensuite on fait pareil avec 3. Puis avec 5 (puisque 4 est dejà retiré). Etc...


Sinon je réitere ma demande concernant les fonctions de Bessel de deuxieme espece....Quelqu'un aurait-il la formule ?

Commentaire de garslouche le 29/11/2003 12:02:52

J'ai trouvé l'algo sur le net (merci google) mais il n'est pas si compliqué à comprendre!
Pour ceux que ça interesse :
http://www.cse.iitk.ac.in/news/primality.pdf

Par contre c'est un peu pipo de dire que l'algo ne fait que 13 lignes. Le tout premier test étant : si N est de la forme a^b alors le nombre n'est pas premier ! Je veux pas dire mais c'est pas si facile à voir (pas trop compliqué non-plus). Mais bref, c'est juste pour dire que pour le coder il faut plus de 13 lignes !

J'en ferai peut-être une source...

Commentaire de nEUrOne le 30/11/2003 15:58:39

Pour les nombres premiers, y'a des solutions plus rapide que le crible d'erastothene en passant par la convergence d'une certaine suite dans le plan complexe (par contre, j'ai oublié le tg de cette suite..... ca doit se trouver facile)

Commentaire de Kirua le 01/10/2005 21:36:02

pas la peine de mettre autant de décimales, un double n'en contient que 15 au mieux.

Commentaire de verdy_p le 28/01/2006 20:57:44

Tu devrais pouvoir optimiser le temps de calcul des sinus et cosinus
en partant du développement limité de chacun, mais en lescalculant en parallèle puisqu'il y a de nombreux facteurs communs, et puisque la séparation des quadrants est identique pour sinus et cosinus. D'ailleurs je m'étonne que la librairie C standard ne fournisse pas cette fonction de calcul simultané de sinus et cosinus.

Maintenant je m’étonne que pour tester la collision de deux points tu doivent passer par un calcul d’angles et de fonctions trigonométrique alors qu’un simple calcul de distance (ou plutôt du carré de la distance) suffit et n’emploie que des opérations linéaires simples avec polynomes du second degré uniquement, même en 3D (ou même en 4D si tu tiens compte du temps avec la vitesse des particules, ce qui permet d'anticiper leurs collisions et réduire considérablement le nombre de couples de particules à tester, notamment si tu veux réduire l'espace de recherche aux seuls points de l'univers présents dans un trapézoïde de visibilité qu'on peut approximer facilement avec une demi-sphère englobante exprimée par un simple point et un rayon: tout point hors de cette demi-sphère 4D ne peut être présent à l'image suivante, et il est possible de préduire à l'avance quand ce point y entrera pour alorsqppliquer une réelle projection, ce qui réduit aussi le nombre de projections à calculer).

Notes: une projection 3D ne nécessite pas de réexécuter un calcul trigonométrique pour chaque point, il suffit de calculer une seule fois la matrice 4D de transformation en 3D et de l'utiliser pour tous les points à représenter dans la scène (l'application de la matrice à un point se réduit alors à un simple calcul linéaire réduit à quelques termes).

Sinon la collision ne dépend pas non plus de cette matrice de transformation, et le calcul du sous-ensemble de points de la scène où il est utile de faire un test de collision ne dépend pas non plus de cette transformation.

Commentaire de Kirua le 29/01/2006 00:20:22

"il ne profite pas dufait que les 100 premiers nombres premiers sont triés"

je ne comprends pas cette phrase, tu peux expliquer?

Commentaire de verdy_p le 02/02/2006 21:37:34

La décomposition existante du nombre flottant avec une mantisse déjà bornée (dans {0} U [1/4, 1/2]) et la partie entière d'un logarithme déjà calculé dans l'exposant de base 2 permet effectivement des optimisations permettant de réduire le nombre d'opérations à effectuer, mais aussi d'augmenter la précision du résultat.

On le met à profit dans l'évaluation des fonctions cycliques (sin, cos...), ou même pour réduire la variable mantisse à un intervalle encore plus faible par exemple dans [0, 2ˆ-32] ce qui accroit très sensiblement la vitesse de convergence du développement limité (d.l.), en enréduisant le dégré, puisque les termes résiduels non calculés dedegré plus élevés du d.l. deviennent inférieurs àlalimite de précision de la somme du polynome (et donc non représentables).

Cette optimisation est très efficace pour les valeurs les plus grandes de la mantisse x, et pour les mantisses les plus petites, le degré des termes du polynome les rend déjà faibles encore plus rapidement.

Les fonctions optimisables de cette façon:
* sin, cos, tan (exploitation du cycle, et des symétries)
* log, exp, sqrt (exploitation de la séparation mantisse/exposant)
Le but est évidemment de réduire le nombre de boucles avecuncritère basé nonpassur une précision absolue (différenceavec la valeur exacte théorique) mais une précision relative (ou pourcentage), cette dernière étant déjà connue à l'avance en fonction du type de nombre (parexemple un long double sur 80 bits possède une mantisse de 64 bits dont la précision relative est de 2^-64).

Ces optimisations sont encore plus essentielles si on travaille sur des nombres à très grande précision (comme BigDecimal en Java)

Commentaire de Toggon le 20/05/2006 17:01:09

Salut garslouche!
Le site des nombres premiers n'existent plus maintenant je crois.
Peux-tu donner la formule stp?

Commentaire de verdy_p le 02/06/2006 01:02:47

je n'aipasdit qu'on réduisait la mantisse à un entier, juste que si la mantisse a un nombre de bits finis, cela fixe la précision puique la plus petite différencerelative représentable sera par exemple 2^-32 (par rapport à 1). Toute augmentation du degré du polynome pour le développement limité converge rapidement audelà de cette limite de précision, et donc n'a plus aucun effet sur la précision du résultat final.

Pour que le critère de convergence soit applicable il faut évidemment ramener la valeur absolue (non relative) à une valeur inférieure à 1. Dans le cas des fonctions sinusoïdales, une fois ramené par symétries et congruences à l'intervalle [0,PI/2], l'intervalle de lavaleur x dans l'intervalle est encore trop grand pour assurer la convergence, cependant x*2/PI est dans l'intervalle[0,1].

On traite alors le cas de x=PI/2 à part (résultat connnu: sin(PI/2)=1,cos(PI/2)=0) car le critère de convergence n'est pas satisfait. Notez qu'on peut aussi utiliser deux développements limités séparés pour sinus et cosinus, et les utiliser chacun sur l’intervalle [0,PI/4] où le critère de convergence est garanti (et offre une meilleure précision finale, avec un degré inférieur dans le développement limité nécessaire pour la valeur maximale, donc une plus grande rapidité de calcul).

(Noter que pour les valeurs négatives, le développement limité converge moins bien et est plus instable et moins précis à cause de l'alternance du signe des termes du polynome; onévite le probème en necalculant les développements limités que sur les valeurs positives)

D'autre part, on gagne en temps de calcul (et en précision finale) en écrivant les polynomes de développements limités sous la forme:

(...(((x+C[n])*x+C[n-1])*x+C[n-2])...)*x+C[0]

(puisqu'en effet on n'évalue pas les exposants successifs de x)
On notera que sous cette forme, les termes de plus grands degrés sont calculés depuis le début et leur apport s'amenuise au fur et à mesure puisque x est inférieur à 1. On évite l'imprécision du résultat final causée par l'accumulation d'erreurs d'arrondis. Pour garantir cela, ondoit veiller à ce que chaque terme contribue au maximum pour la moitié de lavaleur finale. Or, si on calcule le développement limité de sin(x/(PI/2)) dans l'intervalle [0,PI/4], on garantie effectivement cela.

Le dernier pas à faire pour l'optimisation est dans la façon de ramener le calcul dans l'intervalle:celanécessite normalement un calcul de congruence modulo 2PI, et laséparation des cas entre les diférents octants. Or c'est simple à faire: ondivise d'abord la valeur de x par 2PI, et alors leflottant se décompose souslaforme d'une puissance de 2 et d'une mantisse. Lapuissancepeut être ignorée par masquage en le forçant à 0 après une dénormalisation si l'exposant est négatif (équivalent à un décalage binaire de la mantisse), ce qui réalise la congruence, il ne reste alors plus qu'une mantisse dans [0,1], et on traite séparément les cas où la mantisse vaut 0 ou 1 et dont le résultat est connu. Il ne reste plus alors qu'à calculer le développement limité comme indiqué ci-dessus.

Des optimisations similaires existent aussi pour le calcul du logarithme et de l'exponentielle. Il suffit de connaître et appliquer les identités remarquables de ces fonctions!

On trouve ces optimisations (qui ont aussi l'énorme avantage de borner les erreurs d'arrondis et d'assurer la continuité des fonctions et de leurs différentielles) dans TOUTE bonne librairie mathématique.

Commentaire de verdy_p le 02/06/2006 01:27:16

Note finale: unsource C c'est bien si cela applique les techniques ci-dessus. Mais ce n'est souvent qu'une étape avant l'implémentation finale qui fait appel à d'autres optimisations (d'origine non mathématiques elles) destinées à réduire le temps d'exécution. Cette phase demande de l'expérience et fait appel à une bonne connaissance de l'assembleur et des propriétés des processeurs utilisés et des architectures matérielles.

Les meilleures librairies mathématiques actuellement (les plus rapides et les plus précises) pour PC sont celles écrites par Intel (mais elles sont sous licence commerciale). Microsoft a développé ses propres versions, mais elles sont moins bonnes et légèrement moins précises. Le compilateur GNU/C dispose de librairies mathématiques excellentes (meilleures que celles de Microsoft) mais pas encore au niveau de celles d'Intel.

Toutefois, dèsqu'on sort du cadre des calculs numériques sur les flottants normalisés IEEE, les librairies Intel sont insuffisantes. A ce jour, les meilleures librairies en haute précision sont celles de MathLab (licence commerciale), loin devant SCILab (commercial aussi), en attendant que le projet GNU améliore son projet concurrent et libre.

Si vous voulez vraiement être utiles, participez aux projets mathématiques GNU... Il y a beaucoup à apprendre, et dans les discussions vous aurez accès àdestas de travaux de référence libres publiés par des chercheurs mathématiciens d'universités publiques (donc travauxlibres de droit) ou publiés depuis longtemp (travaux désormais libres de droit, leurs brevets ayant expiré).

Commentaire de verdy_p le 08/06/2006 00:20:14

Un développement limité n'a rien àvoir avec identité remarquable.

* Le développement limité d'une fonction est son expression sous forme d'un polynome au voisinage d'un point à partir desvaleurs de ses dériviées en ce point. C'est une série dont la limite tend vers la fonction. Elle comprend une infinité de termes quisont despuissances de la variable pondérées par les coefficients du polynome, eux-mêmes ne dépendant que desvaleurs des dérivées successives en un seul point. Onconnait précisement les valeurs des dérivées successives en 0 des fonctions trigonométriques (ces valeurs de dérivées sont établies par démonstration de théorèmes à partie des définitions des fonctions, et chaque valeur détermine une identité remarquable, mais le développement limité n'est pasune identité remarquable)

* Une identité remarquable n'est pas forcément polynomiale et s'exprime le plus souvent sous forme d'une formule finie. Une identité remarquable est par exemple: sin(x)=cos(x+PI/2)

Je n'ai pas fait de confusion: une fonction approchante à l'infini n'est PAS mathématiquement identique à lafonction elle-même, donc le développement limité d'une fonction en un point reste différent de la fonction, même s’il permet d'approcher la valeur de la fonction avec un écart aussi petit que l'on veut. L'identité n'est établie QUE pour la valeur de la fonction au même point que celui pour lequel le développement limité a été défini. Pour toutes les autres valeurs, on obtient seulement une valeur approchante.

On utilise les développements limités pour approcher la fonction car on connait à l'avance la limite de précision du résultat,ce qui permet de déterminer le nombre de termes suffisants pour la série du développpement limité.