Algos maths - Page 1

http://www.eudil.fr/eudil/jbeuneu/progrc.html

Ci-dessus, vous trouverez plein d'implantations d'algos celebres de maths.
A consommer sans moderation

Tiens, ça pourrait te servir pour la partie numérique du système de calculs de PedroM...

je bookmarque :]

Bookmarké

Moi aussi :]

Kevin: Oui et non. Pas tout de suite parcontre

j'ai pensé a la meme chose que toi kevin

Bah moi je pensais que PpHd avait trouvé ce site en cherchant des idées pour son CAS.

C'est sur que ca servira pour le CAS que je ferais peut etre un jour.
Mais en fait je cherchais un site sur le calcul de determinant. J'avais oublie comment le calculer numeriquement (Me parlait pas de le faire recurisvement, ca explose!)

Si tu veux réduire le nombre de développements de déterminants à faire, il faut introduire des zéros avec une élimination de Gauss.

Sinon, autre algorithme: calculer le déterminant en fonction des permutations. Chaque terme correspond à une permutation. Problème: c'est au moins en O(n!), et la génération des permutations risque même d'être en O(nⁿ). Donc je pense que l'élimination de Gauss soit une idée meilleure.

Ben je fais comme tout le monde. Decomposition LU, puis calcul du produit de la diagonale de U. L'algorithme naif le plus rapide.
Evidemment, comme toutes les operations sur les matrices, on doit etre capable de le faire en O(n^omega). avec 2<omega<3

O(n^3) avec un développement selon les lignes c pas très compliqué De toutes façons pour des trucs numériques t'as pas besoin d'une vitesse énorme non?

Euh sinon :

Donc je pense que l'élimination de Gauss est
une idée meilleure

Va dire que t'as pas besoin d'une vitesse enorme aux developpeurs de GMP. J'aimerais bien porter GMP pour TI n'empeche, puis mpfr.

Au fait, il y a déjà Bhuvanesh Bhatt qui en a porté une partie dans MathTools.

Moue. Seulement les multiplications a ce que je vois. Je suis meme pas sur qu'il estpris tout le paquet multiplication de GMP (Base, Kabasura, TomCook, et FFT selon la taille)>

Kabasura

c pas karatsuba plutot ?

et l'algo à base de FFT c pas un peu trop pour les nombres qu'on risque de manipuler sur TI ?

Ben tu manipules 30000 mots 16 bits x 30000 mots 16 bits, resultat sous 60000 mots 16 bits.
Si, si ca vaut le coup.
PS: Quoique je crois que la limite est plus basse. (naif .10. karatsuba. 100. tomcook. 3000 . fft).

pas plus de 100 pour karatsuba ?
bon. Si tu le dis.

Heu, en fait, c'est pour la version pre-cvs de GMP. Les auteurs ont optimise TomCook3, et ils ont bien decendu la borne. (Cf mailing list de GMP).