PureBasic

Forums PureBasic
Nous sommes le Ven 22/Mar/2019 21:36

Heures au format UTC + 1 heure




Poster un nouveau sujet Répondre au sujet  [ 17 messages ]  Aller à la page 1, 2  Suivante
Auteur Message
 Sujet du message: Puissance de 2 supérieur
MessagePosté: Mer 11/Jan/2017 17:43 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1119
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:
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 : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Jeu 12/Jan/2017 7:51 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3298
Pour x86, c'est ok?
Code:
ProcedureDLL.L SuperiorPower2(number.L)
! MOV ebx,[p.v_number]
! LZCNT eax,ebx
ProcedureReturn
EndProcedure


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Jeu 12/Jan/2017 9:17 
Hors ligne

Inscription: Sam 23/Fév/2008 17:58
Messages: 551
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:
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Jeu 12/Jan/2017 14:33 
Hors ligne

Inscription: Mer 14/Sep/2011 16:59
Messages: 891
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Jeu 12/Jan/2017 17:10 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1119
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 : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Ven 13/Jan/2017 3:45 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3298
Version 32 bits :
Code:
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:
ProcedureDLL.Q Livide64(X.Q)
! mov   rbx, [p.v_X]
! shl   rbx, 1
! mov   rax, 1
! lzcnt rcx, rbx
! shl   rax, cl
ProcedureReturn
EndProcedure


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Ven 13/Jan/2017 11:23 
Hors ligne

Inscription: Sam 23/Fév/2008 17:58
Messages: 551
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:
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Sam 14/Jan/2017 15:46 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3298
@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:
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)


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Sam 14/Jan/2017 19:32 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1119
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 : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Lun 16/Jan/2017 7:55 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3298
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:
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


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Lun 16/Jan/2017 10:03 
Hors ligne

Inscription: Sam 23/Fév/2008 17:58
Messages: 551
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:
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Lun 16/Jan/2017 13:12 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3298
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?


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Lun 16/Jan/2017 23:43 
Hors ligne

Inscription: Sam 23/Fév/2008 17:58
Messages: 551
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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Mar 17/Jan/2017 10:46 
Hors ligne

Inscription: Ven 29/Juin/2007 17:50
Messages: 3298
@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.


Haut
 Profil  
Répondre en citant le message  
 Sujet du message: Re: Puissance de 2 supérieur
MessagePosté: Mar 17/Jan/2017 11:57 
Hors ligne
Avatar de l’utilisateur

Inscription: Jeu 14/Oct/2004 19:48
Messages: 1119
:D Je ne cherchais pas plus rapide, mais "mieux". Au sens de plus simple.
La juxtaposition de mes deux phrases donne effectivement cette impression.
Citation:
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 : 5.45LTS - 32 bits


Haut
 Profil  
Répondre en citant le message  
Afficher les messages postés depuis:  Trier par  
Poster un nouveau sujet Répondre au sujet  [ 17 messages ]  Aller à la page 1, 2  Suivante

Heures au format UTC + 1 heure


Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 4 invités


Vous ne pouvez pas poster de nouveaux sujets
Vous ne pouvez pas répondre aux sujets
Vous ne pouvez pas éditer vos messages
Vous ne pouvez pas supprimer vos messages

Rechercher:
Aller à:  

 


Powered by phpBB © 2008 phpBB Group | Traduction par: phpBB-fr.com
subSilver+ theme by Canver Software, sponsor Sanal Modifiye