-


Extended Euclid Algorithm:



This is the extended form of Euclid’s Algorithm explained in previous post. GCD(A,B) has a special property that it can always be represented in the form of an equation, i.e., Ax + By = GCD(A, B).

This algorithm gives us the coefficients (x and y) of this equation which will be later useful in finding the Modular Multiplicative Inverse. These coefficients can be zero or negative in their value. This algorithm takes two inputs as A and B and returns GCD(A, B) and coefficients of the  equations as output.


Implementation:


#include < iostream > int d, x, y; void extendedEuclid(int A, int B)
{ if(B == 0) { d = A; x = 1; y = 0; } else { extendedEuclid(B, A%B); int temp = x; x = y; y = temp - (A/B)*y; } } int main( )
{ extendedEuclid(16, 10); cout << ”The GCD of 16 and 10 is ” << d << endl; cout << ”Coefficient x and y are: ”<< x << “and “ << y << endl; return 0; }


Output:

The GCD of 16 and 10 is 2
Coefficient x and y are: 2 and -3


Initially, Extended Euclid Algorithm will run as Euclid Algorithm until we get GCD(A, B) or until B gets 0 and then it will assign x = 1 and y = 0. As B = 0 and GCD(A, B) is A in the current condition, so equation Ax + By = GCD(A, B) will be changed to A * 1 + 0 * 0 = A.

So the values of d, x, y in the whole process of extendedEuclid( ) function are:

1) d=2, x = 1, y = 0.
2) d=2, x = 0 , y = 1 - (4/2) * 0 = 1.
3) d=2, x = 1 , y = 0 - (6/4) * 1 = -1.
4) d=2, x = -1 , y = 1 - (10/6) * -1 = 2.
5) d=2 , x= 2, y = -1 - (16/10) * 2 = -3.

Time Complexity: The time complexity of Extended Euclid’s Algorithm is O(log(max(A, B))).






Comments

Post a Comment

Popular posts from this blog

-
Image
Sphenic Number A  Sphenic Number  is a positive integer  n  which is product of exactly three distinct primes. The first few sphenic numbers are 30, 42, 66, 70, 78, 102, 105, 110, 114, … Sphenic number can be checked by fact that every sphenic number will have exactly 8 divisor  SPHENIC NUMBER So first We will try to find if the number is having exactly 8 divisors if not then simply answer is no.If there are exactly 8 divisors then we will confirm weather the first 3 digits after 1 are prime or not. Eg. 30 (sphenic number) 30=p*q*r(i.e p,q and r are three distinct prime no and their product are 30) the set of divisor is (1,2,3,5,6,10,15,30) Examples: 30 = 2 × 3 × 5 Sphenic number can be checked by fact that every sphenic number will have exactly 8 divisor  SPHENIC NUMBER So first We will try to find if the number is having exactly 8 divisors if not then simply answer is no.If there are exactly 8 divisors then we will confirm weather...
Read more

Fibonacci numbers with help of DP

-
Image
Well...the most and simple program which every programmer may have solved at least once.... Fibonacci numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …….. In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation.... with base condition f(0)=0  f(1)=1 In general: f(n)=f(n-1) +f(n-2) Basic Approach: A simple method that is a direct recursive implementation mathematical recurrence relation given above Here is simple CPP program.... #include<bits/stdc++.h> using namespace std;     int fib( int n) {      if (n <= 1)          return n;      return fib(n-1) + fib(n-2); }     int main () {      int n = 9;      cout << fib(n);      return 0; } That was simple....isn't it........
Read more
-
Image
Tutorial-2 is out!!!!! Fasten your seat-belt! Problem-2:- Understanding this problem and its solution properly will make a strong foundation for you in the DP world .(This worked for me :-) ) Here we go- Given an array of integers(positive as well as negative) ,select some elements from this array(select a subset) such that:- Sum of those elements is maximum(Sum of the subset is maximum) . No 2 elements in the subset should be consecutive. Example :- {2,4,6,7,8} Answer:- {2+6+8=16} Common Trick : We create a dp-array , and dp[i] means the maximum sum we could get till index-’i’ of the array. For the above example, dp[1] = 2 (2), [This is the best answer you could get if size of the array was one] dp[2]= 4(4),[This is the best answer you could get if size of the array was two] dp[3]=8(6+2),[This is the best answer you could get if size of the array was three]………lets call this equation-(1)… dp[4]=11(7+4),[This is the best answer you could get if size of ...
Read more