Help With Euclids Extended Algorithim ( Integer division by zero Error )

This is a discussion on Help With Euclids Extended Algorithim ( Integer division by zero Error ) within the C++ Programming forums, part of the General Programming Boards category; so im doing a program on euclids algorithim, and im having problems with the last function, i made a menu ...

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    4

    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];
    
    	
    		}

  2. #2
    Registered User
    Join Date
    Sep 2008
    Posts
    200
    Have you tried using a debugger to step through your code? It'll show you where the error occurs. Debuggers are very useful - get to know yours well!

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Code:
    for (; (b % (a%b)) != 0; i++)
    If 'a' starts out as 4 and 'b' starts out as 2, what do you expect the value of b % (a%b) to be?Or even simpler, what about just a%b?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 10-14-2009, 05:47 AM
  2. Replies: 4
    Last Post: 09-17-2009, 01:31 PM
  3. double division error (I get -0.0000)
    By dorakura in forum C Programming
    Replies: 6
    Last Post: 03-07-2008, 06:33 PM
  4. error on in algorithim
    By v3dant in forum C Programming
    Replies: 1
    Last Post: 11-08-2004, 10:03 AM
  5. overloading the division operator with Integer Class
    By silk.odyssey in forum C++ Programming
    Replies: 3
    Last Post: 05-17-2004, 06:59 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21