some people have suggested (or asked why I didn't use)
why didn't I use it ?
a nice implementation of that idea can be seen at Paul Hsieh's website:
it goes like this:
gcd: add edx,eax
now, remember the "original" C version ?
int gcd(int a, int b)
}what's the advantage of that one over a subtraction-only method ?
there's basically only one: speed !
imagine gcd(1,1000000) ! how many iterations are needed for that one ?
the C version may use slow operations, but it only takes a couple of runs
btw, that algorithm is some 2000 years old ! and still perfectly valid :)
now, on to the real stuff:
while I was toying around with a branchless array-version, I finally
first of all, "simplifying" by 2 should be done as much as possible
even better, no storage space for temporary values is needed
in short, all we have to do is:
that's it already
back to our gcd(1,1000000) example
1 1 000 000
done ! amazing, isn't it ? :)
btw, worst case input for that alg. is actually 2 consecutive Fibonacci numbers
e.g. 89 and 55
(subtraction-only is left as an exercice for the reader)
finally, combining all of the above, some (lots) of ideas from replies
; int gcdAsm(int a, int b)
mov eax,[ebp + 8] ; eax = a (0 <= a <= 2^31 - 1 (= 2 147 483 647))
; by definition: gcd(a,0) = a, gcd(0,b) = b, gcd(0,0) = 1 !
bsf ecx,eax ; "simplify" a as much as possible
add eax,ecx ; a-new = min(a,b)
sub ebx,eax ; we're now sure that that difference is >= 0
bsf ecx,eax ; "simplify" as much as possible by 2
bsf ecx,ebx ; "simplify" as much as possible by 2
jnz mainLoop ; keep looping until ebx = 0
mov ecx,edi ; multiply back with the common power of 2
this should even satisfy those that asked for "cleaner" code with less exit-points :)
("bsf" is really only an option on ppro, p2 or better
all comments, as usual, welcome
" A child of five could understand this, fetch me a child of five "
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.