Le jeu de la programmation (Canard++)

**Daeke** · 27/08/2007, 20h23

Envoyé par DaP

Je ne comprends pas ton code, il marche ? D'après ce que je comprends, si num est nul, on ne passe pas dans la boucle et verif() retourne 1, sinon on décale jusqu'à ce que le lsb soit égal à 1, et verif() retourne 0.

Non il ne marche pas (du tout ;p) mais c'était pour expliquer un peu mieux ma pensée (qui était en gros : utiliser une boucle et des décalages).

**ducon** · 27/08/2007, 20h36

Et comment crois-tu que le processeur compare eax et ebx ? Avec un test pardi.
Pour le maximum, on est coincé, je dirais même mathématiquement, à utiliser quelque part un test.

**DaP** · 27/08/2007, 22h34

Je n'ai pas été assez explicite, je parlais d'éviter les branchements. CMP fait juste une soustraction sans sauvegarder le résultat et positionne les flags de statut. Voilà un exemple qui n'utilise aucune instruction de test (SETA copie !CF dans CL) :

Code:

xor ecx, ecx
mov eax, 10       ; a
mov ebx, 20       ; b

cmp eax, ebx
seta cl           ; ecx = (a > b) ?  1:0
neg ecx           ;                 FF:0

sub eax, ebx
and ecx, eax      ;                a-b:0

add ecx, ebx      ;                  a:b

L'équivalent en C :

Code:

int a, b, max;
max = (-(a > b) & (a-b)) + b;

Tu relances ?

**Tramb** · 27/08/2007, 22h57

Bon les setcc à la place des branchements c'est un peu tricher quand même pour ce genre de truc mais bon ;-)

Si on veut le faire avec des opcodes plus vieillot, la valeur absolue peut se calculer comme ça (idiomatique, j'ai rien inventé):

Code:

cdq
xor eax, edx
sub eax, edx

Question suivante alors?

Mmmh... Allez...
Comment faire une division par 3... sans division?

Edit : Entière la division hein.

**ducon** · 28/08/2007, 06h38

DaP, d’après toi, a>b est un test, ou pas ? :mrgreen:
Il suffit de voir la définition de la valeur absolue pour voir qu’on est coincé et qu’on devra faire appel à un test, de gré ou de force, à un moment ou à un autre.

Pour obtenir le reste, on peut additionner tous les chiffres, comme pour la preuve par neuf.

**DaP** · 28/08/2007, 17h08

Solution bourrine (entrée dans EAX, sortie dans EDX) :

Code:

mov edx, 0AAAAAAABh
mul edx
shr edx, 1

Envoyé par ducon

DaP, d’après toi, a>b est un test, ou pas ? :mrgreen:
Il suffit de voir la définition de la valeur absolue pour voir qu’on est coincé et qu’on devra faire appel à un test, de gré ou de force, à un moment ou à un autre.

Bien sûr, mais c'était un peu évident que je parlais de ne pas faire de branchement pour que le programme ne suive qu'un chemin quoi qu'il arrive. Pour le (a > b), ça dépend de ce que le compilateur en fait.

**Tramb** · 28/08/2007, 21h07

Envoyé par DaP

Si tu as une meilleure solution je suis preneur.

Bah meilleure solution, non, c'est un truc clairement convolué mais comme le disait ducon:

Code:

max(a, b) = ((a+b) + abs(b-a))/2
min(a, b) = ((a+b) - abs(b-a))/2

et tu peux calculer le abs avec le

Code:

cdq
xor eax, edx
sub eax, edx

Bon c'est tordu hein... mais sauf erreur ça tourne dès le 386

(et bien joué pour le div by 3, pratique pour trouver un nombre de triangles à partir du nombre de vertex)
A toi de balancer des questions DaP!

**DaP** · 28/08/2007, 21h20

Ben je comptais sortir ça mais je n'arrive pas à le compiler, et j'ai pas trop envie d'essayer de comprendre non plus.

Alors une connue : comment interchanger deux valeurs sans passer par une variable intermédiaire ?

**Tramb** · 28/08/2007, 21h25

Envoyé par DaP

Alors une connue : comment interchanger deux valeurs sans passer par une variable intermédiaire ?

Bon je réponds pas sur celle là, quelqu'un doit bien connaître ça dans le coin!

**Ghost Line** · 28/08/2007, 22h56

Je vois bien un truc du genre :

a = valeur1
b = valeur2

a+b=b
b-a=a
b-a=b

En algo complet

edit : ça me fait penser aux Tours de Hanoï ...

edit 2 : je suis ARL moi, pas Dev boudiou ^^

**DaP** · 28/08/2007, 23h17

Ca marche, je connaissais pas.

On peut aussi faire avec des XOR :

Code:

int a = 5, b = 2;
   
a ^= b;
b ^= a;
a ^= b;

A toi !

**Ghost Line** · 29/08/2007, 05h22

Envoyé par DaP

Ca marche, je connaissais pas.

On peut aussi faire avec des XOR :

Code:

int a = 5, b = 2;
   
a ^= b;
b ^= a;
a ^= b;

A toi !

Houla, je passe mon tour ! je suis juste un gros curieux en prog, je n'ai pas de onnaissances particulières ! je suivrais le topic avec plaisir, mais je ne me sens pas capable de créer une énigme, dsl

**ducon** · 29/08/2007, 07h39

Code:

int zongo(int n)
{
  {  
    int result = n,i;
    for(i=2;i*i <= n;i++)
    {
      if (n % i == 0) result -= result / i;
        while (n % i == 0) n /= i;
    }
    if (n > 1)
      result -= result / n;
    return result;
  }
}

**Tramb** · 29/08/2007, 11h13

Envoyé par ducon

Code:

int zongo(int n)
{
  {  
    int result = n,i;
    for(i=2;i*i <= n;i++)
    {
      if (n % i == 0) result -= result / i;
        while (n % i == 0) n /= i;
    }
    if (n > 1)
      result -= result / n;
    return result;
  }
}

J'ai beau relire ce truc, j'en ai aucune idée

**ducon** · 29/08/2007, 11h22

C’est un truc de matheux.

**Tramb** · 29/08/2007, 12h42

Envoyé par ducon

C’est un truc de matheux.

Si n est premier, ça renvoie n-1.
En fait ça pourrait presque être un truc qui renvoie le plus gros facteur mais non.
J'arrive pas à capter ce que ça fait.
Un p'tit indice?

**ducon** · 29/08/2007, 12h44

Envoyé par Tramb

Si n est premier, ça renvoie n-1.

Exact.
Tu connais beaucoup de fonctions qui renvoient n−1 si n est premier ?

J'arrive pas à capter ce que ça fait.
Un p'tit indice?

Et si n est composé du produit de deux nombres premiers ? Ou alors d’une puissance d’un seul nombre premier ?

**elpaulo** · 29/08/2007, 12h56

putain les gars arretez tout quoi

**ducon** · 29/08/2007, 12h59

T’es un geek, toi ?

**elpaulo** · 29/08/2007, 13h01

quand je vois ce topic, je me dis que finalement non

**Tramb** · 29/08/2007, 13h13

Envoyé par ducon

Exact.
Tu connais beaucoup de fonctions qui renvoient n−1 si n est premier ?
Et si n est composé du produit de deux nombres premiers ? Ou alors d’une puissance d’un seul nombre premier ?

Mmmh! Ca a l'air de faire ça:
Soit n = produit sur i des ai^pi (ai, premiers)
zongo(n) = produit sur i des (ai-1)*ai^(pi-1)

Ah. Ca a l'air d'être l'indicateur d'Euler en fait après un peu de recherche sur le net, le nombre de nombres inférieurs premiers avec n!

(Disclaimer : on va dire que l'arithmétique est pas ma compétence la plus forte en maths

)

**ducon** · 29/08/2007, 13h16

C’est ça.
Ça s’appelle l’indicatrice d’Euler, et c’est noté ϕ(n).

**Tramb** · 29/08/2007, 13h17

Envoyé par ducon

C’est ça.
Ça s’appelle l’indicatrice d’Euler, et c’est noté ϕ(n).

Ah ben je venais de voir ça

(Cool on peut copier des caractères chelous sur le forum : ط بقناة العربية يقدم على مدار الساعة ال)

**ducon** · 29/08/2007, 13h28

Envoyé par Tramb

(Cool on peut copier des caractères chelous sur le forum : ط بقناة العربية يقدم على مدار الساعة ال)

Ce qui veut dire ?

**elpaulo** · 29/08/2007, 13h54

que tu ne comprend pas les caracteres chelous :smile:

**Tramb** · 29/08/2007, 14h36

Envoyé par elpaulo

que tu ne comprend pas les caracteres chelous :smile:

...et que j'ai copié du texte de google sans savoir ce que c'était.

**ducon** · 29/08/2007, 17h42

En fait, cette fonction compte le nombre de nombres plus petits que n qui sont premiers avec n, c’est-à-dire sans facteur commun avec n.

**DaP** · 29/08/2007, 18h18

Et qui relance dans tout ça ?

**ducon** · 29/08/2007, 18h24

Je peux vous trouver une autre fonction mathématique, si vous voulez.

**Phatcobra** · 29/08/2007, 18h27

Envoyé par Pen²

à fond, c'est mon idole!
j'ai même des posters de lui dans ma chambre

C'est à cause de gars comme toi (les geeks) que les filles ont "peur" des mecs comme moi (les gamers)

Discussion: Le jeu de la programmation (Canard++)

Outils de la discussion

Règles de messages