Help With Euclids Extended Algorithim ( Integer division by zero Error )
so im doing a program on euclids algorithim, and im having problems with the last function,
i made a menu to allow the user to choose between the normal gcd calculator or
to view the extended algorithim which displays the steps, unfortunatly i am having a problem with the extended part. help would be much appreciated, thanks
Code:
#include<iostream>
#include<iomanip>
using namespace std;
int Normal_GCD();
int Extended_Euclidian_Algorithim();
int main() // Main Program Scope
{
int menuvalue;
int arraycounter = 0;
cout << "-----Select a option-----\n";
cout << " 0 GCD Calculator\n";
cout << " 1 Extended Euclidian Algorithim\n";
cout << " 2 Quit\n";
cin >> menuvalue;
if( menuvalue == 0 )
Normal_GCD();
if ( menuvalue == 1 )
Extended_Euclidian_Algorithim();
//else if (menuvalue == 2)
return 0;
}
//---------------------------------------------------------------------------------------------------------------------------//
int Normal_GCD()
{
int dividend, divisor, remainder, number1, number2 = 0; // Declaring Variables
cout << " This Function Will Find The GCD Of 2 Numbers " << endl << endl; // States What The Program Will Do
cout << "Plese Enter The First Number: "; // Enters First Number And
cin >> number1; // Assigns It To The First
cout << endl << endl; // Variable Slot .
cout << "Please Enter The Second Number: "; // Enters Second Number And
cin >> number2; // Assigns It To The Second
cout << endl << endl; // Variable Slot .
if (number1 > number2) // If The First Number Was The Bigger Number Then
{ // It Was Placed As The Dividend
dividend = number1;
divisor = number2;
}
else // If The Second Number Was The Bigger Number Then
{ // It Was Placed As The Dividend
dividend = number2;
divisor = number1;
}
do{
remainder = dividend % divisor;
if(remainder !=0)
{
dividend = divisor;
divisor = remainder;
}
}
while(remainder != 0); //Loops Until The Remainder Is 0
cout << " The GCD OF " << number1 << " And " << number2 << " is: " << divisor << endl << endl; // Calls The Details And Places Them Into A Sentence
cout << setw(15) << "Proof: " << endl << endl;
cout << "GCD" << endl;
cout << setw(2) << divisor << " * " << number1 / divisor << " = " << (number1 / divisor) * divisor << endl;
cout << setw(2) << divisor << " * " << number2 / divisor << " = " << (number2 / divisor) * divisor << endl << endl;
system("PAUSE");
return 0;
}
//---------------------------------------------------------------------------------------------------------------------------//
int Extended_Euclidian_Algorithim()
{
int a;
int b;
cout << "Please Enter The First Number : ";
cin >> a;
cout << endl << endl;
cout << "Please Enter The Second Number : ";
cin >> b;
cout << endl << endl;
int x[3];
int y[3];
int quotient = a / b;
int remainder = a % b;
x[0] = 0;
y[0] = 1;
x[1] = 1;
y[1] = quotient * -1;
int i = 2;
for (; (b % (a%b)) != 0; i++)
{
a = b;
b = remainder;
quotient = a / b;
remainder = a % b;
x[i % 3] = (quotient * -1 * x[(i - 1) % 3]) + x[(i - 2) % 3];
cout << x [i % 3] << " = " << " ( " << (quotient * -1 * x[(i - 1) % 3]) << " + " << x[(i - 2) % 3] << endl;
y[i % 3] = (quotient * -1 * y[(i - 1) % 3]) + y[(i - 2) % 3];
cout << x [i % 3] << " = " << " ( " << (quotient * -1 * x[(i - 1) % 3]) << " + " << x[(i - 2) % 3] << endl;
}
//x[i — 1 % 3] is inverse of a
//y[i — 1 % 3] is inverse of b
return x[(i - 1) % 3];
}
