hi!


This one will popup a messagebox. The magic jump is the jb if you change that to ja it will not popup a messagebox. :)

Yup, but it will always popup, not important if both values are the same, of different.

Cu, Jens
Posted on 2002-03-25 12:56:49 by Jens Duttke
stryker,
Sorry, but I don't get what is your code about.

Let me explain by example.
For example You have array of values:

values dd 123,123,123, 123,123,87, 123,123,123

in this case you need to return 5
with

values dd 65,123,123, 123,123,123 123,123,123

you need to return 0

You allowed to use add, mov, jcc as many times as you want
and cmp or sub no more than twice.

Though you know that one different value is less than others (that all the same)
you don't know what values are they.
Posted on 2002-03-25 13:00:12 by The Svin
Yeah, I already found a bug :grin:
Posted on 2002-03-25 13:05:19 by stryker
Here's another one for the first problem. There are 3 SUBs in the code but only 2 are executed in every possible control path.. Could be optimized a lot more if more opcodes were allowed..


;1st part [eax] = v1 + v2 + v3 + v3
;2nd part [ecx] = v4 + v5 + v6 + v7
;3rd part [edi] = 4 * v9

mov ebx, v9 ;ebx = v9
mov eax, v1 ;eax = v1
mov ecx, v5 ;ecx = v5
mov edi, ebx ;edi = 1*v9
add eax, v2 ;eax = v1 + v2
add ecx, v6 ;ecx = v5 + v6
add edi, ebx ;edi = 2*v9
add eax, v3 ;eax = v1 + v2 + v3
add ecx, v7 ;ecx = v5 + v6 + v7
add edi, ebx ;edi = 3*v9
add eax, v4 ;eax = v1 + v2 + v3 + v4
mov esi, edi ;esi = 3*v9
add ecx, v8 ;ecx = v5 + v6 + v7 + v8
add edi, ebx ;edi = 4*v9
; 1st = 3rd?
sub eax, edi ;eax = (v1 + v2 + v3 + v4) - 4*v9
jz @in_part2 ;yes-> different one is in 2nd part
;no:
; 2nd = 3rd?
sub ecx, edi
jz @in_part1 ;yes-> different one is in 1st part
;no:
; difference is in part 3 so v9 is different
mov eax, ebx
ret
@in_part2:
sub ecx, esi
mov eax, ecx
ret
@in_part1:
add eax, ebx
ret


Thomas
Posted on 2002-03-25 13:14:52 by Thomas
hi!


cmp or sub no more than twice.


Cool, it's allowed to use sub, now ?!?

Maybe we just need to wait 2 or 3 hours and you will also allow us to use AND, XOR and NOT ;)

Cu, Jens
Posted on 2002-03-25 13:28:01 by Jens Duttke
Cool, it's allowed to use sub, now ?!?

Come on, don't fool me, man :)
You used sub in your very first post without waiting for my permission ;)
Actually there is no favor for sub instead of cmp in second task.
Both opcode used for comparesion and main condition - make no more than two comparesion.

Well done, Thomas, I was wondering, who would first find solution you or Eyin :)
Posted on 2002-03-25 13:41:37 by The Svin
hi!

The Svin :

For such a "problem" i think SUB is much more important than cmp :)
I think it's not possible to do that without SUB (and only 2 CMP's), but i am interested in your solution :)

Ok, here is a solution for the second problem :



mov eax, v1
cmp eax, v2
jne @F
mov ebx, 0
sub ebx, v1

mov eax, ebx
add eax, v3
jnz @3
mov eax, ebx
add eax, v4
jnz @4
mov eax, ebx
add eax, v5
jnz @5
mov eax, ebx
add eax, v6
jnz @6
mov eax, ebx
add eax, v7
jnz @7
mov eax, ebx
add eax, v8
jnz @8
jmp @9

@@:
mov ebx, 0
sub ebx, v9

mov eax, ebx
add eax, v1
jnz @1
jmp @2

@1:
mov eax, 1
ret
@2:
mov eax, 2
ret
@3:
mov eax, 3
ret
@4:
mov eax, 4
ret
@5:
mov eax, 5
ret
@6:
mov eax, 6
ret
@7:
mov eax, 7
ret
@8:
mov eax, 8
ret
@9:
mov eax, 9
ret


Cu, Jens
----
http://www.emucheater.com
http://cyberpad.psxemu.com
Posted on 2002-03-25 13:46:33 by Jens Duttke
but i am interested in your solution

he,he
For me is more important to see how your brains produce interesting code :)

For example Thomas made his own logic, I didn't think of.

But I give you a hint:
If there are 27 values (and just one is different from the others)
you need just 3 cmp to find the different.
Posted on 2002-03-25 14:06:25 by The Svin
This is for the index problem:


.386
.MODEL FLAT, STDCALL
OPTION CASEMAP:NONE

INCLUDE \masm32\include\windows.inc
INCLUDE \masm32\include\kernel32.inc
INCLUDELIB \masm32\lib\kernel32.lib
INCLUDE \masm32\include\user32.inc
INCLUDELIB \masm32\lib\user32.lib
INCLUDE \masm32\include\masm32.inc
INCLUDELIB \masm32\lib\masm32.lib

.DATA

Bfr DB 9 DUP(0)
var DD 2, 2, 2, 2, 4, 2, 2, 2, 2

.CODE

Start:

mov eax, DWORD PTR [var]
add eax, DWORD PTR [var+4]
add eax, DWORD PTR [var+8]
add eax, DWORD PTR [var+12]

mov ecx, DWORD PTR [var+16]
add ecx, DWORD PTR [var+20]
add ecx, DWORD PTR [var+24]
add ecx, DWORD PTR [var+28]

cmp eax, ecx
ja @@FirstPartition
jb @@SecondPartition

mov eax, 8
jmp @@Exit

@@FirstPartition:

mov eax, DWORD PTR [var]
add eax, DWORD PTR [var+4]

mov ecx, DWORD PTR [var+8]
add ecx, DWORD PTR [var+12]

cmp eax, ecx
jb @@Check2and3

mov eax, DWORD PTR [var]
cmp eax, DWORD PTR [var+4]
jb @@RETURN1

mov eax, 0
jmp @@Exit

@@RETURN1:

mov eax, 1
jmp @@Exit

@@Check2and3:

mov eax, DWORD PTR [var+8]
cmp eax, DWORD PTR [var+12]
jb @@RETURN4

mov eax, 2
jmp @@Exit

@@RETURN4:

mov eax, 3
jmp @@Exit

@@SecondPartition:

mov eax, DWORD PTR [var+16]
add eax, DWORD PTR [var+20]

mov ecx, DWORD PTR [var+24]
add ecx, DWORD PTR [var+28]

cmp eax, ecx
jb @@Check6and7

mov eax, DWORD PTR [var+16]
cmp eax, DWORD PTR [var+20]
jb @@RETURN5

mov eax, 4
jmp @@Exit

@@RETURN5:

mov eax, 5
jmp @@Exit

@@Check6and7:

mov eax, DWORD PTR [var+24]
cmp eax, DWORD PTR [var+28]
jb @@RETURN7

mov eax, 6
jmp @@Exit

@@RETURN7:

mov eax, 7

@@Exit:

invoke dwtoa, eax, OFFSET Bfr
invoke MessageBox, 0, OFFSET Bfr, 0, 0

invoke ExitProcess, 0

END Start
This one has a lot of compares but only executes 3 cmps(most) 1 cmp (least). :)


I warn you that this one will not work if the odd number is less than the other numbers that were equal.

Like this 4, 4, 4, 4, 2, 4, 4, 4, 4


If you want this to work perfectly 1 cmp more is needed. But that would make the total :: 4 cmps :(
Posted on 2002-03-25 14:22:22 by stryker
Use two three way branches - I don't have
time to code it now, but it's not really hard.

Three states:


1 = 1 2
1 < 2 1
2 > 1 1
By comparing the first two, you can know
the state of all three! The first part consists of comparing
the sum of the first two sets of three (compare one).
Then you compare the three values in the known
set (compare two). I believe this is the solution
Svin has as well - see my signature below. :)
Posted on 2002-03-25 14:28:18 by bitRAKE
Forgive me - I lack an assembler/debugger here:
	mov eax,v1

mov edx,v4
add eax,v2
add edx,v5
add eax,v3
add edx,v6
xor ecx,ecx
cmp eax,edx
mov edx,OFFSET v1
jlt __1
jgt __2
__3: add ecx,3
__2: add ecx,3
__1: mov eax,[edx + ecx*4]
cmp eax,[edx + ecx*4 + 4]
jlt _1
jgt _2
_3: inc ecx
_2: inc ecx
_1: ret
ECX is index number...
Posted on 2002-03-25 16:41:09 by bitRAKE
xor is not allowed, but it's obviously means in your code as
mov reg , 0
so it's OK.
A few words, if I may.

I didn't know asm solution when I posted it, but of course
math logic of it is well known. At least I studied it in 2nd grade
when teacher explained us (little babies) what means < > =.
I think the problem belongs to the algo section pretty well,
'cause in algo terms there is no such one as how offten some
instuction is put in source - importan thing is how often it
is executed (so to called O).
And in example for 9 O is O(log3N) 2 cmp for N = 9 (3^2=9)
3 cmp for N = 27 (3^3=27) etc.
Though as I stated most important thing is how often the cmp
is executed, I feel that many people here took it as restriction
not put cmp more than twice in code.
So it's OK for me too, I'll stick with two cmp in source wich also
will be executed twice, no more.
bitRake was right, that by one comparasion you can know state
of all three, and if you group 9 to 3 by first comparasion you can
determine index of group of 3s and after that make comparesion in
found group.
Here is one primitive of possible realisation of the logic, just
to show you the way:
return 1 for v1 2 for v2 etc.


mov ecx,v1
mov edx,v4
add ecx,v2
add edx,v5
add ecx,v3
add edx,v6
cmp ecx,edx
mov eax,7
mov ecx,v8
mov edx,v9
je @chek
mov eax,4
mov ecx,v5
mov edx,v6
jl @chek
mov eax,1
mov ecx,v2
mov edx,v3
@chek: cmp ecx,edx
je @ret
jl @a1
add eax,1
@a1: add eax,1
@ret: ret
Posted on 2002-03-25 16:50:53 by The Svin
Here is one for the Svin to try!

Same problem as before, BUT this time use only ADD, MOV, and J**, so NO SUB, or CMP, or anything else for that matter.

Whats more, the odd variable may be more or less than the others.

Can it be done (I think it can)?

Mirno
Posted on 2002-03-26 01:37:38 by Mirno
Here is one for the Svin to try

It's nice to see you in the algo section again, Mirno.
I'll try to solve the problem, but in another thread.
'Cause I need to stress that the thread is - how to solve the problem by no more than 2 comparesion steps.

Excuse my English is "odd" here means just "different from the others" or it also means odd as not dividable by 2?
Least sign. bit = 1 ?
Posted on 2002-03-26 06:05:00 by The Svin
Odd as in different from the others

Mirno
Posted on 2002-03-26 06:06:27 by Mirno
Seeing as nobody has tried my variation on the problem (ie doing the task with no cmp/sub instructions), I will post my solution.

Please remember that it is designed to run with no cmp/sub instructions, and not to run fast! In fact it will run very slowly, but it does the job using only add, mov, and j** instructions!



mov esi, offset v1
mov ecx, 0
mov eax, [esi]

@@:
add ecx, 1
add eax, 1
jnz @B

; ecx = -v1

mov edx, [esi + 4]
add edx, ecx
jnz v1_or_v2_is_bad

mov eax, 1

@@:
add eax, 1
mov edx, [esi + eax*4]
add edx, ecx
jz @B

ret

jnz v1_or_v2_is_bad:
mov eax, 0 ; assume v1 is bad
mov edx, [esi + 8]
add edx, ecx
jnz @F

mov eax, 1 ; To get here v1, & v3 are equal - so v2 must be bad
@@:
ret


Mirno
Posted on 2002-03-27 04:46:34 by Mirno
We need a Touring machine ;)
Posted on 2002-03-27 05:24:45 by Maverick