/    Sign up×
Community /Pin to ProfileBookmark

Euclidean Algorithm help

Copy linkTweet thisAlerts:
Jun 13.2017

I picked up this algorithm somewhere online among many that I had looked through and it does exactly what I want it to do, but I’m not sure how exactly it’s working. I understand how the euclidean algorithm works, but I don’t understand how this script is actually performing the algorithm. Would someone mind helping me go through this algorithm line by line with, for example, numerator = 16 and denominator = 24 ?

[code]
function gcd(numerator,denominator){
var gcd = function gcd(a,b){
return b ? gcd(b, a%b) : a;
};
gcd = gcd(numerator,denominator);
return gcd;
}
[/code]

This statement in particular is where I’m getting held up:

[code]
return b ? gcd(b, a%b) : a;
[/code]

I guess I just don’t really know what the condition is when it says “b ?”. Is it saying “If the return is B, then gcd(b, a%b)”? It’s quite confusing because it seems to be defining a function gcd withing itself.

I would appreciate any help in understanding why this works.

Thanks

to post a comment
JavaScript

5 Comments(s) ↴

Copy linkTweet thisAlerts:
@wbportJun 13.2017 — I think what it is doing is that when the mod function returns a zero, the answer is the current value of [B]a[/B]. This is what it looks like in an [B]awk[/B] script:[CODE]# check that two numbers were entered
if ( ARGV[1] ~ /^[0-9]+$/ && ARGV[2] ~ /^[0-9]+$/ ) {
a = ARGV[1]
b = ARGV[2]
if (b > a) { # a must be larger than b
a = ARGV[2]
b = ARGV[1] }
c = 1 # Done to not shut down the while statement before start
while ( c ) {
c = a % b
a = b
b = c }
printf("The gcd of %d and %d is %dn", ARGV[1], ARGV[2], a)
exit
}[/CODE]With 16 and 24, 24%16 = 8. To set the next iteration, c = 8, a = 16, and b=8. On the next loop 16%8 = zero, [B]a[/B] now has [B]b[/B]'s value (8) and [B]b[/B] is zeroed with [B]c[/B]'s value. The loop is over and the value of [B]a[/B] is returned.
Copy linkTweet thisAlerts:
@rootJun 13.2017 — if b == 0 then b will be same as saying FALSE otherwise any value other than zero is TRUE, so the return is saying [B]return[/B] b ?[B] gcd(b, a%b)[/B] : a; when b is not zero, but is saying [B]return[/B] b ? gcd(b, a%b) : [B]a[/B]; return the value of a if b is FALSE.
Copy linkTweet thisAlerts:
@NAK91authorJun 13.2017 — Thanks. I didn't know that a value of zero would evaluate to false for the ternary operator, so maybe that's where I was getting confused. Most of what I've read online about the ternary operator seems to directly compare a ternary operator with an If Then Else statement, indicating ternary as being kind of a shorthand notation.
Copy linkTweet thisAlerts:
@NAK91authorJun 13.2017 — Ok. So, what my example is saying would be:

<i>
</i>function gcd(numerator,denominator){ //use 16 and 24 as input
var gcd = function gcd(a,b){
return b ? gcd(b, a%b) : a; //If 24 is true (not zero), gcd(24, 16%24), Else 16
};
gcd = gcd(numerator,denominator);
return gcd;
}


So, gcd(24, 16%24) returns function gcd(8,24), which returns gcd(24, 8%24), which returns gcd(24,8), which returns gcd(8, 24%8), which returns gcd(8,0) and the ternary evaluates to false. Thus, 8 is returned. I think I've got it.

I appreciate all the help.
Copy linkTweet thisAlerts:
@rootJun 16.2017 — Near enough but your function only needs to be this...
function gcd(a,b){
return b ? gcd(b, a%b) : a;
}
You don't need to declare a function within the function every time you call the main function.
×

Success!

Help @NAK91 spread the word by sharing this article on Twitter...

Tweet This
Sign in
Forgot password?
Sign in with TwitchSign in with GithubCreate Account
about: ({
version: 0.1.9 — BETA 6.17,
whats_new: community page,
up_next: more Davinci•003 tasks,
coming_soon: events calendar,
social: @webDeveloperHQ
});

legal: ({
terms: of use,
privacy: policy
});
changelog: (
version: 0.1.9,
notes: added community page

version: 0.1.8,
notes: added Davinci•003

version: 0.1.7,
notes: upvote answers to bounties

version: 0.1.6,
notes: article editor refresh
)...
recent_tips: (
tipper: @nearjob,
tipped: article
amount: 1000 SATS,

tipper: @meenaratha,
tipped: article
amount: 1000 SATS,

tipper: @meenaratha,
tipped: article
amount: 1000 SATS,
)...