Comparer multiplications et additions

Bonjour,

Je débute en C et avec Visual Studio 2010. Je suis en thèse en cryptographie et j'ai besoin de comparer la durée nécessaire pour faire une multiplication de 2 nombres de 8 bits et la durée pour une addition de 2 nombres de 8 bits.

Pour l'instant, j'ai tapé ça :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

#include <stdio.h> #include <stdlib.h> #include <time.h>   int main(void){ int i = 0; int nombre_aleatoire = 0; for(i=0; i<10000; i++){ nombre_aleatoire = rand()*rand(); nombre_aleatoire = rand()+rand(); } return 0; }

---

J'aimerais obtenir les temps passés sur chaque ligne mais je n'y arrive pas avec l'analyseur de performance.


Merci d'avance pour votre aide.

Bonjour,

Pour faire ce que vous voulez (calcul de temps d'une portion de code), il faudra rajouter du code.
Ce code suit l'algorithme suivant:

Code:

---

1 2 3 4 5

t1=récuperation_du_temps() calcul t2=récupération_du_temps() Le temps du calcul -> t2 - t1()

---

Maintenant, la fonction pour récupérer le temps.
Ah tiens, c'était dans la FAQ -> http://c.developpez.com/faq/?page=da...E_chronometrer

Par contre, ce ne sera jamais fiable pour calculer correctement le temps d'exécution d'une portion de code, car il faut tenir compte aussi des autres programmes qui tournent en parallèle (système multitâches).

Merci pour votre aide !

J'ai réussi à le faire en maple et j'ai de "mauvais" résultats.
L'addition de 2 nombres de 8 bits est seulement 20% plus rapide que la multiplication de nombres de 8 bits. Je m'attendais à ce que soit au moins 4-5 fois plus rapide ce qui rend les résultats de mon article beaucoup moins impressionants (en gros, j'ai modifié un schéma d'identification en divisant par 2 le nombres d'opérations et en passant de multiplications à des additions, je m'attendais à un gain de temps de calcul très significatif).

Mon code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

#include <stdio.h> #include <stdlib.h> #include <time.h> //Ne pas oublier d'inclure le fichier time.h   int main(void){ clock_t start, end; double elapsed; start = clock(); int i = 0; int nombre_aleatoire = 0; for(i=0; i<100000000; i++){ nombre_aleatoire = rand()*rand(); } end = clock(); /* Arret de la mesure */ elapsed = ((double)end - start) / CLOCKS_PER_SEC; /* Conversion en seconde */ printf("%.2f secondes entre start et end.\n", elapsed); return 0; }

---

Mes résultats :
4.64s pour l'addition et 4.67s pour la multiplication :(

Vous auriez des idées pour m'aider ?

Ca me parait impossible que les temps soit si proche

La fonction "rand()" est une fonction couteuse. Vous ne devriez pas l'inclure dans votre mesure (soit, sortez les rand() de la boucle)
Soit générez un gros tableau en mémoire dynamique, avant :p

Je doute qu'il y ait une différence significative de temps d'exécution entre multiplications et additions sur les processeurs modernes

Et sur des systèmes "portables" type carte à puce où les capacités de calculs sont très limités ? intuitivement, vous donneriez quel ordre de grandeur entre les 2 opérations ?

Il n'y aura aucune différence, même sur des puces de bas niveau. Il faudrait vraiment descendre en dessous de quelques centimes d'euro par puce pour voir des circuits qui montreraient une différence entre la multiplication et l'addition, surtout en entier 8bitsx8bits, et encore, seulement si la puce en question est une puce dédiée à autre chose que du calcul.
De plus en plus de puces proposent aujourd'hui une instruction "MAD" faisant soit une addition, soit une multiplication, soit les deux, sur bien plus que 8 bits, en un nombre de cycle exactement identique quelle que soit l'opération (presque toujours 1 seul cycle).

La seule différence que vous pourriez mettre en avant aujourd'hui serait en cas de stockage du débordement (8+8 -> 9 bits, 8x8 -> 16 bits, donc utilisation de la mémoire un peu différente APRES l'opération,ce qui peut éventuellement influer sur un benchmark: ne pas oublier qu'aujourd'hui, la manipulation de la mémoire est de plusieurs ordres de grandeur plus lente que l'arithmétique, en particulier en ce qui concerne la latence).

Je travaille dans l'embarqué depuis plus de 26 ans (!), et certes autrefois votre problématique était particulièrement présente. Par exemple, il me semble me souvenir que le 6809 a introduit pour la première fois dans le jeu d'instructions d'un µP généraliste une multiplication 8x8 bits. Je ne travaille pas du tout sur les cartes à puces, mais j'imagine mal un système de cryptographie moderne pouvant tirer un avantage de votre réorganisation d'instructions, à une époque ou un téléphone de poche écrase un Cray 2, et où l'importance des traitement graphiques force quasiment la présence d'une forme ou d'une autre d'OpenGL, d'où la présence généralisée d'une instruction MAD 128 bits dans le moindre bidule à 100 euros.

Pour prendre un peu de recul par rapport à votre problématique, ne pas oublier que dans un environnement moderne, les bandes passantes, branchements prédictifs, réutilisations de caches et autres astuces d'adressage ont beaucoup plus d'importance sur la vitesse d'exécution que les instructions elles-mêmes. Saviez-vous que très classiquement aujourd'hui, lorsqu'une condition entre dans le pipeline, son résultat n'étant pas connu à toutes les étapes du pipeline, les deux branches possibles de la condition sont exécutées simultanément avant que la décision valide l'une ou l'autre des exécutions "après coup"? Quand une technologie en est à ce stade, il est peut-être peu productif de se pencher sur les micro optimisations basées sur des vérités datant de 20 ou 30 ans.

Si j'avais en charge la conception d'une puce servant à un projet cryptographique où l'on démontrait l'utilité de faire une multiplication au lieu d'une addition (ou l'inverse d'ailleurs), la première chose que je ferais serait d'ajouter une instruction qui fait exactement ce qu'il faut en un cycle (littéralement 10 lignes de VHDL), et puis je passerais à autre chose l'après midi. Mieux, je demanderais à un stagiaire de le faire, parce que c'est vraiment très simple tout en étant quand même les mains dans le cambouis. ;)

Wow !!

Merci beaucoup pour votre réponse très complète. C'est vraiment très appréciable pour nous d'avoir votre avis d'expert sur cette question. Je vais voir si justement nous pouvons mettre en avant une meilleure gestion de la mémoire ou de la bande passante. J'avoue que je ne savais absolument pas qu'on en était à un tel point d'efficacité sur l'arithmétique.