let's say that i got these two dword values located in memory:

dd value1
dd value2

what would be the fastest way to find them in memory if I only knew the result of value1+value2..?

would really appreciate some code snippet:) thank you!
Posted on 2004-02-23 15:57:14 by DZA
If I understood you right, the problem is that any value in memory could potentially be value1, because the sum does not give you any information about the two values except a relation between them.

The first idea that came to my mind was to use a binary search tree.

Go through memory and for each value look up sum - value in the tree -- if it's there you are done, if not insert it.

That should run in O(n * log n) time as far as I can see.

I am sure there is some much simpler solution here soon that will make me bang my head against the wall for half an hour :grin:
Posted on 2004-02-23 16:33:08 by Jibz
Jibz, yes you got it right, that's exactly what I want to do:)

this is how I would do this...:


lea esi, memory
@@:
mov ecx, dword ptr ; get possible value 1
mov edx, dword ptr ; get possible value 2
add edx, ecx ; add them
cmp edx, dword ptr ; check if the result matches my sum
jz sweetivefoundmyvalues
inc esi
jmp @b

i was wondering if there could be any other, faster way...?
Posted on 2004-02-23 18:02:40 by DZA
Ah, so I did misunderstand you :)

I thought the two values could each be placed anywhere in the data, but if they are always right after each other it's a much simpler problem.

And you are right, your linear scan is the algorithm to solve that. You could probably get away with only reading each dword once, by keeping the last read value in a separate register.

But that's just 'CPU twiddling', there is no faster algorithm since you have to look at all values to be able to tell if any consecutive pair sums up to the desired result.
Posted on 2004-02-24 02:23:25 by Jibz