[solved] add trick 2

Index > Main > [solved] add trick 2

Author

Thread

Picnic

Joined: 05 May 2007
Posts: 1389
Location: Piraeus, Greece

Picnic 22 Jul 2011, 15:13

Hi team,

I want to add 2 signed integers, reverse sign if result > MAX or result < MIN and continue addition.

Example with MAX = 99 adding 20 to 90 outputs -88 [ 91,92...99, (reverse) -98,-97...-88 ]

Code:

; examples:
; MAX=99, MIN=-MAX

; _add(90, 20)   =  -88
; _add(90, -20)  =  70
; _add(-90, 20)  =  -70
; _add(-90, -20) =  88

Any small asm algo appreciated.

Last edited by Picnic on 23 Jul 2011, 14:29; edited 1 time in total

22 Jul 2011, 15:13

r22

Joined: 27 Dec 2004
Posts: 805

r22 22 Jul 2011, 16:17

Code:

;eax = X ; 70
;ebx = Y ; 20
;ecx = MIN ; -99
;edx = MAX ; 99

ADD eax, ebx ; x = x + y ; 120
MOV ebx, 0 ; y = 0
CMP eax, edx ; x > MAX ; 120 > 99
CMOVG ebx, edx ; ? y = MAX ; 99
CMP eax, ecx ; x < MIN ; 120 < -99
CMOVL ebx, ecx ; ? y = MIN ;
SUB eax, ebx ; x = x - y ; 120 - 99 = 11
SUB eax, ebx ; x = x - y ; 11 - 99 = -88

Looks like it could work ...

22 Jul 2011, 16:17

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 22 Jul 2011, 18:18

Picnic wrote:

Hi team,

I want to add 2 signed integers, reverse sign if result > MAX or result < MIN and continue addition.

Example with MAX = 99 adding 20 to 90 outputs -88 [ 91,92...99, (reverse) -98,-97...-88 ]

Picnic, I'm not sure if I understood the conditions of your programming competition.

Here some questions arise:

can the MAX and MIN be arbitrarily chosen, or, oppositely, always is MIN = -MAX?
are you sure that "reversion" of the sign will make -98 from 100 (shouldn't be here -99)?

I assume that we can describe it as follows: for any numbers MIN ≤ a, b ≤ MAX we have defined operation of the modified addition (let's denote this operator as Θ), so sum a Θ b is in fact a+b modulo (MAX - MIN) translated by some vector:

a Θ b = (a+b - MIN) mod (MAX - MIN) + MIN

Smile

22 Jul 2011, 18:18

edfed

Joined: 20 Feb 2006
Posts: 4330
Location: Now

edfed 22 Jul 2011, 18:25

Code:

add_n_neg:
.min = -99
.max = -.min
add eax,ebx
cmp eax,.min
jl .neg
cmp  eax,.max
jg .neg
ret
.neg:
neg eax
ret

and then, you just have to preload ebx with the new value to add, call add_n_neg to iterate.

but it would be preferable to do some ping pong action, because if not, a very far to bound addition will lead to an always outside bound result.

if you do some ping pong action, using max or min as a symetry axis, you will always decrease the difference between the value and the bounds, but substracting the bound from the value, in order to reflect the position inside.

the same thing is true if for example, the number to add to X is 45, X is originally 20, and max is 21.
what happens if min = -20? the result of the addition will be 65, greater than 21.
then, negation, and as a result, we have -65, that is lower than -20 (min), and then, another negation is made, and so on.
in the case of the algo of the topic, the value will constantlly oscillate between a value bigger than max, and a value loer than min.

if you do the ping pong algo, instead of negate, you sub min or max.
and if value is greater than max, in our case, it will become 65-21 = 44.
44 is between min and max, then, no more iteration required, the value will be stable.

Last edited by edfed on 22 Jul 2011, 18:42; edited 1 time in total

22 Jul 2011, 18:25

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 22 Jul 2011, 18:37

MHajduk wrote:

I assume that we can describe it as follows: for any numbers MIN ≤ a, b < MAX we have defined operation of the modified addition (let's denote this operator as Θ), so sum a Θ b is in fact a+b modulo (MAX - MIN) translated by some vector:

a Θ b = (a+b - MIN) mod (MAX - MIN) + MIN

If this is exactly what we want to do then we have a such code:

Code:

; Input:
;       eax := a
;       ebx := b
;
; Output:
; edx := (a+b - MIN) mod (MAX - MIN) + MIN
;
xor        edx, edx
add eax, ebx
sub eax, MIN
mov ecx, (MAX - MIN)
idiv        ecx
add      edx, MIN

22 Jul 2011, 18:37

LocoDelAssembly
Your code has a bug

Joined: 06 May 2005
Posts: 4624
Location: Argentina

LocoDelAssembly 22 Jul 2011, 19:42

This is just a remake of r22's code:

Code:

; Input: EAX = [-MAX..MAX]; EDX = [-MAX..MAX]; Output: EAX
        add   eax, edx

        lea   ecx, [eax - 2*MAX]
        cmp   eax, MAX

        cmovg eax, ecx

        lea   ecx, [eax + 2*MAX]
        cmp   eax, -MAX

        cmovl eax, ecx

Worked with Picnic's examples, but haven't checked any further. Not sure if this could be adapted to be as flexible as MHajduk's code, I'm more dumb than usual today Confused

[edit]This version although it has one more instruction it may be faster due to the removal of some dependencies:

Code:

; Input: EAX = [-MAX..MAX]; EDX = [-MAX..MAX]; Output: EAX
        add   eax, edx

        lea   ecx, [eax - 2*MAX]
        mov   edx, eax
        cmp   eax, MAX

        cmovg eax, ecx
        lea   ecx, [edx + 2*MAX]
        cmp   edx, -MAX

        cmovl eax, ecx

Last edited by LocoDelAssembly on 22 Jul 2011, 20:03; edited 1 time in total

22 Jul 2011, 19:42

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 22 Jul 2011, 19:55

Picnic wrote:

Code:

; examples:
; MAX=99, MIN=-MAX

; _add(90, 20)   =  -88
; _add(90, -20)  =  70
; _add(-90, 20)  =  -70
; _add(-90, -20) =  88

Let's check my formula

a Θ b = (a + b - MIN) mod (MAX - MIN) + MIN

arithmetically:

_add(90, 20) = 90 Θ 20 =
= (90 + 20 - MIN) mod (MAX - MIN) + MIN =
= (90 + 20 - (-99)) mod (99 - (-99)) + (-99) =
= (110 + 99) mod (99 + 99) - 99 =
= 209 mod 198 - 99 =
= 11 - 99 = -88

Analogously we have:

_add(90, -20) = 90 Θ - 20 =
= (90 - 20 + 99) mod 198 - 99 =
= (70 + 99) mod 198 - 99 =
169 mod 198 - 99 =
169 - 99 = 70

_add(-90, 20) = -90 Θ 20 =
= (-90 + 20 + 99) mod 198 - 99 =
= (-70 + 99) mod 198 - 99 =
= 29 mod 198 - 99 =
= 29 - 99 = -70

_add(-90, -20) = -90 Θ - 20 =
= (-90 + (-20) + 99) mod 198 - 99 =
= (-110 + 99) mod 198 - 99 =
= (-11) mod 198 - 99 =
= 187 - 99 = 88

So, the main conditions of the exercise are met. Smile

22 Jul 2011, 19:55

Picnic

Joined: 05 May 2007
Posts: 1389
Location: Piraeus, Greece

Picnic 22 Jul 2011, 20:10

edfed, MIN = -MAX always, and the number to add is always < MAX and > MIN -sorry i did not mention that- but since result can exceed limits therefore this adjust, yes a ping pong like adjust.

MHajduk, i get 92 not 88 using your code snippet with _add(-90, -20)
I still have to test the formula.

LocoDelAssembly, i think your code gives me the results i need!

22 Jul 2011, 20:10

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 22 Jul 2011, 20:51

Picnic wrote:

MHajduk, i get 92 not 88 using your code snippet with _add(-90, -20)
I still have to test the formula.

Because 'idiv' is shitty and gives us also negative rests.

22 Jul 2011, 20:51

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 22 Jul 2011, 21:17

Some workaround here, but I don't like it:

Code:

; Input: 
;       eax := a 
;       ebx := b 
; 
; Output: 
;       edx := (a+b - MIN) mod (MAX - MIN) + MIN  
;
add     eax, ebx  
sub     eax, MIN  
mov     ecx, (MAX - MIN) 
cdq  
idiv    ecx
test       edx, edx
jns .x
add       edx, (MAX - MIN)

.x:
     add     edx, MIN

22 Jul 2011, 21:17

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 22 Jul 2011, 22:21

I see another possibility. We can adjust the sum before 'div' to get always non-negative values. I assume that MAX ≥ 0 and MAX > MIN.

For all integer k we have

(y + k*x) mod x = y mod x

so, we can add a multiply of (MAX - MIN) before division, and for small MIN and MAX this code should work properly:

Code:

; Input: 
;       eax := a 
;       ebx := b 
; 
; Output: 
;       edx := (a+b - MIN) mod (MAX - MIN) + MIN  
; 
xor     edx, edx  
add     eax, ebx
add    eax, (MAX - MIN) - MIN 
mov     ecx, (MAX - MIN)
div      ecx
add     edx, MIN

Sorry if I f****d something up - I'm so tired now. Wink

22 Jul 2011, 22:21

edfed

Joined: 20 Feb 2006
Posts: 4330
Location: Now

edfed 22 Jul 2011, 23:09

xor edx,edx
mov ecx,max-min
lea eax,[eax+ebx+(max-min)-min]
div ecx
lea eax,[edx+min]

22 Jul 2011, 23:09

Picnic

Joined: 05 May 2007
Posts: 1389
Location: Piraeus, Greece

Picnic 23 Jul 2011, 14:29

Thanks all for the time and effort, quite enlightening posts.
edfed it loops between min & max sweet!

23 Jul 2011, 14:29

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 23 Jul 2011, 18:20

Picnic, I'm glad because of your comment. Your excitation makes me sure that my method with "shifted" modulo slightly modified by edfed (really smart use of the 'lea' instruction) is correct. So, my yesterday's doubts were completely needless, cool. Razz

Just for the sake of completness, if anybody cares about it, I would like to add some considerations on the theme of adjustment before division.

Some theory

We want to adjust our sum a + b - MIN before division in a such "transparent" way that always dividend will be positive. We assume that MAX > MIN (it's quite natural assumption). Let's consider two complementary cases:

MIN >= 0

In this case expression

a + b - MIN

will be always greater or equal to 0, because "in the worst case" for a = MIN and b = MIN we will have

a + b - MIN = MIN + MIN - MIN = MIN >= 0
MIN < 0

Now expression

a + b - MIN

can be (for some values of a and b) negative. We know that operation modulo is "transparent" (or, in other words, "insensitive") for the addition of the integer multiply of divisor to the argument:

(y + k*x) mod x = y mod x

Hence we get that

(a + b + k*(MAX - MIN) - MIN) mod (MAX - MIN) = (a + b - MIN) mod (MAX - MIN)

For every given pair of values MIN and MAX we want to find corresponding value of k that

a + b + k*(MAX - MIN) - MIN >= 0

Let's consider "the worst case", i.e. when a = b = MIN:

MIN + MIN + k*(MAX - MIN) - MIN >= 0

we have

MIN + k*(MAX - MIN) >= 0

and

k*(MAX - MIN) >= -MIN

finally

k >= -MIN / (MAX - MIN)

Note, that here everything is correct because always (MAX - MIN) > 0 from assumption.

We want k to be integer. It is enough to take

k = [-MIN / (MAX - MIN)] + 1

Where [x] means the "floor" function (called also "entier").

Code snippets modification

Let's come back to the code snippets. Lines

Code:

add     eax, (MAX - MIN) - MIN ; mine

lea eax,[eax+ebx+(max-min)-min] ; edfed's

should look like that:

Code:

add     eax, k*(MAX - MIN) - MIN       ; mine

lea eax,[eax+ebx+k*(max-min)-min] ; edfed's

where

k = [-MIN / (MAX - MIN)] + 1 for MIN < 0
k = 0 for MIN >= 0

The change isn't big yet crucial when we would be talking about arbitrary MIN and MAX. Of course, in our special case when MAX = -MIN we have

k = [-MIN / (MAX - MIN)] + 1 = [-MIN / (-MIN - MIN)] + 1 = [-MIN / (-2MIN)] + 1 = [1/2] + 1 = 0 + 1 = 1

so, in this special case, both lines of code snippets will be the same as original ones. Smile

23 Jul 2011, 18:20

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum