Forum de Ti-Gen.org, le site francophone des TI

Bienvenue Invité ! Se connecter Mes sujets	Administrer
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

Membre: Habitué

Messages: 63

Membre n°875

Inscrit le 09 juin 2005

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

Modérateur général

Groupe: Staff de Ti-Gen

Groupe: Orage Studio

Messages: 947

Membre n°206

Inscrit le 19 avril 2004

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

Fondateur

Groupe: Staff de Ti-Gen

Groupe: Orage Studio

Messages: 4256

Membre n°3

Inscrit le 29 janvier 2004

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

Membre: Habitué

Messages: 63

Membre n°875

Inscrit le 09 juin 2005

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

Membre: Magister

Messages: 302

Membre n°896

Inscrit le 25 juin 2005

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

Administrateur

Groupe: Staff de Ti-Gen

Messages: 4814

Membre n°40

Inscrit le 08 février 2004

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

Membre: Habitué

Messages: 63

Membre n°875

Inscrit le 09 juin 2005

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

Administrateur

Groupe: Staff de Ti-Gen

Messages: 4814

Membre n°40

Inscrit le 08 février 2004

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

./Post n°8 Marquer comme non lu.

Xantares

Ecrit le: Dimanche 16 juillet 2006 à 13:49

Membre: Habitué

Messages: 63

Membre n°875

Inscrit le 09 juin 2005

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

Administrateur

Groupe: Staff de Ti-Gen

Messages: 4814

Membre n°40

Inscrit le 08 février 2004

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-

./Post n°10 Marquer comme non lu.

Xantares

Ecrit le: Lundi 17 juillet 2006 à 08:19

Membre: Habitué

Messages: 63

Membre n°875

Inscrit le 09 juin 2005

> 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

Administrateur

Groupe: Staff de Ti-Gen

Messages: 4814

Membre n°40

Inscrit le 08 février 2004

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");

./Post n°12 Marquer comme non lu.

240-185

Ecrit le: Mardi 18 juillet 2006 à 11:09

Membre: Habitué

Messages: 68

Membre n°1256

Inscrit le 15 mars 2006

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

Modérateur général

Groupe: Staff de Ti-Gen

Groupe: Orage Studio

Messages: 947

Membre n°206

Inscrit le 19 avril 2004

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)

./Post n°14 Marquer comme non lu.

Kevin Kofler

Ecrit le: Mardi 18 juillet 2006 à 11:55

Administrateur

Groupe: Staff de Ti-Gen

Messages: 4814

Membre n°40

Inscrit le 08 février 2004

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?

./Post n°15 Marquer comme non lu.

Onur

Ecrit le: Mardi 18 juillet 2006 à 19:36

Membre: Maître Ultime

Groupe: Orage Studio

Messages: 1604

Membre n°341

Inscrit le 02 juillet 2004

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