Algorithme d'Avizienis et cie

Dans le cadre de mon TIPE sur l'optimisation des calculs informatiques ( et personnel aussi mais bon le boulot prime) , je m'interesse aux méthodes pour améliorer la vitesse des calculs par un ordinateur.

Je suis donc tombé sur différents algorithmes: Avizienis pour l'addition, Takagi, Yasuura et Yajima pour la multiplication, etc ... J'aimerais savoir si vous connaissez des sites parlant de ce sujet, meme si ils ne parlent pas spécifiquement des algorithmes cités ou des bouquins traitant le sujet.

Si de plus certains d'entre vous ont déja travailler un peu sur le sujet et pouvez me consacrer un peu de temps sur le sujet (mail , irc ou ce forum), cela me serait fort utile. si ces personnes le souhaitent, elles pourront etre cité dans le compte rendu (chacun veut sa gloire et c bien normal).

Je precise que je ne veux pas que vous fassiez mon travail a ma place mais la recherche de contact plus ou moins professionnels sur le sujet fait partie de l'epreuve.

ZUL

Ps : mon mail =) : mushroom.dargent@laposte.net

Je vais t'apprendre un truc d'ingénieur temps-réel :

Tu peux optimiser ton algo autant que tu veux, si il ne tient pas compte de la taille du cache et de l'algo utilisé par le cache, ca sert à rien...

En gros, le meilleur algo, c'est celui qui conserve le plus longtemps possible les données dans le cache.

Sur le sujet, j'ai un super exemple avec une multiplication de matrice normale et une multiplication par bloc de taille choisie en fonction du cache. Ca divise le temps de calcul par 150 dans le cadre d'une matrice de taille pathologique (choisie pour s'auto-chasser du cache d'une itération à l'autre).

Attention généralement, ce genre de remarque ne fait pas plaisir aux theoriciens de l'algorithmique, mais c'est une réalisé pratique incontournable !

A+

Alors, tu nous le montre ton exemple?
Ca m'interesse beaucoup.

Tu peux aussi utiliser le deroulage de boucle : plus d'instruction, mais moins de saut -> donc moins de vidage du pipeline -> moins de temps.
Mais Il y a maintenant sur es processeurs actuels des instructions qui permettent de fixer l'adresse du prochain saut.

Pour l'optimisation, il y a plusieurs choses :
-l'algorithme qui doit prendre en compte tous les parametres du processeur, tailles des caches, vitesse d'execution des differentes instruction
-le compilateur qui peut derouler des boucles, modifier des instructions... (peut etre fait automatiquement)

Qu'est-ce qui t'interesse ?

Actuellement je m'interesse plus aux algorithmes théoriques. le sujet est a presénté a des matheux et des physiciens qui ne sont pas forcement des elites en informatique.
Merci quand meme de toutes vos remarques : elles m'interressent bcp. ton exemple serait des plus interessant.

ZUL

> btavernier : ça c la définition du meilleur algo pour l'ingénieur temps-réel. Tu n'as absolument pas les mêmes contraintes que les théoriciens, qui vont chercher le meilleur algo lorsque la grandeur de référence tend vers l'infini, par exemple pour chercher des nombres premiers, comparer des fichiers etc.

Dans ce cadre d'optimisation je dirai qu'il y a plusieurs étapes :

D'abord l'optimisation de l'algorithme proprement dit, ie la minimisation de son efficacité théorique. Ensuite seulement l'optimisation de son implémentation, en fonction du compilateur utilisé, de l'algo utilisé par le cache mémoire comme le dit btavernier ou du CPU sur lequel tournera le prog comme le dit D[r]eadlock.

L'optimisation d'un algo se fait en général petit à petit, en faisant appel aux maths ou au feeling selon les cas. Si veux un exemple très simple d'optimisation, regarde ce post : http://forum.clubic.com/forum2.php3?post=5755&cat=13&config=&interface=&cache=cache&sondage=&owntopic=&p=1&trash=&subcat= Je suis joachim sur clubic, n'hésite pas à m'y contacter par messages privés.

Si tu veux d'autres exemples d'optimisations, un cas d'école est l'algoritme de Bresenham, bien qu'il soit aujourd'hui dépassé. Tu trouveras de nombreux articles avec Google.

Par ailleurs il existe plusieurs types de méthodes pour aller plus vite, chacune correspondant à un type de prob : progra dynamique (mon post sur clubic), algos génétiques, etc.

N'hésite pas à me contacter par MP (sur clubic stp), je te répondrai dans la mesure de mes possibilités (suis pas une bête :()