Puissance de 2 supérieur

Partagez votre expérience de PureBasic avec les autres utilisateurs.
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Puissance de 2 supérieur

Message par Fig »

Ca peut être pratique de calculer la puissance de 2 supérieur à un nombre. (pour faire un arrondi par exemple)
Par exemple:
1000 => 1024
33 => 64

Une petite procédure (32 bits) assez rapide. Je n'ai pas trouvé mieux comme méthode...
Si vous avez, je suis preneur. :D

Code : Tout sélectionner

ProcedureDLL SuperiorPower2(number.i)
  !MOV ebx,[p.v_number]
  !BSR ecx,ebx
  !MOV eax,1
  !SAL eax,cl
  !CMP eax,ebx
  !Je _suite
  !SAL eax,1
  !_suite:
  ProcedureReturn
EndProcedure
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 6.00LTS - 64 bits
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Puissance de 2 supérieur

Message par Ollivier »

Pour x86, c'est ok?

Code : Tout sélectionner

ProcedureDLL.L SuperiorPower2(number.L)
! MOV ebx,[p.v_number]
! LZCNT eax,ebx
ProcedureReturn
EndProcedure
PAPIPP
Messages : 534
Inscription : sam. 23/févr./2008 17:58

Re: Puissance de 2 supérieur

Message par PAPIPP »

Bonjour Fig et Ollivier

Avec une petite modification sur le 2em prg qui donne la puissance de 2 en fait compte le nombre de bit à 0

Code : Tout sélectionner

ProcedureDLL SuperiorPower2(number.i)
  enableasm
	MOV ebx,[p.v_number]
	BSR ecx,ebx
	MOV eax,1
	SAL eax,cl
	CMP eax,ebx
	Je _suite
	SAL eax,1
	!_suite:
	ProcedureReturn
		disableasm
EndProcedure
ProcedureDLL.L SuperiorPower2_(number.L)
  enableasm
  MOV ebx,[p.v_number]
 !LZCNT eax,ebx
  inc eax
  ProcedureReturn
  		disableasm
EndProcedure
For i=3 to 2048 step 5
result=  SuperiorPower2_(I)
debug str(i)+" => "+str(SuperiorPower2(I))
debug "2 ^"+str(result)+" =  "+str(pow(2,result))
next
Il reste encore une erreur sur 8 avec comme résultat 2^4=16 à la place de 2^3=8

A+
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Mesa
Messages : 1093
Inscription : mer. 14/sept./2011 16:59

Re: Puissance de 2 supérieur

Message par Mesa »

D'après le fonctionnement de LZCNT, le résultat de SuperiorPower2_ sera faux à chaque fois que le nombre à tester sera exactement un multiple de deux.

Seul BSR peut fonctionner dans tous les cas.

M.
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Re: Puissance de 2 supérieur

Message par Fig »

BSR a le même problème, ça explique le test que j'ai du faire pour ajuster en cas d'égalité. :|
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 6.00LTS - 64 bits
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Puissance de 2 supérieur

Message par Ollivier »

Version 32 bits :

Code : Tout sélectionner

ProcedureDLL.L Livide32(X.L)
! mov   ebx, [p.v_X]
! shl   ebx, 1
! mov   eax, 1
! lzcnt ecx, ebx
! shl   eax, cl
ProcedureReturn
EndProcedure
Version 64 bits :

Code : Tout sélectionner

ProcedureDLL.Q Livide64(X.Q)
! mov   rbx, [p.v_X]
! shl   rbx, 1
! mov   rax, 1
! lzcnt rcx, rbx
! shl   rax, cl
ProcedureReturn
EndProcedure
PAPIPP
Messages : 534
Inscription : sam. 23/févr./2008 17:58

Re: Puissance de 2 supérieur

Message par PAPIPP »

Bonjour à tous
Voici une solution sans boucle.
1) en prenant le Log base 2 du nombre.
2) en l'arrondissant à la valeur supérieure.
3) et en prenant la puissance de 2 en utilisant le décalage de l'arrondi.

Code : Tout sélectionner

Macro _q_t_
 "
EndMacro
Macro _n (__n)
_q_t_#__n#=_q_t_+Str(__n)+" "
EndMacro
Macro _Q (__Q)
_q_t_#__Q#=_q_t_+Str(__Q)+" "
EndMacro
Macro _d (__D,__nv=8)
_q_t_#__D#=_q_t_+StrD(__D,__nv)+" "
EndMacro


RESUL.F
RESULI.l
for i=2 to 2048 step 2
EnableASM
finit                                              ;; Initialisation FPU
FLD1                                             ;; Chargement de 1 dans ST
fild  [v_i]                                        ;; push ST dans ST1 et chargement du Nombre dans ST
FYL2X                                            ;; Calcul  ST1=st1*logbase2(du nombre) et pop de ST1 dans ST
fst  [v_RESUL]                                 ;; Déchargement du résultat dans la variable RESUL.F
RESEXP=Round(resul,#PB_Round_Up )  ;; Arrondi du log à la valeur supérieure
RESULfin=1<<resexp                         ;; Décalage en fonction du log ce qui correspond à 2^logbase2(du nombre)=Résultat  demandé
debug _n(i)+_d(resul)+_n(RESEXP)+_n(resulfin)
next


debug "************************************"
PROCEDURE.l POW2SUP(numb)
  protected RESEXP,RESULFIN,RESUL.f
EnableASM
finit
FLD1 
fild  dword [p.v_numb]
FYL2X 
fst  dword [p.v_RESUL]
RESEXP=Round(resul,#PB_Round_Up )
RESULFIN=1<<resexp
procedurereturn resulfin
disableasm
EndProcedure
for j=2 to 2048 step 2
  jj=POW2SUP(J)
  debug _n(J)+_n(jj)
next  

A+
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Puissance de 2 supérieur

Message par Ollivier »

@Fig

Est-ce que c'est bon ou pas, les procédures 32 et 64 bits?
Parce que je comprends pas bien la question!

Je vois et lis "puissance de 2 supérieure à n".

D'accord mais supérieur, ce n'est pas précis:
- Strictement supérieur?
- Supérieur ou égal?

Et les exemples ne précisent pas :
1024? Ça doit donner quoi? 1024 ou 2048?

Je choisis LZCNT parceque BSR n'est pas assuré de te donner le résultat prévu avec une source à zéro.

Donc, ce qui serait bien de préciser, c'est la séquence voulue de 0 à 9 au moins :
Ici, concrètement, j'ai:
0 : 1
1 : 2
2 : 4
3 : 4
5 : 8
6 : 8
7 : 8
8 : 8
9 : 16
Etc...

Avec ce code copié:

Code : Tout sélectionner

ProcedureDLL.L Livide32(X.L)
! mov ebx, [p.v_X]
! shl ebx, 1
! mov eax, 1
! lzcnt ecx, ebx
! shl eax, cl
ProcedureReturn
EndProcedure
Mais, on peut patauger longtemps...
1 1 2 2 4 4 4 4 8 8 ...
0 1 2 2 4 4 4 4 8 8 ...
1 2 4 4 8 8 8 8 16 16 ...
2 2 4 4 8 8 8 8 16 16 ...

Donc, précise s'il-te-plaît... (précise aussi si tu dois prendre en charge une source négative)
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Re: Puissance de 2 supérieur

Message par Fig »

Bonjour Olivier,
En fait l'idée est la suivante: l'utilisateur entre une valeur.
Le programme sélectionne une puissance de 2 égale ou supérieur.

Ca correspond à un besoin en fait.
J'ai fait une dll pour une table de hashage alternative à celle de PB.
L'utilisateur peut créer sa table en précisant le nombre de slot à utiliser. (comme avec pb).
Pour des raisons de performance, il vaut mieux que la table ait un nombre de slot puissance de 2, mais je ne veux pas embêter l'utilisateur de la dll avec cette contrainte.

Donc si il rentre 1000 il faut 1024 nombre de slot.
Si il rentre 512 ça reste 512 etc..

A priori pas nécessaire de prendre en compte les cas négatifs, mais pour un usage plus général, pourquoi pas ?
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 6.00LTS - 64 bits
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Puissance de 2 supérieur

Message par Ollivier »

Ah, je comprends pourquoi la réponse de Mesa.
Tente ça voir (je n'ai pas testé).
Mais je doute que ce soit plus rapide...

Code : Tout sélectionner

ProcedureDLL.L Livide32(X.L)

! mov eax, 1
! mov ebx, [p.v_X]
! cmovz ebx, eax
! shl ebx, 1
! dec ebx
! lzcnt ecx, ebx
! shl eax, cl

ProcedureReturn

EndProcedure
PAPIPP
Messages : 534
Inscription : sam. 23/févr./2008 17:58

Re: Puissance de 2 supérieur

Message par PAPIPP »

Bonjour à tous

voici les temps des 3 prg qui donnent les mêmes résultats.

le plus rapide celui de Fig très proche celui d'Olivier enfin le mien qui est dans les choux.

Code : Tout sélectionner

Macro __nbc (__cc)
__cc.q
!RDTSC
!PUSH edx
!PUSH eax
!POP dword[v_#__cc]
!POP dword[v_#__cc+4]
EndMacro
ProcedureDLL.L Livide(X.L) 
	 enableasm
	 mov eax, 1 
	 mov ebx, [p.v_X] 
	 cmovz ebx, eax 
	 shl ebx, 1 
	 dec ebx 
	 nop
	! lzcnt ecx, ebx 
	 shl eax, cl 
	 
	ProcedureReturn 
	 
EndProcedure
ProcedureDLL SupPow2(number.i) 
		!MOV ebx,[p.v_number] 
		!BSR ecx,ebx 
		!MOV eax,1 
		!SAL eax,cl 
		!CMP eax,ebx 
		!Je _suite 
		!SAL eax,1 
		!_suite: 
		ProcedureReturn 
	EndProcedure
	PROCEDURE.l POW2SUP(numb) 
		protected RESEXP,RESULFIN,RESUL.f 
	EnableASM 
	finit 
	FLD1  
	fild  dword [p.v_numb] 
	FYL2X  
	fst  dword [p.v_RESUL] 
	RESEXP=Round(resul,#PB_Round_Up ) 
	RESULFIN=1<<resexp 
	procedurereturn resulfin 
	disableasm 
EndProcedure 
max=1024
	  __nbc(T0)
	for j=1 to max
	  JLIV=Livide(J)
	next  
	__nbc(Tliv_T0)
	FOR j=1 to max
	  jPOW2=POW2SUP(J)
	next  
	__nbc(TPOW2_TLIV)
	for j=1 to max
	  JSUP=SUPPOW2(j)
	next  
	  __nbc(TSUP_TPOW2)
; 		debug _n(J)+_n(Jpow2) +_n(jSUP)+_n(jLIV)
	tliv.q=tliv_t0-T0 
	tpow2.q=TPOW2_TLIV-Tliv_T0 
	tsup.q=Tsup_tpow2-TPOW2_TLIV 
	messagerequester("Temps pour les 3 Sous/prg",_n(Tliv)+_n(tpow2)+_n(tsup))


A+
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Puissance de 2 supérieur

Message par Ollivier »

Bonjour PAPIPP,

Merci d'avoir testé et comparé. Je n'ai pas compris pourquoi l'ajout d'un NOP dans ma procédure pour mesurer?
PAPIPP
Messages : 534
Inscription : sam. 23/févr./2008 17:58

Re: Puissance de 2 supérieur

Message par PAPIPP »

Bonjour Ollivier

Le nop dans ta procédure m'a servi pour me permettre un arrêt avant l'instruction Lzcnt précédée de !
Or sur les instructions ASM précédés de ! on ne peut avoir d'arrêt.
L'instruction asm lzcnt n'est pas reconnue par PB on ne peut donc pas avoir d'arrêt dessus et pour l'exécuter directement en ASM il faut !
J'ai oublié de la retirer pour la mesure des temps.

J'ai mesuré à nouveau sans le nop et les résultats sont identiques. je pense que nop ne prend aucun cycle machine.

A+
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Ollivier
Messages : 4190
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Puissance de 2 supérieur

Message par Ollivier »

@PAPIPP

Je suis étonné par cette d'histoire d'arrêt (arrêter quoi notamment?).

J'ai obtenu des résultats 15% plus rapides que ceux de Fig sans mélanger les directives (EnableAsm et !), avec 2 opérations "Nop" au départ de la procédure.

Il me semble que c'est dû aux tailles des instructions machine. Un "nop" c'est 1 cycle. C'est dû aussi à la génération du processeur. La procédure de Fig fonctionne aussi sur des processeurs plus anciens.

Maintenant, je le trouve exigeant Fig, parce qu'on n'appelle vraiment pas si souvent que ça ce type de procédure pour une map.

Pour un calcul de grands nombres oui, mais d'autres algos plus performants sont utilisables.
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Re: Puissance de 2 supérieur

Message par Fig »

:D Je ne cherchais pas plus rapide, mais "mieux". Au sens de plus simple.
La juxtaposition de mes deux phrases donne effectivement cette impression.
Une petite procédure (32 bits) assez rapide. Je n'ai pas trouvé mieux comme méthode...
Je ne suis pas un expert en assembleur, je me demandais juste s'il n'existait une méthode plus simple pour obtenir ce genre de résultat. (une instruction particulière... ?)

Mais enfin, c'est toujours sympathique d'avoir le plus rapide aussi, pour la section trucs et astuces. :wink:

Merci pour votre interet en tout cas.
Ps: PapiPP ton code de 9h03 ne fonctionne pas en état (?)
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 6.00LTS - 64 bits
Répondre