I am compiling using the cl program that runs in the command line for visual basic (got sick of creating a new project for every snippet of code) Running windows vista home basic.
The program is an extended exercise from C++ for Mathematicians by Scheinerman
the header and function code were given in the book, I wrote the main() and the extra cout in the function
Here is header file
CODE
#ifndef GCD_H
#define GCD_H
/**
*Calculate the greates common divisor of two integers.
*Note: gcd (0,0) will return 0 and print an error message.
*@param a the first integer
*@param b the second integer
*@return the greatest common divisor of a and b
*/
long gcd(long a, long b);
long gcd(long a, long b, long&x, long&y);
#endif
the function file
CODE
#include <iostream>
using namespace std;
long gcd(long a, long b, long&x, long&y)
{
long d; // place to hold final gcd
// in case b=0, we have d=|a|, x =1 or -1, y arbitrary (say, 0)
if (b==0)
{
if (a<0)
{
d = -a;
x = -1;
y = 0;
}
else
{
d = a;
x = 1;
y = 0;
}
return d;
}
// if b is negative, here is a workaround
if (b<0)
{
d = gcd (a,-b,x,y);
y = -y;
return d;
}
// if a is negative, here is a workaround
if (a<0)
{
d = gcd (-a,b,x,y);
x = -x;
return d;
}
// set up recursion
long aa = b;
long bb = a%b;
long qq = a/b;
long xx,yy;
d = gcd(aa,bb,xx,yy);
x = yy;
y = xx - qq*yy;
cout << x <<","<<y<<","<<xx<<","<<yy<<"\n"; // this verifies x and y are correct
return d;
}
and the main file
CODE
#include "gcd.h"
#include <iostream>
using namespace std;
/**
*A program to find d = ax + by given a, b
*Linear Diophantine Equations
*/
int main ()
{
long a,b,x,y;
cout << "Enter the first number --> ";
cin >> a;
cout << endl;
cout << "Enter the second number --> ";
cin >> b;
cout << endl;
x=1;
y=1;
cout << "The gcd of " << a << " and " << b << " is "
<< gcd(a,b,x,y) << "=" << a << "x" << x
<< "+" << b << "x" << y << endl;
return 0;
}
This post has been edited by thompson03: 8 Jul, 2008 - 02:21 PM
| 