Accueil Ti-Gen Foire Aux Questions Chat sur le chan #tigcc sur IRC
Liste des membres Rechercher Aide
Bienvenue Invité !   Se connecter             Mes sujets   
Administrer
0 membre(s) et 1 visiteur(s) actif(s) durant les 5 dernières minutes Utilisateurs actifs : Aucun membre + 1 visiteur
Avant de poster sur le forum, il y a des régles de bases à respecter pour une bonne entente et un respect de tous.
Veuillez lire la charte du forum.
  :: Index » Forum TiZ80 » Algorithmie et optimisation » algorithme pour symetriser un nombre (18 réponse(s))
./POST DE DEPART (post n°0)   Marquer comme non lu.
Xantares Ecrit le: Vendredi 14 juillet 2006 à 18:36 Déconnecté(e)    Voir le profil de Xantares Envoyer un email à Xantares Envoyer un message privé à Xantares  

comment feriez-vous pour obtenir le symetrique binaire d'un nombre

je m'explique sur cet exemple :

s(139)=s(0b10001011)=0b11010001=209

donc le symetrique binaire de 139 c'est 209

j'ai essayer de faire leur somme, leur difference, mais je trouve pas de 'truc' pour avoir le nombre d'un coup.

j'ai remarqué ceci (sur 3bits là mais ca marche aussi avec plus)

0b000=0; s(0)=0b000=0
0b001=1; s(1)=0b100=4
0b010=2; s(2)=0b010=2
0b011=3; s(3)=0b110=6
0b100=4; s(4)=0b001=1
0b101=5; s(5)=0b101=5
0b110=6; s(6)=0b011=3
0b111=7; s(7)=0b111=7

maintenant regardons les differences i-s(i)

0 : 0-s(0)=0
1 : 1-s(1)=-3
2 : 2-s(2)=0
3 : 3-s(3)=-3
4 : 4-s(4)=3
5 : 5-s(5)=0
6 : 6-s(6)=3
7 : 7-s(7)=0

vous allez me dire que c'est du à la reflectivité du truc puisque s²(x)=x

mais on retrouve une valeur fixe (et c'est pas le nombre de bits désolé pour les petits malins) je trouve ca louche moi

c'est pour symetriser des sprites dans le sens horizontal,
dans le sens vertical échanger les nombres suffit

    
./Post n°1   Marquer comme non lu.
LionelA Ecrit le: Vendredi 14 juillet 2006 à 19:00 Déconnecté(e)    Voir le profil de LionelA Envoyer un email à LionelA Visiter le site WEB de LionelA Envoyer un message privé à LionelA  


je ferais avec une table précalculée
Auteur de Mode7 Engine pour ti68k
Auteur de F-ZERO for TI68k
Membre de Orage Studio
Mon site perso : http://www.tigen.org/lionela/
Le gite de mes parents à coté de Narbonne :
http://chaletdenis.free.fr/
    
./Post n°2   Marquer comme non lu.
geogeo Ecrit le: Vendredi 14 juillet 2006 à 19:04 Déconnecté(e)    Voir le profil de geogeo Envoyer un email à geogeo Visiter le site WEB de geogeo Envoyer un message privé à geogeo  


Moi je ne vois qu'une chose:
Faire une table sur 8 bits où tu fais correspondre à chaque indice sa valeur miroir et ensuite tu appliques cette table sur ton nombre.

En gros:

unsigned char FlipU_tab[256] = {....};

unsigned long FlipU(unsigned long n) {
  unsigned long res = 0;
  for (unsigned short i = 0; i < sizeof(n); ++i) {
     res <<= 8;
     res |= FlipU_tab[n & 0xFF];
     n >>= 8;
  }
  
  return res;
}


Code optimisable bien sur mais bon l'idée est là. De plus en assembleur se sera beaucoup plus rapide.
-Edité le Vendredi 14 juillet 2006 à 19:05 par geogeo-
Webmaster du site.
Programmeur sur TI68K. Arkanoid, Nebulus, GFA-Basic.

Plus d'informations sur GFA-Basic (un langage Basic pour TI68K).
http://www.tigen.org/gfabasic
    
./Post n°3   Marquer comme non lu.
Xantares Ecrit le: Vendredi 14 juillet 2006 à 21:56 Déconnecté(e)    Voir le profil de Xantares Envoyer un email à Xantares Envoyer un message privé à Xantares  

euh... en fait j'ai fini par trouver ! (3 heures plus tard lol)


int symbin(int a, int n)
{
       int s=0;
       while(n>0)
       {
              n--;
              s+=(a%2)*pow(2,n);
              a>>=1;
       }
       return s;  
}

-Edité le Vendredi 14 juillet 2006 à 21:57 par Xantares-
    
./Post n°4   Marquer comme non lu.
Link Ecrit le: Samedi 15 juillet 2006 à 00:22 Déconnecté(e)    Voir le profil de Link Envoyer un email à Link Visiter le site WEB de Link Envoyer un message privé à Link  

Je crois que tu peux remplacer a%2 par a&1 (l'optimiseur le fait sans doute) et pow(2,n) par 1<<n (là, je ne suis pas sûr que l'optimiseur le fasse)
    
./Post n°5   Marquer comme non lu.
Kevin Kofler Ecrit le: Samedi 15 juillet 2006 à 08:07 Déconnecté(e)    Voir le profil de Kevin Kofler Envoyer un email à Kevin Kofler Visiter le site WEB de Kevin Kofler Envoyer un message privé à Kevin Kofler  


Xantares :
pow(2,n)

Il ne faut jamais utiliser pow(2,n) sur des entiers!!! pow calcule sur des flottants!!! C'est très inefficace pour calculer des puissances de 2!!! Faut mettre 1<<n.

Et sinon, si n=8, 16 ou 32, j'ai nettement plus efficace (mais 68k only):
unsigned char symbin8(unsigned char a asm("d1"));
asm(".xdef symbin8
symbin8:
moveq.l #7,%d2
0: add.b %d1,%d1
roxr.b #1,%d0
dbra.w %d2,0b
rts");

unsigned short symbin16(unsigned short a asm("d1"));
asm(".xdef symbin16
symbin16:
moveq.l #15,%d2
0: add.w %d1,%d1
roxr.w #1,%d0
dbra.w %d2,0b
rts");

unsigned long symbin32(unsigned long a asm("d1"));
asm(".xdef symbin32
symbin32:
moveq.l #31,%d2
0: add.l %d1,%d1
roxr.l #1,%d0
dbra.w %d2,0b
rts");
Membre de l'équipe de TIGCC: http://tigcc.ticalc.org
Mainteneur du portage Linux/Unix de TIGCC: http://tigcc.ticalc.org/linux/
Membre de l'équipe de CalcForge: http://www.calcforge.org:70/

Participez à la reprise de Ti-Gen!
    
./Post n°6   Marquer comme non lu.
Xantares Ecrit le: Dimanche 16 juillet 2006 à 08:52 Déconnecté(e)    Voir le profil de Xantares Envoyer un email à Xantares Envoyer un message privé à Xantares  

effectivement ca a l'air beaucoup plus rapide

merci !


int symbin(int a,int n)
{
  int s=0;
  while(n>0)
  {
      n--;
      s+=(a&1)*(1<<n);
      a>>=1;
    }
  return s;
}


ou en basic :


symbin(a,n)
func
local s
0->s
while n>0
n-1->n
(a and 1)*shift(1,n)+s->s
shift(a,-1)->a
endwhile
s
endfunc
    
./Post n°7   Marquer comme non lu.
Kevin Kofler Ecrit le: Dimanche 16 juillet 2006 à 13:00 Déconnecté(e)    Voir le profil de Kevin Kofler Envoyer un email à Kevin Kofler Visiter le site WEB de Kevin Kofler Envoyer un message privé à Kevin Kofler  


Et mon ASM, tu l'as essayé? Je peux aussi essayer de faire une version avec un n variable si tu en as besoin (faudra rajouter un shift).
Membre de l'équipe de TIGCC: http://tigcc.ticalc.org
Mainteneur du portage Linux/Unix de TIGCC: http://tigcc.ticalc.org/linux/
Membre de l'équipe de CalcForge: http://www.calcforge.org:70/

Participez à la reprise de Ti-Gen!
    
./Post n°8   Marquer comme non lu.
Xantares Ecrit le: Dimanche 16 juillet 2006 à 13:49 Déconnecté(e)    Voir le profil de Xantares Envoyer un email à Xantares Envoyer un message privé à Xantares  

kevin k>

non desolé toutes ces lignes obscures en asm me font très peur

la fonction en c devrait aller suffisamment vite pour ce que je veux faire

c'était pas la peine de te donner tout ce mal ! mais merci pour tes conseils
    
./Post n°9   Marquer comme non lu.
Kevin Kofler Ecrit le: Dimanche 16 juillet 2006 à 14:48 Déconnecté(e)    Voir le profil de Kevin Kofler Envoyer un email à Kevin Kofler Visiter le site WEB de Kevin Kofler Envoyer un message privé à Kevin Kofler  


Mais le code ASM est vraiment plus efficace. Plus petit et plus rapide.

Pour un n variable:
unsigned short symbin(unsigned short a asm("d1"), unsigned short n asm("d2"));
asm(".xdef symbin
symbin:
clr.w %d0
0: lsr.w #1,%d1
addx.w %d0,%d0
subq.w #1,%d2
bne.s 0b
rts");
Total: 2 minutes et demie de travail. :)
(Même pas besoin de rajouter un shift en fait, il suffit de faire passer le dépilage et l'empilage par la droite plutôt que par la gauche, et de rajouter un clr pour %d0 pour éviter d'avoir des bits non-initialisés.)
-Edité le Dimanche 16 juillet 2006 à 14:49 par Kevin Kofler-
Membre de l'équipe de TIGCC: http://tigcc.ticalc.org
Mainteneur du portage Linux/Unix de TIGCC: http://tigcc.ticalc.org/linux/
Membre de l'équipe de CalcForge: http://www.calcforge.org:70/

Participez à la reprise de Ti-Gen!
    
./Post n°10   Marquer comme non lu.
Xantares Ecrit le: Lundi 17 juillet 2006 à 08:19 Déconnecté(e)    Voir le profil de Xantares Envoyer un email à Xantares Envoyer un message privé à Xantares  

> on gagnerait combien en vitesse à ton avis en asm sur cette fonction ? 40% ? plus ?
    
./Post n°11   Marquer comme non lu.
Kevin Kofler Ecrit le: Lundi 17 juillet 2006 à 19:15 Déconnecté(e)    Voir le profil de Kevin Kofler Envoyer un email à Kevin Kofler Visiter le site WEB de Kevin Kofler Envoyer un message privé à Kevin Kofler  


Je ne sais pas, faudrait mesurer.

Sinon, un peu plus rapide, mais 2 octets de plus:
unsigned short symbin(unsigned short a asm("d1"), unsigned short n asm("d2"));
asm(".xdef symbin
symbin:
clr.w %d0
subq.w #1,%d2
0: lsr.w #1,%d1
addx.w %d0,%d0
dbra.w %d2,0b
rts");
Membre de l'équipe de TIGCC: http://tigcc.ticalc.org
Mainteneur du portage Linux/Unix de TIGCC: http://tigcc.ticalc.org/linux/
Membre de l'équipe de CalcForge: http://www.calcforge.org:70/

Participez à la reprise de Ti-Gen!
    
./Post n°12   Marquer comme non lu.
240-185 Ecrit le: Mardi 18 juillet 2006 à 11:09 Déconnecté(e)    Voir le profil de 240-185 Envoyer un email à 240-185 Envoyer un message privé à 240-185  

A quoi ca sert de lui donner un code ASM s'il ne comprend pas ce que ca fait ???
Tel un automate, le dinosaure noir s'avance vers le chef des Chomp et dit : "euh..."
    
./Post n°13   Marquer comme non lu.
LionelA Ecrit le: Mardi 18 juillet 2006 à 11:54 Déconnecté(e)    Voir le profil de LionelA Envoyer un email à LionelA Visiter le site WEB de LionelA Envoyer un message privé à LionelA  


A ce qu'il essaye de le comprendre peut etre ? (sinon ca sera toujours bien plus lent qu'avec la table qui ne coute que 256 octets, meme en C)
Auteur de Mode7 Engine pour ti68k
Auteur de F-ZERO for TI68k
Membre de Orage Studio
Mon site perso : http://www.tigen.org/lionela/
Le gite de mes parents à coté de Narbonne :
http://chaletdenis.free.fr/
    
./Post n°14   Marquer comme non lu.
Kevin Kofler Ecrit le: Mardi 18 juillet 2006 à 11:55 Déconnecté(e)    Voir le profil de Kevin Kofler Envoyer un email à Kevin Kofler Visiter le site WEB de Kevin Kofler Envoyer un message privé à Kevin Kofler  


240-185 :
A quoi ca sert de lui donner un code ASM s'il ne comprend pas ce que ca fait ???

À ce qu'il l'utilise? Pourquoi utiliser un code inefficace sur prétexte que c'est ce qu'on comprend?
Membre de l'équipe de TIGCC: http://tigcc.ticalc.org
Mainteneur du portage Linux/Unix de TIGCC: http://tigcc.ticalc.org/linux/
Membre de l'équipe de CalcForge: http://www.calcforge.org:70/

Participez à la reprise de Ti-Gen!
    
./Post n°15   Marquer comme non lu.
Onur Ecrit le: Mardi 18 juillet 2006 à 19:36 Déconnecté(e)    Voir le profil de Onur Envoyer un email à Onur Visiter le site WEB de Onur Envoyer un message privé à Onur  


LionelA :
A ce qu'il essaye de le comprendre peut etre ? (sinon ca sera toujours bien plus lent qu'avec la table qui ne coute que 256 octets, meme en C)


chaque octet est important :/
Je ne veux pas faire quelque chose de bien, je cherche l'excellence:ETP Studio...


et autres projets à finir avant 2010
    
./Post n°16   Marquer comme non lu.
LionelA Ecrit le: Mardi 18 juillet 2006 à 21:36 Déconnecté(e)    Voir le profil de LionelA Envoyer un email à LionelA Visiter le site WEB de LionelA Envoyer un message privé à LionelA  


je te le fais pas dire :p
Auteur de Mode7 Engine pour ti68k
Auteur de F-ZERO for TI68k
Membre de Orage Studio
Mon site perso : http://www.tigen.org/lionela/
Le gite de mes parents à coté de Narbonne :
http://chaletdenis.free.fr/
    
./Post n°17   Marquer comme non lu.
Xantares Ecrit le: Lundi 24 juillet 2006 à 11:53 Déconnecté(e)    Voir le profil de Xantares Envoyer un email à Xantares Envoyer un message privé à Xantares  

oui mais pour calculer la table il te faudra quand meme l'algorithme pour la remplir
    
./Post n°18   Marquer comme non lu.
LionelA Ecrit le: Lundi 24 juillet 2006 à 12:53 Déconnecté(e)    Voir le profil de LionelA Envoyer un email à LionelA Visiter le site WEB de LionelA Envoyer un message privé à LionelA  


ben tu le fait qu'une seule fois sur pc :)
Auteur de Mode7 Engine pour ti68k
Auteur de F-ZERO for TI68k
Membre de Orage Studio
Mon site perso : http://www.tigen.org/lionela/
Le gite de mes parents à coté de Narbonne :
http://chaletdenis.free.fr/
    
  :: Index » Forum TiZ80 » Algorithmie et optimisation » algorithme pour symetriser un nombre (18 réponse(s))
Pages : 1/1     « [1] » »|

.Répondre à ce sujet
Les boutons de code
[B]old[I]talic[U]nderline[S]trikethrough[L]ine Flip Hori[Z]ontallyFlip [V]erticallySha[D]ow[G]low[S]poilerCode [G][C]ite
Bullet [L]istList Item [K] Link [H][E]mail[P]icture SmileysHelp
Couleurs :
Saisissez votre message
Activer les smileys
     

Forum de Ti-Gen v3.0 Copyright ©2004 by Geoffrey ANNEHEIM
Webmaster: Kevin KOFLER, Content Admins: list, Server Admins: Tyler CASSIDY and Kevin KOFLER, DNS Admin: squalyl
Page générée en 56ms avec 18 requetes