begin process at 2012 05 27 14:43:02
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > COMMENT UN PC FAIT DES MULTIPLICATIONS...

COMMENT UN PC FAIT DES MULTIPLICATIONS...


 Information sur la source

Note :
Aucune note
Catégorie :Maths & Algorithmes Niveau :Débutant Date de création :04/03/2004 Date de mise à jour :04/03/2004 20:27:14 Vu :3 915
Auteur : MetalDwarf

Ecrire un message privé
Commentaire sur cette source (11)
Ajouter un commentaire et/ou une note

 Description

Un tout petit code qui montre comment un PC fait une multiplication.
Je sais dans la fonction j'emploie la multiplication, mais en fait ce ne sont que des multiplications par 2, ce qui revient a decaler d'1 bit vers la gauche (et diviser par 2 revient a decaler d un bit vers la droite...).

D ailleurs la fonction mult2 fait la meme chose mais uniquement en employant
les operateurs << et >>.

Pour l addtion elle est definie egalement de facon recursive par le processeur
mais pour pouvoir le retranscrire en C il faut avoir en entree un tableau en base
2...

Source

  • unsigned int mult(unsigned int a, unsigned int b)
  • {
  • if(b==1) return a;
  • if(b%2) return mult(2*a,(b-1)/2) + a;
  • else return mult(2*a,b/2);
  • }
  • unsigned int mult2(unsigned int a, unsigned int b)
  • {
  • if(b==1) return a;
  • if(b%2) return mult(a<<1,b>>1) + a;
  • else return mult(a<<1,b>>1);
  • }
unsigned int mult(unsigned int a, unsigned int b)
{
	if(b==1) return a;
	if(b%2) return mult(2*a,(b-1)/2) + a;
	else return mult(2*a,b/2);
}

unsigned int mult2(unsigned int a, unsigned int b)
{
	if(b==1) return a;
	if(b%2) return mult(a<<1,b>>1) + a;
	else return mult(a<<1,b>>1);
}

 Conclusion

Il faut remarquer que ces fonctions sont surement beaucoup plus lentes que l operateur "*" car celui ci se traduit par une seule instruction assembleur, mais il effectue bien le meme travail.
De plus la definition recursive est correcte (prouvee en DS d info...).


 Sources du même auteur

Source avec Zip LECTURE/ECRITURE DES MSR (MODEL SPECIFIC REGISTER) EN C SOUS...
Source avec Zip Source avec une capture SOLUTION GRAPHIQUE APPROCHÉE AU PROBLÈME DES N CORPS
Source avec Zip Source avec une capture SERVEUR DE CHAT MULTITHREADE EN C SOUS LINUX
Source avec Zip TESTE SI UN TRES GRAND NOMBRE (PLUSIEURS MILLIERS DE CHIFFRE...
Source avec Zip COMPRESSION BZ2 (MIEUX QUE ZLIB) EN C.
Toutes les sources de MetalDwarf

 Sources de la même categorie

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture CHIFFREMENT DE VIGENERE par lajouad
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel
Source avec Zip Source avec une capture DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel
Toutes les sources de la catégorie Maths & Algorithmes

Commentaires et avis

Commentaire de BruNews le 04/03/2004 19:29:32 administrateur CS

diviser est decaler vers la DROITE et non la gauche, dixit ASM Intel.
EAX /= 2:
shr eax, 1
Que l'addition se fasse recursivement, je n'ai aucune info sur le sujet mais comment expliquer alors qu'elle s'effectue sur 2 registres en 1 SEUL cycle ???

Commentaire de MetalDwarf le 04/03/2004 19:35:31

Oui je ne connais plus ma droite et ma gauche!!! C est vrai parce que le bit de poids faible est a droite (meme si ca ne correspond a rien).
En fait la definition de l addtion est recursive mais un processeur traite tout ca en un cycle... Je sais que c est recursif car c etait unr partie de mon dernier devoir d info (en prepa...). En fait un ordinateur ne sait basiquement qu ajouter 1 a un nombre et tester des bits. A partir de la l addtion se construit recursivement (mais bien sur pas en faisant 1+1+1+1+...+1 n fois si il faut additionner n a un autre nombre).

C est donc uniquement la definition qui est recursive, mais de toute facon un processeur ne sait pas ce qu est la recursivite alors...
En realite l aspect recursif est cable dans le processeur.
J espere avoir eclaire ta lanterne et merci pour la correction...

Commentaire de Kirua le 05/03/2004 07:43:35

je comprends pas comment tu peux avoir une opération modulo % dans ta fonction de division, c'est pas une opération de base, le proco sait pas le faire d'un coup il me semble, si? chtrouve ça bizarre

sinon pour le test sur b == 1, pq ne pas tester aussi a? et pourquoi pas non plus 0?

Commentaire de BruNews le 05/03/2004 08:18:57 administrateur CS

Ben si le modulo est une operation de base indirecte.
Il est place dans EDX a chaque division.

Commentaire de ccarniel le 05/03/2004 08:42:59

Kirua :
le test (b%2)
peut s'écrire (b&1), dans ce cas je pense que tu verras mieux l'usage du modulo et tu comprendras.

MetalDwarf:
Sinon, je ne comprends pas pourquoi dans ton commentaire tu dis clairement que tu sais que tu utilises *et / et qu'ils sont équivalents à des décallages, alors pourquoi ne pas avoir remplacé directement ton
mult(2*a,(b-1)/2) + a;
par
mult(a&lt;&lt;1,(b-1)&gt;&gt;1) + a;

Le code aurait été nickel et personne n'aurait rien eu à redire :)

Alors, à quand l'addition et la division ?

Commentaire de Pamaury le 05/03/2004 15:47:16

juste une précision : le processeur sais ajouter plus de 1 à la fois, simplement le nombre est décomposé en bit et chaque bit est traité séparemment par le processeur par une suite d'additionneur basique ce qui veut dire que ce n'est pas récursif . Ensuite, il existe une autre méthode(non récursive) pour faire des multiplications mais je ne l'ai plus en tête sinon, pour une question de rapidité, &lt;&lt; et &gt;&gt; sont bien plus rapide que une dividion ou une multiplication par 2 .

Commentaire de sibi12 le 05/03/2004 18:41:53

salut,

arfff c'est con j'ai supprimer il y a pas longtemps des petite fonctions que j'avais fait permettant d'additionner, soustraire et multiplier  diviser et trouver le modulo le tout en assembleur juste en utilisant and or xor et not...je l'ai supprimer durant le grand nettoyage d'hiver...

j'avais fait ça pour m'exercer en assembleur...

@+

Commentaire de MetalDwarf le 06/03/2004 10:06:17

Pour l addition j ai dit que la definition en est recursive mais pas que l implementtation dans le processeur l est. Pour (a%2) c est effectivement equivalent a (a&1), puisque le bit de poids faible indique la parite.
Pour ce qui est de (b-1)/2, je voulais le montrer d abord de facon bien "visible". Mais pour l histoire il n a pas ete defini que le processeur sait soustraire 1 a un nombre dans cette operation. En fait comme b est impair dans ce cas (b-1)&gt;&gt;1 equivaut a b&gt;&gt;1...
Pour l addition peut etre bientot, quand j aurais retrouve le sujet de mon DS d info... Pour la multiplication je ne sais ps comment le processeur traite ca.

Une derniere remarque : effectivement &gt;&gt; et &lt;&lt; sont beaucup plus rapides que des multiplications ou divisions en general mais si le compilateur est malin dans le cas entier une division ou une multipliacation a par une puissance de 2 est remplacee par &gt;&gt; ou &lt;&lt;.

Commentaire de ccarniel le 06/03/2004 10:26:53

les compilateurs modernes sont effectivement capables de voir ce qu'il y a derrière ce qu'on écrit et donc de traduire un *2 par un &lt;&lt;1.

Mais c'est toujours un bon exercice d'essayer d'optimiser raisonnablement son code :)
( sans forcément rentrer dans des trucs de fous non plus, faut pas exagérer tout de même )

Commentaire de camelator le 07/03/2004 00:19:35

Généralement, pour faire ses décalages, un processeur utilise une instruction assembleur qui permet de décaler un registre et de sauvegarder le bit 0 qui devrait être perdu dans un flag spécial (le carry). Ce flag peut ensuite être testé, Il n'existe pas en C++ de telle fonction, alors il est difficile de retranscrire l'algorithme de multiplication en C++.

Commentaire de Pamaury le 09/10/2004 22:01:16

petite info en retard : la multiplication peut être faite de deux façon sur un processeur :(j'ai réalisé en schéma la première)
->codé à la bourin à l'aide d'addition et de décalage :
soit A et B les opérande
si le bit 0 de A==0 ajouter 0 sinon ajouter B
si le bit 1 de A==0 ajouter 0 sinon ajouter B<<1
si le bit 2 de A==0 ajouter 0 sinon ajouter B<<2
.....
Avantages : très très rapide
Défaut : BCP BCP BCP de portes(mais bon pas grave)

->Codé un algo récursiave à l'aide de porte(logique séquencielle)
Avantage : peu de porte(additionneur et module de répétition)
Défaut, assez lent car 1 cycle->1 addition

Pour l'instant c'est plutôt la deuxième solution utilisé .

Pour info, sur (preques ?) tous les processeur, une multiplication ne s'effectue pas en 1 cycle, ni même la plus basique des instruction(env 4 cycles ?) mais on considère que env 4 cycles -> une instruction de base

 Ajouter un commentaire

Nos sponsors


Sondage...

Comparez les prix


Samsung LE26B350 LCD
Entre 359€ et 417€

Visiter le guide achat

CalendriCode

Mai 2012
LMMJVSD
 123456
78910111213
14151617181920
21222324252627
28293031   

Consulter la suite du CalendriCode

A découvrir
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,811 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)