Explain the working of a program that prints the GCD and LCD of two numbers

Question

I know its very simple but I can't find out what the variable t is for.

int main() {
    int a, b, x, y, t, gcd, lcm;

    printf("Enter two integers\n");
    scanf("%d%d", &x, &y);

    a = x;
    b = y;

    while (b != 0) {
       t = b;
        b = a % b;
        a = t;
    }

    gcd = a;
    lcm = (x*y)/gcd;

    printf("Greatest common divisor of %d and %d = %d\n", x, y, gcd);
    printf("Least common multiple of %d and %d = %d\n", x, y, lcm);

    return 0;
}

If I remove the usage of variable t, the input has to be given in decreasing order (i.e. highest input first). If t is used everything works fine. I am very new to programming so please help.

t holds the value of b and then assigns it to a after a has been used in an expression to provide a new value for b. Think of t as a temp variable. — scartag, Mar 21 '13 at 07:00
It is to store temporaryly value of `b`... since `a` & `b` original values are used in at `b =a % b`... later `b` holds different value — Kiran, Mar 21 '13 at 07:05
Suggest perhaps you read up on [Euclid's Algorithm](http://en.wikipedia.org/wiki/Euclidean_algorithm) — WhozCraig, Mar 21 '13 at 07:15

score 2 · Accepted Answer · answered Mar 21 '13 at 07:18

2

This is Euclid's Algorithm for calculating the GCD.

 function gcd(a, b){
     while (b ≠ 0){
        t := b;
        b := a mod t;
        a := t;
      }
     return a
    }

This logic reduces the value of a and b. t is a dummy variable holding the value of b, while the next new value of b is being calculated. Which will be even less in magnitude. So eventually we will be able to terminate the algorithm with the required result.

answered Mar 21 '13 at 07:18

John Doe

2,752
5
40
58

does that mean the while loop runs again after calculating (b=a mod t) and if b=0.. – Mar 21 '13 at 07:23
1

Yes that is its purpose.When b is 0 we are left with the answer and we dont enter the while loop further. Please see http://en.wikipedia.org/wiki/Euclidean_algorithm. – John Doe Mar 21 '13 at 07:38
a mathematical equation c = (f-32) * 5/9; is correct and gives correct answers too but the same statement when written as c = 5/9 * (f-32); gives output as zero '0' for any input...why is that..? – Mar 21 '13 at 12:30
This is another question.Any way, I think this celsius Fahrenheit conversion program you are doing. Set the data type of the variables correctly i.e (make them float or in other words anything which accepts the floating point value) you will get the correct answer all the time. – John Doe Mar 21 '13 at 14:08
no i tried everything..it works only if its (f-32)*5/9..it doesnt work if its 5/9*(f-32)...if i use float i get the output as 0.0000 – Mar 21 '13 at 16:17
This is what I meant when I said use float. – John Doe Mar 22 '13 at 05:27
wow, that did the trick..using (5.0/9.0) Thnx....but what i want to know is why it didn't work when it was int...? – Mar 25 '13 at 04:43

score 1 · Answer 2 · answered Mar 21 '13 at 07:03

1

In this t is for temporary holding.

In this while loop a%b has to be set to b, and b's value has to be set to a. To avoid loss of b's value.

answered Mar 21 '13 at 07:03

Abin Manathoor Devasia

1,945
2
21
47

score 1 · Answer 3 · answered Mar 21 '13 at 07:07

Say you have 2 values - old 'a' and old 'b' (no 't').

The 'while' loop is supposed to update those values to new 'a' and new 'b'. Every recalculation of new 'a' requires old 'b', and every recalculation of new 'b' requires old 'a'. However, if you calculate 'b' first, it overwrites the old value and you can't calculate 'a' correctly. Same goes the other way around - recalculate new 'a', you lose the old value and can't use it to calculate 'b'. Therefore you need a temporary variable in which to store the old value of whichever variable ('a' or 'b') you recalculate first in an iteration, then use this cached value for calculating the other :) 't' is this temporary variable.

jxh · Answer 4 · 2013-03-21T07:42:55.180

The use of a temporary variable is a common programming idiom. It is used to hold a copy of a variable's value so that the value can be used later after the variable is updated with a different value. Perhaps the simplest use case is the swap, also known as exchange.

/* swap the values held by a and b */
t = b; /* t holds the value in b */
b = a; /* b gets the value in a */
a = t; /* a gets the value in t */

The logic of the while loop is not fundamentally different from the illustration above.

The algorithm that is implemented is Euclid's algorithm. It is based on the division theorem, which states that for positive a and b, there exists q such that a = q*b + r and 0 <= r < b. In C, r can be computed with a % b.

In the case that a is smaller than b, then a % b is a. So, the algorithm allows a and b to switch positions at the next iteration.

If you want a formulation of the algorithm without a temporary, you can use a circular buffer instead.

int r[3] = { a, b, a % b };
int i = 0;
while (r[(i + 2) % 3]) {
    ++i;
    r[(i + 2) % 3] = r[i % 3] % r[(i + 1) % 3];
}
gcd = r[(i + 1) % 3];

a mathematical equation c = (f-32) * 5/9; is correct and gives correct answers too but the same statement when written as c = 5/9 * (f-32); gives output as zero '0' for any input...why is that..? ive tried declaring it as float but still the answer is answer is same..intsead of 0 i get 0.0000 — , Mar 22 '13 at 02:34
@user2193932: http://stackoverflow.com/questions/4890480/converting-fahrenheit-to-celsius-in-c — jxh, Mar 22 '13 at 04:59

Anish Ramaswamy · Answer 5 · 2013-03-21T07:45:39.237

1

According to your program's logic,

Consider two numbers - 2 and 3.
To calculate the GCD,
1. Calculate 2 % 3. The result is 2 (which is not 0) so continue.
2. Calculate 3 % result => 3 % 2. The result is 1 (which is not 0) so continue.
3. Calculate 2 % result => 2 % 1. This answer is 0. Thus our GCD is the second number (i.e) 1.

So basically, your t helps you store the second number in each iteration so that in the next iteration, your first number (i.e. the number to the left of the '%' operator) was the previous iteration's second number. (I hope that didn't confuse the crap out of you)

All this is necessary because you're overwriting the second number in each iteration with the result of the '%' operation.

edited Mar 21 '13 at 07:45

answered Mar 21 '13 at 07:14

Anish Ramaswamy

2,326
3
32
63

does that mean the while loop runs again after calculating (b=a mod t) and if b=0.. – Mar 21 '13 at 07:29
@user2193932, No! If `b` is 0, the `while` loop condition fails which means it will not enter the loop. – Anish Ramaswamy Mar 21 '13 at 07:36
got it...thnx for the help. – Mar 21 '13 at 07:46

Explain the working of a program that prints the GCD and LCD of two numbers

5 Answers5