Waste less time on Facebook — follow Brilliant.
×

GCD and the Euclidean Algorithm

Introducing …. the Greedy Calvinosaurus Dinosaur

In this week's post, learn about Greatest Common Divisor.

Last week, we introduced several questions based on calculating the Greatest Common Divisor of several integers and polynomials. Using the Euclidean Algorithm is a standard approach to helping us to quickly calculate these values.

Judging from the comments in the solution discussions, here are some questions for you to ponder:

1) If \( n < 10 \), can \( \gcd (n, m ) > 10 \)?

2) What is the value of \( \gcd( -14, -21 ) \)?

3) Why does the Euclidean algorithm work? Specifically, why does \( \gcd(n,m) = \gcd(n, m+kn ) \) for any integers \(n, m, k \)?

For those who want a coding challenge:

Write code to calculate the GCD of 2 numbers, which ends in finitely many steps. You are not allowed to use conditions like “If n > 0, continue” or equivalent hacks.

Note by Calvin Lin
3 years, 11 months ago

No vote yet
24 votes

Comments

Sort by:

Top Newest

I generally programme in Pascal. Apart from the setting-up exercises (to ensure that \(a\) and \(b\) are positive and ordered), the function calls itself recursively as many times as the Euclidean algorithm is used in the calculation of the gcd.

function gcd(a,b: Integer): Integer;
begin
if ((a < 0) or (b < 0)) then
 begin
 Result := gcd(Abs(a),Abs(b));
 exit;
 end;
if a < b then
 begin
 Result := gcd(b,a);
 exit;
 end 
if b = 0 then
 Result := a 
else 
 Result := gcd(b, a%b);
end;
Mark Hennings · 3 years, 11 months ago

Log in to reply

@Mark Hennings As I said, you are not allowed to use "if n \( > 0 \)" conditions (similarly for "while \(n>0\)"). You have hidden it within calling of the gcd function.

The main aspect of this problem is to figure out the number of steps which the Euclidean algorithm has to take. Calvin Lin Staff · 3 years, 11 months ago

Log in to reply

@Calvin Lin So you want to know about the time complexity of the Euclidean algorithm. Try some consecutive Fibonacci numbers. Mark Hennings · 3 years, 11 months ago

Log in to reply

@Mark Hennings Yes, that is the idea of the question. Calvin Lin Staff · 3 years, 11 months ago

Log in to reply

@Calvin Lin If \(a \ge b \ge 1\), then the number of applications of the Division Algorithm needed to calculate the HCF of \(a\) and \(b\) is no greater than \(5\log_{10} b\). Thus:

function gcd(a,b: Integer): Integer;
var i,j,k,m: Integer;
begin
if Abs(a) >= Abs(b) then
  begin
  Result := Abs(a);
  j := Abs(b);
  end
else
  begin
  Result := Abs(b);
  j := Abs(a);
  end;
k := Int(5*Log(j));
for i := 1 to k do
  begin
  if j = 0 then break;
  m := j;
  j := Result % j;
  Result := m;
  end;
end;
Mark Hennings · 3 years, 11 months ago

Log in to reply

I hope these are right:

1) Yes, if \(n < -10\)

2) 7 C D · 3 years, 11 months ago

Log in to reply

@C D Yup. Tim Vermeulen · 3 years, 11 months ago

Log in to reply

Hello Calvin! Will you post the answers to the 3 questions in the future? That would greatly help.

A few questions, how do you define gcd of negative numbers? Can you please give a few hints for the second question? In the first question, can n be negative?

Thanks! Pranav Arora · 3 years, 11 months ago

Log in to reply

@Calvin What do you mean by " finite many steps"? Do you mean to write a code in the least amount of lines of code? Nathan Antwi · 3 years, 11 months ago

Log in to reply

@Nathan Antwi It shouldn't have a phrase equivalent to "If \(n, m>0\), continue".

It can have a phrase "For i = 1 to \(\max(n,m) \)", though of course this is very inefficient. Calvin Lin Staff · 3 years, 11 months ago

Log in to reply

@Calvin Lin Is this one legit?

def gcd(m, n):

    a = max(abs(m), abs(n))

    b = min(abs(m), abs(n))

    for i in reversed(range(b+1)):

        if a % i == 0 and b % i == 0:

            return i
Lokesh Sharma · 3 years, 11 months ago

Log in to reply

@Lokesh Sharma This has to check every number from 1 to \(\max(a,b) \), which is extremely tedious. What is the complexity of your statement? How many steps would it take for you to find the gcd two \( 10^9 \) numbers? Calvin Lin Staff · 3 years, 11 months ago

Log in to reply

@Calvin Lin The complexity is O(n) I guess, because it would take about min(a, b) steps in the worst case to find the GCD. Right? How can I find the complexity of the one down below? I think it's O(log(n)) but I am not at all sure and have no idea how to find it. What does it mean to 'find the gcd two \( 10^9\) numbers'? Thanks for replying. Lokesh Sharma · 3 years, 11 months ago

Log in to reply

@Lokesh Sharma I'm guessing he means "find the GCD of two numbers each about \(10^9.\)" Michael Tang · 3 years, 11 months ago

Log in to reply

@Lokesh Sharma I am wondering, compared to the one below and above, which one's the better one in terms of speed?

def gcd2(m, n):

    a, b = max(abs(m), abs(n)), min(abs(m), abs(n))

    if a % b == 0:

        return b

    elif a % b == 1:

        return 1

    else:

        return gcd2(b, a%b)
Lokesh Sharma · 3 years, 11 months ago

Log in to reply

@Lokesh Sharma Your code would crash if you entered \(0\) as one of the values - it would try to divide by \(0\).

If you fix this, the code is about optimal for speed, but it breaks the rules about no loops, like my first version did. Mark Hennings · 3 years, 11 months ago

Log in to reply

@Lokesh Sharma I think this one is good... I dident think of that.. nice.. Nathan Antwi · 3 years, 11 months ago

Log in to reply

@Calvin Lin Alright. I'm working on a code right now...during class. Nathan Antwi · 3 years, 11 months ago

Log in to reply

@Calvin Lin So in Python, we can't use a while loop? Michael Tang · 3 years, 11 months ago

Log in to reply

@Michael Tang I guess not..All the codes i have scripted use a loop and i guess thats not permitted here. Nathan Antwi · 3 years, 11 months ago

Log in to reply

1) If \(n < 10\), then \(gcd(n, m)\) can be greater than \(10\). This is because if n can be negative too. Here's an example \(gcd(-20, 40) = 20\).

2) \(gcd(-14, -21) = 7\)

3) I'll post it later Arulx Z · 1 year, 10 months ago

Log in to reply

I'm not sure if this is allowed but it works.

astr = input("Type first number") bstr = input("Type second number") a = int(astr) b = int(bstr) while a < b or a > b: if a > b: a = a-b else: b = b-a if a == b: astr1 = str(a) print(astr1) C D · 3 years, 11 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...