CODEWITHSUNDEEP
c++intdivisionmodulo
Matt
Matt

Reputation: 723

Simple Modulo Operations

So I am learning C++, and in one of the books I'm reading, there is an example for finding GCF (greatest common factor). The function is as follows:

int gcf(int a, int b) {
    if(b == 0) {
        return a;
    }
    else {
        return gcf(b, a%b);
    }
}

What I don't understand is that if I put in 15 and 5 for example, then

a = 15
b = 5
b is not 0 so then the else statement executes
(5, 15%5 = 0) so since b is now 0 it returns, a, which is 5.

That makes sense, but if I reverse the numbers, why/how do I get the same answer?

a = 5
b = 15
b is not 0 so then the else statement executes
(15, 5%15) but 5%15 is .3 or 1/3, but in C++, 5%15 returns 5.

I don't understand where 5 comes from, if anything, since it's an integer, I thought it maybe return 0 but it doesn't return 15, so it can't be.

Upvotes: 0

Views: 687

Answers (4)

Cerin
Cerin

Reputation: 63

If you are interested, the piece of code you have written there is called Euclid's Algorithm which is based upon Euclid's Lemma (big surprise there). Although I heard from a professor that some people might refer to different formulations of Euclid's Lemma. My Higher Algebra book particularly refers to it as "Equal gcd's". It states:

Let a, b, q, and c be integers with a=qb+c. Then gcd(a,b)=gcd(b,c)

gcd(a,b) refers to the greatest common divisor of a and b. This seems to be precisely what you are doing in your program.

Any integer a can be written as the qb+c for any b. This means that a is a product qb plus some remainder c. The remainder here is what you are calculating when you use the % operator. If we let a = 12 and b = 5 then can write 12=5q+c. Let q be 2. Then our remainder c is 2. Perhaps these things are elementary but hopefully this is nice background to supplement your book's explanation.

Upvotes: 0

Sufian Latif
Sufian Latif

Reputation: 13356

What you're doing is integer calculation - no floating points or fractions involved.

5 % 15 is actually the remainder you get after dividing 5 by 15, and that is, of course, 5 (the quotient would be 0).

15 |  5 | 0   <-- this is the first call gcf(5, 15)
      0
     ---
      5 | 15 | 3  <-- this is the first recursive call gcf(15, 5)
          15
         ---
           0 |  5 |   <-- this is the second recursive call gcf(5, 0), returns 5

Upvotes: 3

ken
ken

Reputation: 836

Modulo operator is different from division,usually when we divide the return value is a quotient but when you use modulo operator return value is its reminder. so in your case when

**

a=5 and b = 15, a%b the return value of this was 0 ,

**

that is the reason why it returned 5. check the following links for greater clarity on modulo operator http://www.cplusplus.com/doc/tutorial/operators/

http://www.cprogramming.com/tutorial/modulus.html

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490178

In integer division, 5/15 = 0. Since 5%15 is the remainder, it needs to be 5. C and C++ mandate that for any a and b, a/b*b + a%b = a.

Upvotes: 0

Related Questions