!! Rapidité !!Résolu

Question

Je voudrais savoir qu'est ce qui est plus rapide ?

1) Une division d'un grand nombre par un plus petit
2 )Ou une multiplication de deux nombre ?

??

Merci

ZogStriP
IA pour : Incomplet de l'Ancéphale  %-6 
http://blog.developpeur.org/zogstrip/
 8-)  www.rubikscubor.fr.st  8-) 

#define ThatTheQuestion ((bb) || !(bb))

cs_AlexMAN · Accepted Answer

ZogStrip, le break apres le return TRUE ne sert strictement a rien, puis que ta fonction aura rendu la main a la fonction appelante. Mais c vrai que ta fonction est bizar, et celle ci ne travaillant que sur des entiers, un chiffre come 3 ou 6, ne renverra rien...Enfin c ptet le but etant donné ke tous les nombres ont une racine carré..Mais bon, voila comment jlecrirais : 

int isSquare(int nbre) {
    int i = sqrt(nbre); //conversion implicite de double en int

    i *= i; 
   if (i == nbre) return 1;

   return 0;
}

Voila ++

Alhexman

vecchio56 · Answer

Ca dépend des cas: 100000/1 est surement plus rapide que certaines multiplications, mais en général, je dirais qu'une multiplication doit être plus rapide

#define ThatTheQuestion 1

BruNews · Answer

La multiplication est a tout coup plus rapide, il n'y a pas d'instruction plus lente que 'div'.

ciao...
BruNews, Admin CS, MVP Visual C++

cosmobob · Answer

non les divisions prennent toutes le meme temps a moins que le compilateur ait optimisé le code et ait fait la division lors de la compilation...
int a = 1000;
int b = 1;
a/b va prendre autant de temps que n'importe quelle division.

Sinon effectivement les multiplications sont bcp plus rapides.
a+ ;)

cs_djl · Answer

ca tient aussi bien pour les reels que pour les entiers ?

cs_LordBob · Answer

moi je voudrais connaitre l'interet de savoir si la multiplication est plus rapide que la division !!! je ne me suis jamais poser la question, et je ne vois pas ou serait l'utilité de savoir une telle chose...
Bob...

"La chance accorde ses faveur aux esprits avertis..."

BruNews · Answer

djl > me semble que oui mais je n'ai pas fait de mesure dessus, faudra tester pour etre sur.
LordBob > quand tu auras a faire un prog ou le temps de calcul est primordial, tu seras oblige d'y penser. En medecine c'est le cas par exemple.

ciao...
BruNews, Admin CS, MVP Visual C++

cs_djl · Answer

ouai, genre dans une operation tu essayera de remplacer les division par des multiplications

ZogStriP · Answer

C'etait pour savoir si ma fonction était rapide ou si il y avait plus rapide :

// Fonction permettant de savoir si un nombre est un carré :
int __stdcall isSquare(long nombre)
{
long compteur, tmpCarre;
for(compteur = 2; compteur < nombre; compteur++)
{
tmpCarre = compteur * compteur;
if(tmpCarre == nombre)
{
// Renvoie 1 :
return true;
break;
}else if(tmpCarre > nombre){
break;
}
}
return false;
}

ZogStriP
IA pour : Incomplet de l'Ancéphale  %-6 
http://blog.developpeur.org/zogstrip/
 8-)  www.rubikscubor.fr.st  8-) 

#define ThatTheQuestion ((bb) || !(bb))

BruNews · Answer

Pas compris le but.

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

savoir si un nombre est un carré parfait tiens

BruNews · Answer

Enleve cette boucle.
Prends la racine carree, et mets la en int.
compare si (racCar * RacCar) == nbr.

ciao...
BruNews, Admin CS, MVP Visual C++

BruNews · Answer

Rectif:
pas de cast en int pour certitude.

ciao...
BruNews, Admin CS, MVP Visual C++

BruNews · Answer

Oui c'est bien cast int, on a le resultat a coup sur.
Passer du coq a l'ane, je ne sais plus ou j'en suis.

ciao...
BruNews, Admin CS, MVP Visual C++

BruNews · Answer

ZogStriP et AlexMAN, vu que vous etes tous 2 clients asmfr maintenant, sortez donc le listing produit par le compilo et regardez si on peut gagner qlqchose.
- Si appel externe pour sqrt, alors inserer asm correspondant.
- isSquare doit prendre param en registre (gros benef).
Bon exercice, non ?

ciao...
BruNews, Admin CS, MVP Visual C++

cs_AlexMAN · Answer

BruNews > wè pas mal, surtt si tu te proposes pour corriger apres...Je mi attelle de suite.

BruNews · Answer

ok bien entendu.
et y a pas le feu, bien reflechir avant proposition, me permettra de finir ce que j'ai en route.

ciao...
BruNews, Admin CS, MVP Visual C++

BruNews · Answer

au fait, DWORD en param pour tres longue plage, ok ?

ciao...
BruNews, Admin CS, MVP Visual C++

cs_AlexMAN · Answer

Brunews, le code assembleur generé par VC est incomprehensible ! j'obtien des fonctions du style
ldarg.0				; _nbre$
conv.r8
call		?sqrt@@$$J0YANN@Z
conv.i4
stloc.0				; _i$

je dois prendre le code asm avec un desassembleur ?

cs_AlexMAN · Answer

Nop c bon, j'ai trifouillé ds les propriété du projet et jobtiens du "bon" asm... 

++ Brunews

BruNews · Answer

donc tu vois appel vers ?sqrt, c'etait couru comme truc.
Le truc c'est justement ici, on peut gagner gros en supprimant cela et mettre tout le code sur place.
__declspec(naked) int __fastcall isSquare(unsigned int dwnum)
{
  __asm {
    ; code ici
    ret 0
  }
}

voila comment doit se presenter. Sur que faut se creuser un peu les meninges, nenni desassembler.
Je te fais le prog avec une dialog pour saisir nombre et tester.
Envoie propositions sur mon mail, tu auras le mien en retour.

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

BruNews> Dans ta solution, il faut faire une multiplication de 2 doubles, c'est paspossible de calculer la racine carrée et de regarder si la partie décimale est nulle (on sait comment est codé un double)

BruNews · Answer

on a rectifie en DWORD.

ciao...
BruNews, Admin CS, MVP Visual C++

cs_AlexMAN · Answer

vecchio56 > justement je ne sais pas, comment est codé un double ? et pkoi tu parles de 2 double a multiplier, il nen a jamais ete question ! si ?

vecchio56 · Answer

Je me suis trompé, c'est deux DWORD qu'on multiplie
J'ai essayé de faire l'exo mais je dois être un gros débile, j'y arrive pas (en fait j'arrive pas à utiliser les double et à appeler sqrt)

BruNews · Answer

AlexMAN > je te poste sur ton mail un chm de mon cru (asm en french). Devrait t'aider a resoudre ce probleme.

ciao...
BruNews, Admin CS, MVP Visual C++

BruNews · Answer

vecchio56 > tu veux aussi la fpu french chm ?

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

Je l'ai déja, version du 19/04/2003, mais je sais pas si ca va suffire...

cs_AlexMAN · Answer

vecchio56 > on ne doit pas utiliser de double, genere le code asm avec VC, si tu las pas, jte lenvoie...

Brunews > Merci pour le chm, justement jen cherchais un sur le net...merci donc !
Ah oui aussi, je voulais te dire qu'un appel a une fonction ftol2 est effectué (je presume pour convertir le resultat de double en int), donc ya 2 appels a des fonctions externes, ca fait bocou pour skon veut faire non ? 

++

vecchio56 · Answer

Voila ce que j'ai, mais je ne comprends pas tout


_isSquare@4 PROC NEAR					; COMDAT
; Line 26
fild	DWORD PTR _dw$[esp-4]
push	esi
mov	esi, DWORD PTR _dw$[esp]
test	esi, esi
jge	SHORT $L74763
fadd	QWORD PTR __real@41f0000000000000
$L74763:
fsqrt
call	__ftol2
; Line 27
imul	eax, eax
sub	eax, esi
neg	eax
sbb	eax, eax
inc	eax
pop	esi
; Line 28
ret	4
_isSquare@4 ENDP

BruNews · Answer

justement pour cela qu'on refait, suppression de tout appel externe, on gagne enorme.

vecchio56 > si si doit suffire.

ciao...
BruNews, Admin CS, MVP Visual C++

cs_AlexMAN · Answer

J'ai généré le code asm avec l'ekivalent C au dessus des instructions correspondantes. voila ce ke j'ai (un ptit diff de ton code)

push	ebp
mov	ebp, esp
push	ecx

; 5    : 	int i =(int)sqrt((double)nbre); //conversion implicite de double en int

fild	DWORD PTR _nbre$[ebp]
sub	esp, 8
fstp	QWORD PTR [esp]
call	_sqrt
add	esp, 8
call	__ftol2
mov	DWORD PTR _i$[ebp], eax

; 6    : 	i *= i; 

mov	eax, DWORD PTR _i$[ebp]
imul	eax, DWORD PTR _i$[ebp]
mov	DWORD PTR _i$[ebp], eax

; 7    : 	if (i == nbre) return 1;

mov	ecx, DWORD PTR _i$[ebp]
cmp	ecx, DWORD PTR _nbre$[ebp]
jne	SHORT $L586
mov	eax, 1
jmp	SHORT $L582
$L586:

; 8    : 
; 9    : 	return 0;

xor	eax, eax
$L582:

; 10   : }

mov	esp, ebp
pop	ebp
ret	0

J'ai desactivé auparavant TOUTES optimisations, pour avoir le code le plus "pur" possible, ce ke tu nas pas fait je pense, car tu as un appel a fsqrt directement, alors ke mon prog passe par la fonction standard sqrt...Bon enfin, voila, dis moi ce ke tu comprend pas..Les 2seules fonction inconu ptet sont : 

fild > empile une valeur reelle 
fstp > stocke une valeur reelle 

Voila

BruNews · Answer

fild > c'est l'inverse, empile du SIGNED en fpu.

le prob, on traite du DWORD (non signe), reflechir....

Mettre fonction en __fastcall.
Pousser optimisation compilo maxi et decocher le stack frame.

ciao...
BruNews, Admin CS, MVP Visual C++

BruNews · Answer

Ohe j'ai fait ma func, reste a faire batterie de tests.
Je fais quelques controles avec calculatrice Windows et je vous passerai le proj complet VS2003.
Je previens que rien a voir avec ce que fait le compilo.

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

Je t'ai envoyé un truc, dis moi ce que t'en pense,mais soit pas trop violent quand même

cs_AlexMAN · Answer

Ne me lenvoie pas tt de suite stp, jprefererais essayer encore un peu, sinon je c ke jV mater ton code et ne rien faire...jgalere un ptit peu au nivo des instructions fpu et des registres (en gros tt koi) mais jV yarriver...

merci ++

vecchio56 · Answer

Moi j'ai fait un tuc bien bien dégueulasse je crois, mais enfin ca a l'air de marcher.
A part ca j'ai acheté un livre sur l'assembleur, et dans les instruction du pentium il n'y a pas toutes ces intructions pour les flottants, et d'ailleurs ils en parlent jamais des flottants. C'est normal?

cs_AlexMAN · Answer

c des instructions du FPU donc wè c normal.
Ta acheté koi come boukin ?

BruNews · Answer

Pour sur qu'on va y arriver, j'ai un petit malaise aussi sur le mien quand nbr est tres grand, on l'aura !!!
OK quand sera au point, j'attendrai feu vert d'envoi.

vecchio56 > en fastcall, il n'y a pas de param, c'est passe en registre dans ECX.
naked force ecriture de VRAI asm car empeche compilo d'y mettre ses pattes, faut donc bien TOUT ecrire, plus de mnemo nommant un param ni quoi que ce soit de ce genre, rien que des registres et des adresses. Si tu touches autres que EAX,ECX ou EDX, il faut le rendre comme etait a l'arrivee.

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

Ca s'appelle "Assembleur x86", de Kip Irvine, je savais pas trop quoi prendre...

vecchio56 · Answer

au fait il y a combien de registres st(i) pour la fpu?? 8?

cs_AlexMAN · Answer

9 mais mais st(0) est reservé

cs_AlexMAN · Answer

oula,  g dit une betise : il y en a bien 9 mais ce n'est pas st(0) ki est reservé, il y a simplement un registre de flag ki permet de notifier toutes divisions par zero, overflows...etc, dsl pour l'erreur

BruNews · Answer

Je suis vraiment dans les choux, j'avais tout bon sauf que au debut j'excluais les nbr impairs, la senilite.....
Donc dispo.
Pour info, je ne me sers que des 3 registres generaux, rien a sauvegarder.

Vous pouvez adresser de st(0) jusque st(7).

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

ce qui nous fait 8

vecchio56 · Answer

Il est dispo ou ca le code?

BruNews · Answer

N'achete pas trop de livres de base qui vont t'embrouiller avec des instructions totalement obsoletes, en asm 32 bits suffit de savoir les mnemonics Intel. Tu les as d'ailleurs avec MASM32. Tout le reste est pure logique.
Pour l'optimisation faut lire Michael Abrash, le gros bouquin noir "Programmation graphique C/C++ Assembleur" est on ne peut mieux.

ciao...
BruNews, Admin CS, MVP Visual C++

BruNews · Answer

vecchio56 > je te le poste de suite.

ciao...
BruNews, Admin CS, MVP Visual C++

BruNews · Answer

proj complet parti.

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

et "Zen de la programmation graphique"?

BruNews · Answer

Du meme auteur forcement bien, c'est le maitre de l'optimisation.
Je le lisais quand paraissait en articles separes, nous rajeunit pas tout ça.

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

Merci pour le code

vecchio56 · Answer

T'es sur que ca vaut le coup, c'est pas un peu 'dépasse'?

cs_AlexMAN · Answer

Bon BruNews, je ny arrive pas trop, jte poste un bout de code, dis moi stp si c un bon debut : 

__asm {
push ebp
mov ebp, esp
sub esp, 8
mov esp, ecx
mov dword ptr[esp + 4], 0
fld qword ptr[esp]
fsqrt
sub esp, 8
fstp qword ptr [esp]
mov eax, dword ptr[esp]
        pop ebp
}

je ne pense pas kil faille un truc come ca, mais serieu je blok, bocou plus dur que ce ke je pensais..

BruNews · Answer

Si tu peux, prends celui que j'ai mis plus haut. Tout est a savoir dedans, il enumere au contraire tout ce qu'il convient d'ecarter a partir du Pentium, va tranquille c'est rien que du bon.

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

Sinon c'est quoi selon toi les ouvrages de références pour l'assembleur s'il y en a d'autres?

BruNews · Answer

faut prendre le modele que j'avais mis plus haut et supprimer la stack frame de ton code, c'est mortel pour les perfs.

sub esp, 8
mov esp, ecx  ????
si tu veux entrer valeur dans la pile
mov [esp], ecx
sinon tu deplaces esp et badaboum

je te poste le proj, vaut mieux que tu regardes et tu demanderas si tu ne comprends pas.

ciao...
BruNews, Admin CS, MVP Visual C++

BruNews · Answer

Meme reponse, point trop de bouquins en asm hormis les manuels Intel. Mieux vaut des books d'algo en C comme ceux de Sedgewick et ensuite si besoin on s'ecrit sa bibli en haute performance en asm.

ciao...
BruNews, Admin CS, MVP Visual C++

cs_AlexMAN · Answer

bon voila ton code alors (c pour le reprendre ds mes kestions)
__asm {
xor     eax, eax
    lea     edx, [esp-12]
    test    ecx, ecx
    ja      short nbrOK
    jb      short sqrtExit
    inc     eax
    ret     0
nbrOK:
    mov     esp, edx        ; ESP -= 12
    mov     [edx+8], ecx    ; sauve nbr
    mov     [edx+4], eax    ; ZERO
    mov     [edx], ecx
    fild    qword ptr[edx]
    nop
    fsqrt
    nop
    fistp   dword ptr[edx]
    nop
    pop     ecx
    xor     edx, edx
    mov     eax, ecx
    add     esp, 4
    mul     ecx
    test    edx, edx
    pop     ecx             ; ECX = nbr, ESP revenu
    jnz     short faux
    cmp     eax, ecx
    je      short sqrtExit  ; sort NON ZERO pour OK
faux:
    xor     eax, eax
sqrtExit:
    ret     0
}

- les seuls trucs ke j'ai pas compris, ce sont les "test reg, reg", je sais ke ca fait un 'et logik', enfin jvois pas le rappor, donc si tu pouvais m'expliker ce point la...
Puis ce que ji suis oci, kan tu fais un pop ecx par exemple, implicitement, il y a un "add esp, 4" ?

 merci pour le code, ca n'avait rien a voir avec ce ke j'ai fait, et jme dis ke j'ai ENORMEMENT de boulot..

Merci 

++

vecchio56 · Answer

BruNews tu ma pas dit ce que tu pensais de mon code que je t'ai envoyé

cs_AlexMAN · Answer

tiens, vecchio56, ta envoyé un kilo octet message, ca se fete !

BruNews · Answer

pop remonte esp de 4 (en 32 bits qui nous inyteresse ici).
on decompose le 'pop ecx':
mov  ecx, [esp]
add esp, 4

'test' est un 'and' SANS affectation sur la 1ere operande, ne fait que modifier l'eflags.

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

Ouais vive le Kilo, je sens que tu l'avais préparée celle la (oh merde qu'est ce que j'ai fait ?). Bon maintenant on va attendre celui de AlexMAN

cs_AlexMAN · Answer

Brunews > ok j'ai compris, dou le fait ke tu utilise des mov dword ptr[...] a la place de pop pour le passage de tes params a une fonction ? tu economises un add...

on fetera ensemble mon kilo,  les 4 kilo de Brunews (il devient lourd le brunews, va avoir du mal a naviguer..) et tes 2ko vecchio56..

vecchio56 · Answer

Moi je ne comprends pas poourquoi vous êtes obligés de toucher à esp, moi le truc que j'ai fait ne l'utilise pas et ca marche, mainenant peut être qu'il y a quand meme un probleme

BruNews · Answer

comment cela il marche ton truc ? m'etonnerait fort.
mets un nombre grand (bit 31 positionne) tu verras que forcement tout faux, fild charge du SIGNED !!!

ciao...
BruNews, Admin CS, MVP Visual C++

cs_AlexMAN · Answer

vecchio56 > j'ai pa vu ton code, si tu pouvais me l'envoyer par mail : alhexman@tiscali.fr

Moi j'ai touché a esp paske j'ai vu ca ds l'assembly generé par vc, et puis je savais pas vraiment a koi toucher donc voila...

cs_AlexMAN · Answer

brunews, tu travailles oci sur du signé : 

fild qword ptr[edx]
nop
fsqrt
nop
fistp dword ptr[edx]

ta du te planter ! bouh le BruNews !

vecchio56 · Answer

c tipar

BruNews · Answer

NON AlexMAN, c'est la ruse, regarde ce que j'ai mis 4 octests olus haut ([edx+4]), un beau zero et je fais un chargepment sur 64 bits. le dernier etant non positionne je reste bien avec du positif en fpu.

ciao...
BruNews, Admin CS, MVP Visual C++

cs_AlexMAN · Answer

ah ok, pas bete, j'avais pas remarké, dsl BruNews, j'enleve mon "bouh"...jpensais t'avoir eu, mais mm pas...

BruNews · Answer

oh la vache, j'ai fait une bourde en nettoyant le code.
test ecx, ecx aal 3eme ligne, remplacer par
cmp, ecx, 4

ciao...
BruNews, Admin CS, MVP Visual C++

BruNews · Answer

ben tu vois je me suis eu tout seul.

ciao...
BruNews, Admin CS, MVP Visual C++

cs_AlexMAN · Answer

wé wé, jvois ca, ce ki prouve ke personne n'est parfait !
Bon jte remercie pour ce ptit exo, si un jour d'autres t'en viennent a l'esprit, nésite pas, jtrouve ca assez sympa .

++

Alhexman

BruNews · Answer

oh merde j'etais en train de manger et je dis nimporte quoi...

comme carres parfaits:
0 ok
1 ok

je vais donc rectifier apres le cafe.

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

BruNews n'a pas la bosse des maths; on peut pas tout avoir

BruNews · Answer

bon y est va arriver, je modif aussi la func appelante.

Faut pas etre beaucoup bossu pour voir que 0 et 1 sont des carres, juste faut pas avoir a repondre a bobonne et autres futilites du meme acabit.

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

Et les nop dans ton code, c'est pour attendre le coprocesseur?

BruNews · Answer

oui et surtout eviter penalite quand instruction est dependante de fin de la precedente.

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

Il peut y avoir des chevauchements? Mais dans ce cas qu'est ce qui assure qu'un seul nop suffira?

BruNews · Answer

en vrai faudrait un fwait mais sur processuers modernes un nop doit suffire.

http://www.cppfrance.com/code.aspx?ID=24664

ciao...
BruNews, Admin CS, MVP Visual C++

vecchio56 · Answer

Bon j'arrête de t'embêter (pour aujourd'hui :))
Merci pour tout

BruNews · Answer

J'ai remodele la func asm sur la source, va nettement mieux au reveil qu'a des heures indues.

ciao...
BruNews, Admin CS, MVP Visual C++

cs_AlexMAN · Answer

Le reveil a 14h ?! ben yen a ki ont passé une nuit agitée ..
Merci, jV voir ta source si jcomprends encore tout..

++

!! Rapidité !!

84 réponses

Votre réponse

Discussions similaires