There are 3 possible implementation for Euclid's algorithm:

__1. Division-Based Euclid__/* * Description: * Returns the greatest common denominator of a and b using the * Euclid's algorithm division-based. * Parameters: * a,b - two positive integers * Returns: * the greatest common denominator */ int Euclid_Gcd_Division(int a, int b) { int temp; while(b!=0) { temp = b; b = a % b; a = temp; } return abs(a); }Here's numeric example on how the algorithm works:

Phase | a | b | temp |

Initialization | 32 | 15 | Undefined |

Step 1 | 15 | 2 | 15 |

Step 2 | 2 | 1 | 2 |

Step 3 | 1 | 0 | 1 |

__2.Subtraction-based Euclid__/* * Description: * Returns the greatest common denominator of a and b using the * Euclid's algorithm subtraction-based. * Parameters: * a,b - two positive integers * Returns: * the greatest common denominator */ int Euclid_Gcd_Subtraction(int a, int b) { a = abs(a); b = abs(b); if (a != 0) { while (b != 0) { if (a > b) { a = a - b; } else { b = b - a; } } } return a; }Here's a numeric example on how the algorithm works:

Phase | a | b | Observation |

Input | -32 | 15 | |

Initialization | 32 | 15 | a>b |

Step 1 | 17 | 15 | a>b |

Step 2 | 2 | 15 | a<b |

Step 3 | 2 | 13 | a<b |

Step 4 | 2 | 11 | a<b |

Step 5 | 2 | 9 | a<b |

Step 6 | 2 | 7 | a<b |

Step 7 | 2 | 5 | a<b |

Step 8 | 2 | 3 | a<b |

Step 9 | 2 | 1 | a>b |

Step 10 | 1 | 1 | a>b |

Step 11 | 1 | 0 | b>=a (else branch) |

__3.Recursion-based Euclid__/* * Description: * Returns the greatest common denominator of a and b using the * Euclid's algorithm recursion-based. * Parameters: * a,b - two positive integers * Returns: * the greatest common denominator */ int Euclid_Gcd_Recursion(int a, int b) { int result; if (b == 0) { result = a; } else { result = Euclid_Gcd_Recursion(b, a % b); } return abs(result); }The algorithm is the same as the division-based Euclid algorithm. The difference is that this is algorithm is recursive, while the division-based Euclid is iterative.

__4.Example__#include<stdio.h> #include<stdlib.h> int Euclid_Gcd_Division(int a, int b); int Euclid_Gcd_Subtraction(int a, int b); int Euclid_Gcd_Recursion(int a, int b); int main(void) { int a = 580; int b = -320; printf("Euclid division based : %d\n" "Euclid subtraction based: %d\n" "Euclid recursion based : %d\n", Euclid_Gcd_Division(a,b), Euclid_Gcd_Subtraction(a,b), Euclid_Gcd_Recursion(a,b)); return 0; }

Thank you so much! This post was so helpful for my work :)

ReplyDelete