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.

## Comments

Sort by:

TopNewestI 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.

– Mark Hennings · 3 years, 11 months agoLog in to reply

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

– Mark Hennings · 3 years, 11 months ago

So you want to know about the time complexity of the Euclidean algorithm. Try some consecutive Fibonacci numbers.Log in to reply

– Calvin Lin Staff · 3 years, 11 months ago

Yes, that is the idea of the question.Log in to reply

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

– Tim Vermeulen · 3 years, 11 months ago

Yup.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

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

Log in to reply

– Calvin Lin Staff · 3 years, 11 months ago

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?Log in to reply

– Lokesh Sharma · 3 years, 11 months ago

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.Log in to reply

– Michael Tang · 3 years, 11 months ago

I'm guessing he means "find the GCD of two numbers each about \(10^9.\)"Log in to reply

Log in to reply

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

– Nathan Antwi · 3 years, 11 months ago

I think this one is good... I dident think of that.. nice..Log in to reply

– Nathan Antwi · 3 years, 11 months ago

Alright. I'm working on a code right now...during class.Log in to reply

– Michael Tang · 3 years, 11 months ago

So in Python, we can't use a while loop?Log in to reply

– Nathan Antwi · 3 years, 11 months ago

I guess not..All the codes i have scripted use a loop and i guess thats not permitted here.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