Euclid's Method

[lotus18]

Hello experts

The Euclid's Method:

If u is greater then v then the greatest common divisor of u and v is the sum as the greatest common divisor of v and u-v.

Now my question is, how can I apply this method in getting the right answer for the following inputs:

Inputs:

Numerator: 4
Denominator: 6

The result must be:

4/6 = 2/3

Even a simple program will do. Please help. Thanks.

[oler1s]

So, what have you tried? Where's your code? We aren''t going to do your homework for you.

[lotus18]

Here's the code:

gcd(u, v) = gcd(v, u mod v) 
// calculate gcd
template <int u, int v>
struct gcd
{
    enum { value = gcd<v, u % v>::value };
};
 
template <int u>
struct gcd<u, 0>
{
    enum { value = u };
};
 
template <>
struct gcd<0, 0>
 
{
    enum { value = -1 };
};
 

[oler1s]

Right, so I see the work you have done. Oh wait, something isn't right here. It looks like you got it from: here.

We can see your utter lack of interest and effort, and moreover, from our mentality and experience, we can spot homework questions and copied answers. We don't spend time on the forums doing other people's homework.

It's also against the forum rules. Here it's explicit. Other forums may be more implicit in this rule. Either way, you're on your own.

[lotus18]

Right, so I see the work you have done. Oh wait, something isn't right here. It looks like you got it from: here.

We can see your utter lack of interest and effort, and moreover, from our mentality and experience, we can spot homework questions and copied answers. We don't spend time on the forums doing other people's homework.

It's also against the forum rules. Here it's explicit. Other forums may be more implicit in this rule. Either way, you're on your own.

Yes you're right. I only have a little knowledge in c++ and I have no time to understand and learn it by myself. Could you explain to me how do these codes work?

[oler1s]

I could, but I won't. Neither will other professionals. We come here to help people who genuinely want to learn. Not assist you in getting by your assignment. Sorry, but you have no sympathy from us.

[lotus18]

I could, but I won't. Neither will other professionals. We come here to help people who genuinely want to learn. Not assist you in getting by your assignment. Sorry, but you have no sympathy from us.

Sorry sir

OK, I'll do my assignment with my own. Can you help me If I try to build a code with my own? Thanks for your remarkable reminder. Don't worry sir I'll try to learn this language and I assure you that :)

Thanks for reply sir

Regards

Rey Sean

[lotus18]

Hi oler1s

I came up with these codes with the help of my friend

#include<iostream.h>
void main()
 
 
    {
        int numerator, denominator, temp, tempnum, tempden, final1, final2;
        cout<<"This program demostrates how to get the Greatest Common Denominator (GCD)\n";
        cout<<"\n\n";
        cout<<"Enter first number (numerator): ";
        cin>>numerator;
        cout<<"Enter second number (denominator): ";
        cin>>denominator;
 
 
        if(numerator<denominator)
        { 
            temp=numerator;
            tempnum=numerator; //temporary storage for numerator
            numerator=denominator; 
            tempden=denominator; //temporary storage for denominator
            denominator=temp;
        //}
        //else
        //{
        //    final1=numerator/denominator;
        //    cout<<final1;
        //}
        while(denominator!=0)
        {
            temp=numerator%denominator;
            numerator=denominator;
            denominator=temp;
        }
        cout<<endl;
        cout<<"The GCD is:"<<numerator<<endl;
        final1=tempnum/numerator;
        final2=tempden/numerator;
        cout<<"The numerator is: "<<final1<<endl;
        cout<<"The denominator is: "<<final2;
        cout<<endl;
        cout<<endl;
        cout<<tempnum<<"/"<<tempden<<" = "<<final1<<"/"<<final2<<"\n\n";
        }
        else
        {
            //final1=numerator/denominator;
            //cout<<final1<<endl;
            temp=denominator%numerator;
            cout<<temp<<endl;
        }
    }
 
 

Now, my problem is... how can I get the answer if the numerator is greater than denominator? For instance, 6/4 = 1 1/2. Any algorithm please. Thank you in advance.

[oler1s]

I'm not entirely sure you understand Euclid's method. It isn't a method of division. It's a way of finding an integral divisor that is common to two numbers. The GCD to be precise. It does not involve division. Only taking the remainder over and over.

This isn't a numerator/denominator issue. There is no fraction here. There is no straight division. You aren't dividing the numbers. And if your answer is an integer greater or equal to 1, then it obviously is wrong.

So I suggest you take a look at the Euclid's algorithm again. And understand it.

[oler1s]

Oh, I see what you're trying to do. But it's still messy, and complicated, and I'm not sure what is going on. I think the idea is to reduce a fraction to it's simplified form (i.e. reduce the numbers). So if you have a numerator of 6 and denominator of 4, the gcd is 2 and 6/2 = 3 and 4/2 = 2.

Euclid's algorithm doesn't care about the relative magnitude of the two numbers. If for gcd(a,b), a>b or b>a, it doesn't matter.

The only if/else statement you need is to make sure both a and b are greater than 0. Once you do that, just run euclid's algorithm to get a gcd, and divide the numerator and denominator by the gcd to get the simplified fraction. The GCD is obviously going to be equal to or smaller than the smaller of both numbers. So you don't have to write messy code that deals with numerator > denominator, and denominator > numerator.

[lotus18]

OK I'll do it. Thanks for your reply : )

[lotus18]

I'd just scanned the euclid's algorithm without understanding it. All I thought that euclid's algorithm is only used for reducing fraction to its simplest form and it doesn't care about for gcd(a,b), a>b or b>a.

Here's my latest codes yes it's still messy. I want to create a function but I don't know how to do it right now.

#include<iostream.h>
void main()
 
 
    {
        int numerator, denominator, temp, tempnum, tempden, final1, final2;
        cout<<"This program demostrates how to get the Greatest Common Denominator (GCD)\n";
        cout<<"\n\n";
 
        rey:
            cout<<"Enter first number (numerator): ";
            cin>>numerator;
            cout<<"Enter second number (denominator): ";
            cin>>denominator;
 
            if (numerator==0||denominator==0)
            {
                cout<<"The numerator or the denominator cannot be zero value.\n\n";
                goto rey;
            }
            else
            {
                if(numerator<denominator)
                { 
                    temp=numerator;
                    tempnum=numerator; //temporary storage for numerator
                    numerator=denominator; 
                    tempden=denominator; //temporary storage for denominator
                    denominator=temp;
                while(denominator!=0)
                {
                    temp=numerator%denominator;
                    numerator=denominator;
                    denominator=temp;
 
                }
                cout<<endl;
                cout<<"The GCD is:"<<numerator<<endl;
                final1=tempnum/numerator;
                final2=tempden/numerator;
                cout<<"The numerator is: "<<final1<<endl;
                cout<<"The denominator is: "<<final2;
                cout<<endl;
                cout<<endl;
                cout<<tempnum<<"/"<<tempden<<" = "<<final1<<"/"<<final2<<"\n\n";
                }
            }
        }