ID:1604992
 
The following are two procedures to calculate the greatest common denominator(GCD) of two numbers. The reason I'm listing two procedures instead of one is because my benchmark results of them prove their runtimes are the same in a sense. Considering the ternary procedure is pretty much the exact same as the basic procedure it makes sense for them to come up as the faster/slower than each other depending on the runtimes.

Syntaxs:
Basic_GCD(number1,number2)
Ternary_GCD(number1,number2)

Code:
//Basic
proc
Basic_GCD(num1 as num,num2 as num)
if(!num2) return num1
return Recursive_GCD(num2, num1%num2)

//Ternary
proc
Ternary_GCD(num1 as num,num2 as num)
return !num2 ? num1 : Recursive_Ternary_GCD(num2, num1%num2)


How to use:
mob/verb/GCD()
var number1=3000, number2 = 3
world << Basic_GCD(number1,number2)
world << Ternary_GCD(number1,number2)


Output:
3
3
It seems to show issues in which there is no greatest common denominator other than 1.

Example: 42 and 13. 13 and 5.

The problem comes from your line here
return num1%num2


Normally, I'd do a check for even/odd. Even numbers can be based on powers of 2, and I'd reduce odd numbers to even numbers and solve the problem above.

A brute force method could also be employed, where you check every integer between 0 and the smaller number to see if it divides the larger number.
Your right. I should have actually checked this before posting it. It was a snippit laying around in my old files and I figured it wouldn't have any issues else i'd have noted it in the file. Thanks for pointing that out! I'll fix it up when I get up as it's 6:53 AM here and I haven't slept yet.
Fixed and Updated to avoid the issue Lugia addressed. I couldn't sleep without fixing it. Lol.
It's still broken, mate. Try combos such as 42 and 12. Any combo where a%b != 0

The issue is this line:
if(!((num1%num2)%1<1))    return num1%num2

at a glance.
Unless I'm misunderstanding their purpose, these probably shouldn't specifically be /mob procedures.
In response to Lugia319
Lugia319 wrote:
It's still broken, mate. Try combos such as 42 and 12. Any combo where a%b != 0

The issue is this line:
> if(!((num1%num2)%1<1))    return num1%num2
>

at a glance.
Anything were a GCD wouldn't be 1 it returns a value that it should be. Else it returns 1, which would be the greatest common denominator. Unless I'm missing something. 42 and 13 as posted above, return with 1. So goes 13 and 5.

LordAndrew wrote:
Unless I'm misunderstanding their purpose, these probably shouldn't specifically be /mob procedures.

Your right on that, my apologies I typed this pretty fast pretty late.
But 42 and 12 return 1 when it should return 6.

44 and 12 return 1 when it should return 2.
In response to Lugia319
Lugia319 wrote:
But 42 and 12 return 1 when it should return 6.

44 and 12 return 1 when it should return 2.

Ohh, now I understand what you mean. Alright. I thought you meant it was returning numbers where it should return 1. Give me a bit to fix it; shouldn't take long.

Edit: Thinking about it now I should have just made these Recursive.
The recursive solution is the one I would've gone with, yes.
Welp, just got up and flipped them around to be recursive. Everything works out fine now. It's a pity really. I wanted to stay away from recursion as it's not very efficient in DM. It actually tends to be slower than other methods I've used. (Not always for this particular case)
Looks good now, thanks!
For an iterative solution you can go with:

proc/gcd_iterative(var/u as num,var/v as num)
var/t
while (v)
t = u
u = v
v = t % v
return abs(u)


Lovingly pinched from http://rosettacode.org/wiki/ Greatest_common_divisor#Iterative_Euclid_algorithm
Yeah, I was aware you could do a looped GCD but when i benchmarked it against the recursive, and non recursive ones i had before it was horrible slow.
Fair enough. I mean essentially a GCD/HCF function isn't going to be your performance bottleneck anyway, so it doesn't matter much. But by way of idle amusement, I set the following up:

proc/Basic_GCD(num1 as num,num2 as num)
if(!num2) return num1
return Basic_GCD(num2, num1%num2)

proc/gcd_iterative(var/u as num,var/v as num)
var/t
while (v)
t = u
u = v
v = t % v
return abs(u)

client/verb/Test_Basic_GCD()
rand_seed(1)
var/i = 0
while (i < 100000)
i++
Basic_GCD(rand(1,100000),rand(1,100000))

client/verb/Test_Iterative_GCD()
rand_seed(1)
var/i = 0
while (i < 100000)
i++
gcd_iterative(rand(1,100000),rand(1,100000))


Essentially using the rand_seed() to produce consistent and fair "random" data, that will be the same for both functions, and the same across verb calls. Hopefully the ranges seem reasonable, as this produces a range of data that's a little more representative of "many scenarios", so you don't for example see as much bias for one algorithm performing much better with small / big inputs.

For comparative purposes, you wanna look at the verb calls, as obviously the recursive procedure produces a lot more actual calls and I suspect DM profiler's accounting is a little off for that.

On my machine:
/client/verb/Test_Basic_GCD Total CPU: 1.284
/client/verb/Test_Iterative_GCD Total CPU: 0.603

I mean ... in practice, use either, these are not exactly big performance numbers we're talking here, for quite a few calls. You're talking 128 micro-seconds per call to 60 micro-seconds, after all.
In response to Stephen001
Hmm. That's interesting. I used 30, and 3 when testing mine but had it calculate 10 million times over. My iterative code took 22.0ish CPU and the Recursive took 1.2ish. Didn't save the profiled results. I'll checks yours out in a little bit and see if the way I set mine up was just inefficient.
I don't think it's possible on BYOND to do better than Stephen's gcd_iterative(). The Euclidean algorithm is insanely good, especially iterative.
That's kind of the issue I have with these kind of snippets, to be honest. They are usually about well known problems, that a quick Google will give you an optimal/asymptopically optimal solution for.

But I dunno, maybe we're sufficiently self-isolated here on BYOND that people won't just Google these kinds of problems.
Good point. It is a bit of wonder. I'm guilty of it from time to time.
Well as far as mathematical snippets go, sure. But while the algorithms are fairly easy to find, converting them into languages isn't quite as easy. I'm working on a matrix library atm, almost fully functional (with the only bug being a dot product function). Many languages have the libaries to deal with these issues, but BYOND doesn't.

I think a lot of the more useful snippets probably come as a result of trying to make the language do more, rather than do something we know it can do.