473,379 Members | 1,330 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,379 software developers and data experts.

Greatest Common Divisor using Extended Euclid's Algorithm

Hi,
Can someone help me with an idea on how to start writing a C++ code
for generating
greatest common divisor and the linear combination of two intergers
represented as gcd(m, n)= mx + ny and adding them it will give us the
greatest common divisor and I need to use the extended Euclidean
algorithm.
I already have the code for the greatest common divisor but I dont
know how to do the linear combination.
This is what I have:

#include <iostream>
#include <iomanip>
using namespace std;

void gcd(int, int);
void extended_gcd(int, int, int, int);

int main()
{
int m=0, n=0;

cout<<"Welcome to the Greatest Common Divisor Program\n\n";
cout<<"Enter the first number: ";
cin>>m;
cout<<endl;
cout<<"Enter the second number: ";
cin>>n;
cout<<endl;
cout<<"gcd("<<m<<", "<<n<<") = ";
gcd(m, n);
return 0;
}

void gcd(int m, int n)
{
int r, q, d;
while (n!=0)
{
r = m % n;
q = m / n;
r = m - n * q; // I was thinking on put it on the stack
but I dont know how
m = n;
n = r;
}

d = m;
cout<<d<<endl;
//then pop the stack as d=r-q*n
}

May 30 '07 #1
4 13658
sd****@gmail.com writes:
Can someone help me with an idea on how to start writing a C++ code
[snip]

This is comp.lang.c. comp.lang.c++ is down the hall, just past the
water cooler, second door on the left.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
May 30 '07 #2
sd****@gmail.com wrote:
Hi,
Can someone help me with an idea on how to start writing a C++ code
[...]
Yes! Someone can help you!

... but you've chosen a strange place to look for
him or her. This is a newsgroup devoted to C, not to
C++, and (not to put too fine a point on it) some of
the devotees of C think C++ is the work of the Devil
and will have nothing to do with it -- they may or may
not be right, but if they shun C++ they are not likely
to be willing (or able) to offer you much help.

I suggest you seek assistance in one or more of
the following newsgroups:

comp.crypto.burn.before.reading
alt.religion.kibology
comp.fortran.fossils
rec.swedish.chef.bork.bork.bork
comp.lang.c++
alt.tin.foil.helmets

Choose whichever seems most likely to be helpful, and
try your question there.

--
Eric Sosman
es*****@acm-dot-org.invalid
May 30 '07 #3
On May 29, 11:44 pm, Eric Sosman <esos...@acm-dot-org.invalidwrote:
sdl...@gmail.com wrote:
Hi,
Can someone help me with an idea on how to start writing a C++ code
[...]

Yes! Someone can help you!

... but you've chosen a strange place to look for
him or her. This is a newsgroup devoted to C, not to
C++, and (not to put too fine a point on it) some of
the devotees of C think C++ is the work of the Devil
and will have nothing to do with it -- they may or may
not be right, but if they shun C++ they are not likely
to be willing (or able) to offer you much help.

I suggest you seek assistance in one or more of
the following newsgroups:

comp.crypto.burn.before.reading
alt.religion.kibology
comp.fortran.fossils
rec.swedish.chef.bork.bork.bork
comp.lang.c++
alt.tin.foil.helmets

Choose whichever seems most likely to be helpful, and
try your question there.

--
Eric Sosman
esos...@acm-dot-org.invalid
Thanks

May 30 '07 #4
sd****@gmail.com wrote:
Hi,
Can someone help me with an idea on how to start writing a C++ code
step 1: learn that C++ is a different language from C. Posts about C++
are not topical in <news:comp.lang.c>. The C++ newsgroup is
<news:comp.lang.c++>, but your post is about algorithms independent of
any language, so is not topical there either.
for generating
greatest common divisor and the linear combination of two intergers
represented as gcd(m, n)= mx + ny and adding them it will give us the
greatest common divisor and I need to use the extended Euclidean
algorithm.
I already have the code for the greatest common divisor but I dont
know how to do the linear combination.
The above makes no sense.
1) If you "have the code for the greatest common divisor" then you are done.
2) You _don't_ have the code for the greatest common divisor.

Here is a version of you code which
a) is legal C so is topical here
b) has a working (if not best) gcd() function.

Now, what was your question?

#include <stdio.h>

int gcd(int, int); /* notice return type */

int main(void)
{
int m = 0, n = 0;

puts("Welcome to the Greatest Common Divisor Program\n\n"
"Enter the first number: ");
scanf("%d", &m);
puts("\nEnter the second number: ");
scanf("%d", &n);
printf("gcd(%d,%d) =%d\n", m, n, gcd(m, n));
return 0;
}

int gcd(int m, int n)
{
if (!m || !n) return 0;
if (m < 0) return gcd(-m,n);
if (n < 0) return gcd(m,-n);
if (m < n) return gcd(n,m);
if (m%n) return gcd(n, m%n);
return n;
}

This is what I have:

#include <iostream>
#include <iomanip>
using namespace std;

void gcd(int, int);
void extended_gcd(int, int, int, int);

int main()
{
int m=0, n=0;

cout<<"Welcome to the Greatest Common Divisor Program\n\n";
cout<<"Enter the first number: ";
cin>>m;
cout<<endl;
cout<<"Enter the second number: ";
cin>>n;
cout<<endl;
cout<<"gcd("<<m<<", "<<n<<") = ";
gcd(m, n);
return 0;
}

void gcd(int m, int n)
{
int r, q, d;
while (n!=0)
{
r = m % n;
q = m / n;
r = m - n * q; // I was thinking on put it on the stack
but I dont know how
m = n;
n = r;
}

d = m;
cout<<d<<endl;
//then pop the stack as d=r-q*n
}
May 30 '07 #5

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: mudasirk | last post by:
actually i have recently started learning C++, i have my paper of C++ tommorow......so plz help me how 2 find GCD .......
12
by: Erik the Red | last post by:
In Fundamental Algorithms (The Art of Computer Programming), the first algorithm discussed is Euclid's Algorithm. The only idea I have of writing this in python is that it must involve usage of...
21
by: Frederick Gotham | last post by:
I'm trying to devise a compile-time constant for X, where X is the greatest number which satisfies both the following criteria: (1) X <= DESIGNATED_MAX_VALUE (2) X % Y == 0 I'll try to...
7
by: cess | last post by:
Hi!!! i would like to know if what is lacking in the codes below to have a greatest common denominator of two given(by the user) numbers?? I'm confused and i need your help! import java.io.*;...
0
by: sdlt85 | last post by:
Hi, Can someone help me with an idea on how to start writing a C++ code for generating greatest common divisor and the linear combination of two intergers represented as gcd(m, n)= mx + ny and...
2
by: 7asco | last post by:
i want the code of greater common divisor algorithm in c++
35
by: aarklon | last post by:
Hi all, The following question is asked frequently in interviews How to find the greatest of 2 numbers without using relational operators ? the solution i have seen is ( a+b + abs(a-b) )...
4
by: jmf777 | last post by:
Hi I'm trying to write a program to find the greatest common divisor of 2 numbers input by the user. This is what I got so far: #include <stdio.h> int gcd(int a, int b); int main(void) {
5
by: tejas2991 | last post by:
this is my gcd prog.. #include<iostream> using namespace std; int GCD(int ,int ); void main() { int x,y; cout<<"Plz enter the two numbers : "; cin>>x>>y;
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...
0
by: ryjfgjl | last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
0
by: taylorcarr | last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: aa123db | last post by:
Variable and constants Use var or let for variables and const fror constants. Var foo ='bar'; Let foo ='bar';const baz ='bar'; Functions function $name$ ($parameters$) { } ...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.