1. Accueil
  2. Tous les snippets
  3. Snippets C / C++ / C++.NET
  4. Comment un pc fait des multiplications...

Comment un pc fait des multiplications...

0/5 (11 avis)

Snippet vu 5 066 fois - Téléchargée 27 fois

Commenter

Contenu du snippet

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 / Exemple : 


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...).

A voir également

Ajouter un commentaire Commentaires
BruNews Messages postés 21041 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 17
4 mars 2004 à 19:29
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 ???
MetalDwarf Messages postés 241 Date d'inscription mardi 29 octobre 2002 Statut Membre Dernière intervention 23 janvier 2006
4 mars 2004 à 19:35
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...
cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
5 mars 2004 à 07:43
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?
BruNews Messages postés 21041 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 17
5 mars 2004 à 08:18
Ben si le modulo est une operation de base indirecte.
Il est place dans EDX a chaque division.
ccarniel Messages postés 23 Date d'inscription samedi 24 janvier 2004 Statut Membre Dernière intervention 17 octobre 2004
5 mars 2004 à 08:42
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<<1,(b-1)>>1) + a;

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

Alors, à quand l'addition et la division ?
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (MetalDwarf)