Comment mesure t-on l'efficacité d'un algorithme ?

invitefd4e7c09 · 17/09/2011, 17h15

Bonjour,

Je viens de créer un algorithme permettant d'effectuer le produit de deux entiers naturels.
Comment puis je mesurer son efficacité par rapport à tous ceux (et il y en a des masses) qui existent déjà ?

Je pensais partir sur le principe de compter le nombre d'opérations élémentaires qu'il faille faire pour aboutir au résultat.
Mettons deux entiers $\text{[math]}$ et $\text{[math]}$ , on aboutit au résultat en additionnant $\text{[math]}$ chiffres et en multipliant $\text{[math]}$ chiffres.
Les valeurs de $\text{[math]}$ et $\text{[math]}$ permettant alors de quantifier l'efficacité de l'algorithme.

Cordialement
Anthony

**erik** · 17/09/2011, 17h58

Salut,

Il faut que tu détermines le nombre d'opération d'opérations nécessaire en fonction du nombre de chiffres des deux nombres que tu multiplies.

Par exemple pour multiplier deux nombres de n et m chiffres (comme on l'apprend à l'école) il faut nXm opérations.
En général il n'est pas possible de déterminer le nombre exacte d'opérations, suivant le problème envisagé on s'intéresse alors au nombre d'opérations nécessaire dans le pire des cas ou au nombre moyen d'opérations nécessaire.

Une intro à lire : http://www.enseignement.polytechniqu...w-poly009.html

invite4ef352d8 · 17/09/2011, 18h03

Bonjour !

en général oui, on s'intéresse au "nombres d'opération élèmentaire" nécessaire. et plus précisement à la facon donc ce nombre croit avec la taille des donnée (en ignorant le plus souvent les constantes multiplicative qui ne sont pas toujours pertinente puisque le temps nécessaire à effectué une opération élémentaire dépend fortement de la machine qu'on utilise

par exemple, pour la multiplication de deux entier A et B, on va dire que "l'opération elementaire" c'est le fait d'additioner ou de multiplier deux entier (au niveau de l'ordinateur, les nombres A et B seront le plus souvent stocké en binaire, et donc "chiffre" sera en fait un 0 ou un 1 et additioner ou multiplicer des 0 ou des 1 c'est quelque chose d'immediat ^^) l'algoritme "classique" (celui qu'on apprend à l'ecole primaire) demande de l'ordre de n^2 opération (n étant le nombres de chiffre maximal de A et de B). En première approche on se moque assez royalement de savoir si c'est 4n² ou 12n² parceque par rapport à ce qui vient après c'est pas forcement pertinent. il existe une algorithme un peu meilleur utilisant une technique "diviser pour regner" (methode de Karatsuba il me semble) qui donne le résultat en n^(sqrt(3)). enfin, la multiplication par FFT (intéressante seulement si n est assez grand) donne le résultat en n.log(n).

invitefd4e7c09 · 17/09/2011, 18h10

Pour le cas de la multiplication qu'on apprend à l'école le constat est bien plus lourd car certes le nombre de multiplications est de n*m mais il y a également des additions à faire exemple : 23*47 donne 4 multiplications mais aussi 14 chiffres à additionner soit au final $\text{[math]}$ et $\text{[math]}$ pour reprendre mes notations. A titre de comparaison mon bricolage donne sur cette exemple $\text{[math]}$ et $\text{[math]}$ .

A voir en vidéo sur Futura · Aujourd'hui

invitefd4e7c09 · 17/09/2011, 18h17

L'algo Karatsuba revient souvent sur le tapis et pourtant, il n'aboutit pas à des valeurs faibles de $\text{[math]}$ et $\text{[math]}$ par rapport à d'autres algo d’où mon étonnement

**erik** · 17/09/2011, 18h45

Si tu veut être compris il faut laisser tomber tes alpha et tes mu.

L'algo de Karatsuba est en $\text{[math]}$ (n étant le nombre de chiffres des deux nombres à multipli),ce qui est une amélioration (sans être exceptionnel) par rapport à l'algo (scolaire) est lui en $\text{[math]}$ (même en tenant compte des additions en plus des multiplications on reste en O(n²))

Si tu ne mesures pas la complexité de ton algo, de la même manière que tout le monde cela va être dur de comparer.

invite4ef352d8 · 17/09/2011, 19h31

Si tu trouve que Karatsuba est moins efficace que ton algoritme c'est parceque tu regarde tes trop petit nombre !
en pratique, quand on travail sur un processeur classique, additionner ou multiplier deux nombres codé sur 32 bits (donc inférieur à 2^32, ou compris entre 2^31 et -2^31 selon le codage utilisé), et garder le résultat modulo 2^32 et une opération élèmentaire. qui n'occupe qu'une unité de temps de processeur. réfkechir aux nombres de multiplication neccessaire pour multiplicer 37 et 52 n'as aucun sens ! surtout que dans l'ordinateur 37 et 52 sont stocké en binaire donc l'addition de chiffres décimal n'est pas une primitive intéressante.

donc chercher des meilleur algo de multiplication est interessant quand on aura de très très grand nombres (du genre plusieurs dizaine de chiffres en base 2^16 le plus souvent) l'algo classique - et très probablement aussi le tiens - demande alors environ n^2 opération élémentaire. alors que Karatusbu a un exposant <2 (et la multiplication par FFT encore moins) ce qui veut dire que "pour des nombres assez grand, karatsuba sera meilleur que ton algo". après la question de savoir quand utiliser Karatsuba et quand utiliser un algo plus traditionel est intéressante, mais c'est de l'optimisation déjà assez pointu.

invitefd4e7c09 · 18/09/2011, 08h50

Bonjour

Il semblerait que je n utilise pas la bonne façon de décrire l algorithme seulement voila je ne sais pas s il est en O(n) ou O(logn) ou tout autre chose Tout ce dont je puis dire c est qu il est question d exécuter que des additions (et ça apparemment ça va vite) et aucune multiplication. D autre part l algo gagne en efficacité avec la taille des entiers a multiplier (cf multiplier sans connaitre ses tables part. 2/2 ou il est question de multiplier deux entiers de 7 chiffres.

Cordialement
Anthony

inviteea028771 · 18/09/2011, 13h47

Ce que tu nous dis là ne nous avance pas vraiment pour savoir si ton algorithme est intéressant... Il va falloir que tu fasses le calcul de la complexité, ou au moins une estimation.

Une méthode pour l'estimer pourrait être d'implémenter ton algorithme (avec scilab par exemple, mais ça se fait très bien en C), d'ajouter un compteur d'opération, et de calculer $\text{[math]}$ , le nombre d'opérations nécessaires pour multiplier 2 nombres aléatoires de taille n.

Ensuite tu traces $\text{[math]}$ => si ça tend vers a>0, la complexité est probablement en O(n²), si ça diverge, la complexité est probablement moins bonne que O(n²), et si ça tend vers 0, la complexité est probablement meilleure que O(n²).

invitefd4e7c09 · 18/09/2011, 14h41

Merci pour cette réponse Tryss mais malheureusement je n'ai pas de compilateur en C et en plus je suis une horreur en programmation et pour finir je ne vois pas (même le programme écrit) comment voir ce fameux compteur donnant le nombre d'opérations effectuées.
En tout cas cette façon de tester un algorithme me plait car elle met vraiment tout le monde à égalité.

Cordialement
Anthony

invite4492c379 · 18/09/2011, 15h05

Pas la peine de compilateur, quel est ton algo ?

invitefd4e7c09 · 18/09/2011, 15h31

Mon algo est donné sous forme de videos intitulées "Multiplier sans connaitre ses tables de multiplication".
Je ne sais pas si c'est suffisamment clair mais en tout cas ça suffit largement pour s'en sortir lorsqu'on a une feuille et un crayon.
Je ne sais pas le formaliser en tout cas ni sous forme de code ni sous forme de losanges etc...

invite4492c379 · 18/09/2011, 15h39

à la base un algo est juste une méthode, donc tu peux l'écrire en français. Certains formalismes existent mais rien de réellement universel.

invitefd4e7c09 · 18/09/2011, 16h02

Ok alors essayons :

En partant du fait qu'on veuille multiplier deux entiers $\text{[math]}$ et $\text{[math]}$ écris en ligne.

Déterminer la digit la plus grande de l'entier gauche (appelons la $\text{[math]}$ ).
Suivant la valeur de $\text{[math]}$ , on va additionner l'entier droit (terme 1) par lui même donnant (terme 2) puis ce résultat par lui même donnant (terme 4) etc donnant (terme 8)

On recopie sous chaque digit de l'entier gauche en commençant par la digit de gauche le terme (1), (2), (4) ou (8) ou une combinaison de ces termes en posant le chiffre des unités du terme dans l'alignement de la digit de l'entier gauche. Ensuite on passe à la seconde digit de l'entier gauche sous laquelle on recopie le terme (1), (2), (4) ou (8) ou une combinaison de ces termes en posant le chiffre des unités du terme dans l'alignement de la digit de l'entier gauche etc .......

On exécute l'addition de tous les termes recopiés sous l'entier gauche pour aboutir au résultat

C'est immonde à lire je sais

invite4492c379 · 18/09/2011, 16h20

Non ça va il y a pire. À première vue il est aussi efficace que la méthode de multiplication type école, plus gourmand en mémoire pour s'affranchir de la multiplication.

invitefd4e7c09 · 18/09/2011, 16h28

Comment avez vous fait pour :

1/ Décoder ce foutoir

2/ Coder ce foutoir

3/ En déduire finalement que ça vaut pas mieux que l'algo de l'école

invitefd4e7c09 · 18/09/2011, 16h38

Je reste perplexe tout de meme car sur cet exemple

On voit bien que la méthode école est beaucoup plus longue avec ses 49 multiplications !

**Médiat** · 18/09/2011, 17h10

Que donne votre algorithme pour multiplier 357953973 par 737537935 ?

**erik** · 18/09/2011, 17h11

Tu comptes pour 2 110 117 x 2 522 144 49 multiplications, c'est ok, je suis d'accord.

Mais tu considère que 2 110 117 + 2 110 117 ne compte que pour une addition, là pas d'accords, il faut compter 7 additions pour obtenir la somme.

En comptant le nombre d'addition que tu fait (digit par digit) tu fait une bonne cinquantaine d'opérations.

Je plussoie donc photon57, à la louche il faut autant d'opération que pour la multiplication standard. (par contre je doit avouer que je n'ai pas cherché à comprendre l'explication de ton algo)

invitefd4e7c09 · 18/09/2011, 17h18

Envoyé par erik

Tu comptes pour 2 110 117 x 2 522 144 49 multiplications, c'est ok, je suis d'accord.

Mais tu considère que 2 110 117 + 2 110 117 ne compte que pour une addition, là pas d'accords, il faut compter 7 additions pour obtenir la somme.

En comptant le nombre d'addition que tu fait (digit par digit) tu fait une bonne cinquantaine d'opérations.

Je plussoie donc photon57, à la louche il faut autant d'opération que pour la multiplication standard. (par contre je doit avouer que je n'ai pas cherché à comprendre l'explication de ton algo)

Vous noterez tout de même que l'algo école aussi nécessite de faire beaucoup d'additions digit par digit, car il ne suffit pas de se taper les 49 multiplications

invite4492c379 · 18/09/2011, 17h25

Envoyé par anthony_unac

Comment avez vous fait pour :

1/ Décoder ce foutoir

2/ Coder ce foutoir

3/ En déduire finalement que ça vaut pas mieux que l'algo de l'école

Je ne l'ai pas codé, ce n'est pas nécessaire. Je l'affirme car a priori, pour ce que j'ai compris, tu remplaces les tables de multiplications des chiffres par le calcul d'une table de multiplication du deuxième nombre.

Ton algo est bien celui-ci :

Code:

UnacMult( N : entier de n chiffres, M : entier de m chiffres) : entier
début
    kFoisM[0]=0
    pour chaque entier k de 1 à 9
        kFoisM[k] = M + kFoisM[k-1]

    res = 0
    pour c de 0 à n-1
        res = res + Decalage(kFoisM[N[c]],c)
fin.

où Decalage( E : entier, d : entier) est une fonction qui renvoie E x 10^d

Non ?

invitefd4e7c09 · 18/09/2011, 18h32

Envoyé par Médiat

Que donne votre algorithme pour multiplier 357953973 par 737537935 ?

A peu près ceci :
Pièce jointe 158709

**Médiat** · 18/09/2011, 18h39

Ma question portait sur l'efficacité de votre algorithme, pas son application (en tenant compte de la remarque d'Erik au message 19, en ne comptant une addition chaque fois que vous additionnez deux digits).

invitefd4e7c09 · 18/09/2011, 18h46

Ma question a l'origine portait également sur l'efficacité de l'algo (chose que je suis incapable de mesurer).
Concernant l 'addition digit par digit je ne sais pas combien il y en a ici beaucoup c'est vrai mais il y en a beaucoup également c'est vrai aussi avec la méthode école qui nécessite au préalable de se taper $\text{[math]}$ multiplications.

invite4492c379 · 18/09/2011, 18h47

Envoyé par anthony_unac

Ma question a l'origine portait également sur l'efficacité de l'algo (chose que je suis incapable de mesurer).
Concernant l 'addition digit par digit je ne sais pas combien il y en a ici beaucoup c'est vrai mais il y en a beaucoup également c'est vrai aussi avec la méthode école qui nécessite au préalable de se taper $\text{[math]}$ multiplications.

Pour mesurer l'efficacité d'un algo il faut déjà écrire cet algo, ma proposition est-elle correcte ?

invitefd4e7c09 · 18/09/2011, 18h50

Envoyé par photon57

Je ne l'ai pas codé, ce n'est pas nécessaire. Je l'affirme car a priori, pour ce que j'ai compris, tu remplaces les tables de multiplications des chiffres par le calcul d'une table de multiplication du deuxième nombre.

Ton algo est bien celui-ci

Non ?

Je n'en ai aucune idée car je suis incompétent en informatique.
Désolé mais c'est vrai

invitefd4e7c09 · 19/09/2011, 09h41

Bonjour,

En reprenant l'exemple proposé par Médiat : $\text{[math]}$
J'aboutis au résultat suivant (sans compter les digits égal à zéro):
************************
Avec mon algo: 194 additions de digits et 0 multiplication soit 194 opérations élémentaires
Avec l'algo école : 162 additions de digits et 81 multiplications soit 243 opérations élémentaires

Conclusion:
**********
L'algo école est moins performant et cela d'autant plus que Médiat a choisi un exemple très défavorable (le pire cas en fait) pour mon algo au sens ou les deux entiers à multiplier ne comportaient aucune puissance de deux.

**Médiat** · 19/09/2011, 10h53

Bonjour,

Envoyé par anthony_unac

Avec mon algo: 194 additions de digits et 0 multiplication soit 194 opérations élémentaires
Avec l'algo école : 162 additions de digits et 81 multiplications soit 243 opérations élémentaires

Quand, dans votre algorithme, vous utilisez plusieurs fois le calcul de 2n, 4n ou 8n, vous ne comptez qu'une fois ces calculs, en faisant pareil dans l'algorithme école, vous obtenez 36 multiplications et non 81, soit un total (je n'ai pas vérifié le nombres d'additions) de 198 comparé à 194, la différence n'est, de toute façon, pas significative, et s'inverserait sans doute avec d'autres exemples.

invite4492c379 · 19/09/2011, 13h21

pfff 5 minutes c'est court ...

Bref,

Envoyé par anthony_unac

Bonjour, 
 
En reprenant l'exemple proposé par Médiat : $\text{[math]}$ 
J'aboutis au résultat suivant (sans compter les digits égal à zéro): 
************************ 
Avec mon algo: 194 additions de digits et 0 multiplication soit 194 opérations élémentaires 
Avec l'algo école : 162 additions de digits et 81 multiplications soit 243 opérations élémentaires 
 
Conclusion: 
********** 
L'algo école est moins performant et cela d'autant plus que Médiat a choisi un exemple très défavorable (le pire cas en fait) pour mon algo au sens ou les deux entiers à multiplier ne comportaient aucune puissance de deux.

Je te fais une petite réponse rapide. Oui tu as raison, ton algo est plus performant sur les exemples qui vont bien selon ta méthode de définition de ce qu'est un opération élémentaire. 
 
Quelques remarques cependant: La complexité algorithmique d'un algorithme est définie pour le comportement de l'algorithme en terme de temps d'exécution par rapport à la taille des données en entrée, et aussi par rapport à la place requise pour le faire tourner. Une notation pour mesurer ces comportements est utilisée : la notation Grand O. Celle-ci désigne quelquechose de simple, le comportement de l'algorithme dans le pire des cas. Dire que l'algo recherche_binaire est en O(lg n) signifie que même dans le pire des cas doubler le nombre d'éléments dans un table  ne doublera pas le temps d'éxécution au contraire de l'algorithme naïf. Sans rentrer dans des calculs complexes, je t'affirme que la complexité en espace de ton algo est plus grand que l'algo école car à chaque opération tu dois recalcler une table d'addition spécifique à chaque donnée en entrée. <ul></ul>

invitefd4e7c09 · 19/09/2011, 13h28

J en doute fort vu que vous avez choisi le cas le plus défavorable et que même dans ce cas je bats l algo école

Comment mesure t-on l'efficacité d'un algorithme ?

Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Re : Comment mesure t-on l'efficacité d'un algorithme ?

Discussions similaires

améliorer l'efficacité d'un insert

augmanter l'efficacité d'un emetteur ultrasonique

Mesurer l'efficacité d'un cryptosystème

comment avoir la mesure principale d'un angle ?