Concours absolu - Page 1

Salut,
Un petit jeu pour ceux qui aiment se remuer les méninges : écrire une fonction qui rend la valeur absolue d’un entier 32 bits sans utiliser aucun saut.
À vous de jouer !

(On a droit à une table ? )

function abs(x) {
x = x * x
return sqrt(x)
}

sérieusement

Using assembly language, it is possible to take the absolute value of a register in just three instructions (example shown for a 32-bit register on an x86 architecture, Intel syntax):

http://www.google.fr/#hl=fr&q=%22absolute+value%22+algorithm&meta=&fp=1&cad=b

http://www.experiencefestival.com/a/Absolute_value_-_Algorithms/id/604651

cdq
xor eax, edx
sub eax, edx


(qu'est ce que c'est que ce site )

Pen^2 (./2) :
(On a droit à une table ? )

Oui, de 4 gigas (cf le topic "enfin une extension mémoire réalisable rapidement" )

En 68k, ça donne:
long absl(long n asm("d0"));

absl:
tst.l %d0
slt.b %d1
ext.w %d1
ext.l %d1
eor.l %d1,%d0
sub.l %d1,%d0
rts

merci pour la transcription

[code] move.l d0, d1
rol.l #1, d1
and.l #1, d1
neg.l d1
eor.l d1, d0
sub.l d1, d0[/code]

Variation perso. Mais je sais pas si ça prend moins de cycles que la version de Kevin.

Ta version prend plus de place en tout cas!

Oui, c'est vrai. On peut faire :

[code] moveq.l #1, d2
move.l d0, d1
rol.l d2, d1
and.l d2, d1
neg.l d1
eor.l d1, d0
sub.l d1, d0[/code]

mais ça prend 2 octets de plus que ta version.

Il est possible de faire tenir ça sur 10 octets (sans compter le rts, et en utilisant une autre démarche que celles que vous avez proposées)
Indice : utiliser le bit de retenue « x »

Bon, j'ai pas trouvé l'astuce avec le flag X, mais j'y arrive aussi en 10 octets :

move.l  d0, d1
moveq.l #31, d2
asr.l  d2, d1
eor.l  d1, d0
sub.l  d1, d0

(par contre, en nombre de cycles, ça risque de faire mal )

Excellent !
La solution que j’ai (trouvée dans un papier de Henry Massalin) fait la même taille mais prend moins de cycles :

move.l  d0, d1
add.l   d1, d1
subx.l  d1, d1
eor.l   d1, d0
sub.l   d1, d0

Ah oui, pas bête le coup du add + subx

C'est intelligent Mais en réalité on fait un test suivi d'un saut car c'est plus rapide et plus petit, non ?

Sur 68000 ça vaudrait le coup de comparer les deux solutions, c'est pas sûr qu'on soit gagnant en effet.

Mais sur les processeurs plus évolués avec un long pipeline, vaut mieux en général éviter les sauts si on peut faire autrement : un saut peut faire perdre beaucoup de cycles, le temps que le pipeline soit rechargé.

tst.l d0
bpl.s Positif
neg.l d0

Positif:

6 octets avec un saut

Oui, mais c'est facile, ça.

Naturellement, ce n'était qu'un élément de comparaison hein.

ça fait super longtemps que j'ai pas touché au 68000 donc j'ai un doute sur le format des entiers signés 32bits mais si c'est le msb qui sert pour stocker le signe, il suffit de le masquer, non ? (à moins que le valeurs négatives soient en complément à deux)

oui, c'est le msb, et les valeurs négatives sont en complément à deux

vince > je te conseille Zguide (il est toujours en ligne http://membres.lycos.fr/zorglop/ti92/zguide/)

nan

Si

Je déconseille fortement le Zguide, c'est vraiment catastrophique. (Je me rappelle toujours quand j'ai essayé d'apprendre avec cette horreur il y a quelques années, c'était totalement impossible.)

Ben j'ai appris avec, entre autres et comme d'autres (Pen2 ?). Il était bordélique mais c'etait le seul document en français avec la traduction d'un cours américain assez pointu. Les deux se complétaient.

Oué, nous n'étions pas au courant que c'était impossible, alors nous avons appris avec quand même
Zorglop n'y est pour rien si tu es mauvais

Je cherchais une manière de le dire, puis j'ai laissé tomber

'service