S01E01: GCD and Fibonacci: Shakespeare of Computing

Question:

What is the worst case scenario for Euclid’s GCD algorithm and what does it have to do with Fibonacci sequence?

Additional Questions:

Note the number of steps taken for a pair of numbers in Euclid’s GCD algorithm, is there any other pair smaller than this which takes the same number of steps?

What is the smallest pair for a certain number of steps taken in GCD algorithm?

Look at these pairs of inputs and the number of steps taken in GCD algorithm, is there any relationship between the these inputs and the number of steps taken.

What are the properties of inputs for which you get more steps in GCD algorithm?

Coding Assignments:

Create a program that taken an input pair and returns their GCD and also the number of steps taken to compute that. (implement Euclid’s GCD algorithm).

Create a program that gives the smallest input pairs given the number of steps it should take in Euclid’s GCD algorithm.

Create a program to emperically find the worst case input pairs for Euclid’s GCD algorithm.

Plot graphs of input pair ratios and the number of steps it takes to compute GCD using Euclid’s GCD algorithm.

← Back to Season 01