Finding the Greatest Common Denomenator

[mattig89ch]

Hidy ho all,

I just got an assignment where I have to find the Greatest Common denominator of 2 numbers that a user inputs.

My first idea on how to do this is to loop through both numbers to find which numbers between 0 and the inputed number, then store those numbers in a dynamic array, before finally comparing the two arrays to find which ones are equal.

Since I have no idea how many denomenators are in each array, I need to use a dynamic array. Now I'm coming to java from C++ so I know how to use vectors. My question is, are vectors able to be used in java? If so, where can I find more info on them?

[Norm]

The ArrayList class is commonly used to store varying amounts of data.

See the API doc: http://docs.oracle.com/javase/7/docs/api/

[mattig89ch]

Thanks for that link. I think I may have a way to do it w/out using arrays. Would someone mind checking my logic to see how right or wrong I am?

First the user inputs 2 numbers.

Next I check which of the 2 numbers is the biggest using an if else statement. If the first number is the biggest it gets stored in biggest variable and the second number is stored in a smaller variable, else the second number is stored in the biggest variable and the first is stored in the smaller variable.

Then I run the numbers through a loop with a counter in it. The first and second numbers are put through the % operator (firstNumber % counter, secondNumber % counter) so I can find where their remainders are 0. If the remainder is 0 on both of them, I then store the counter in a GCD variable and increment the counter by 1 (counter ++). This is done so long as the counter is less then the smaller number. Remember, I need to find the greatest common denominator of both numbers.

Finally, I output the GCD variable.

heres the code:

        if (firstInput > secInput)
        {
            largest = firstInput;
            smallest = secInput;
        }
        else
        {
            largest = secInput;
            smallest = firstInput;
        }
 
        do{
 
 
            firstResult = firstInput % counter;
            secResult = secInput % counter;
 
            if (firstResult == 0 || secResult == 0)
            {
                GCD = counter;
            }
 
        counter ++;
        }
        while (counter < smallest);
 
        System.out.println("The Greatest Common Denominator is: " + GCD);

[GregBrannon]

The preferred term is Greatest Common Factor (GCF) (or less precise, Greatest Common Divisor (GCD)).

I suppose your algorithm will work, but I'm not sure of the purpose of the counter. Store the number that results in a remainder of 0 for both numbers until a larger number is found to replace it.

There are more efficient ways to find the GCF which you can read about by searching the 'net.

[mattig89ch]

Right-o. I'm running the math through a do-while loop that terminates when the counter reaches the size of the smallest variable.

The counter both controls the loop and provides something to get the remainder from.

I entered 25 and 30. It spat back 15 as the gcd. So something is wrong.

[mattig89ch]

Ok, I still haven't been able to find where my problem is. Does anyone know where my logic is going bad?

[GregBrannon]

How are we supposed to help? Post the complete algorithm you've coded, preferably in a runnable example that demonstrates undesired results.

[mattig89ch]

I did acutally, but I'll post it again.

int firstInput = Integer.parseInt(JOptionPane.showInputDialog("Enter First number"));
        int secInput = Integer.parseInt(JOptionPane.showInputDialog("Enter Second number"));
        int GCD = 0, largest =0, firstResult =0, counter = 1, smallest = 0, secResult = 0;
 
        if (firstInput > secInput)
        {
            largest = firstInput;
            smallest = secInput;
        }
        else
        {
            largest = secInput;
            smallest = firstInput;
        }
 
        do{
 
 
            firstResult = firstInput % counter;
            secResult = secInput % counter;
 
            if (firstResult == 0 || secResult == 0)
            {
                GCD = counter;
            }
 
        counter ++;
        }
        while (counter < smallest);
 
        System.out.println("The Greatest Common Denominator is: " + GCD);

I put 25 and 30 into it. Now done by hand the GCD is 5, with the program I get 15 as a result. So I know thats not right. Trouble is, I don't know where I'm going wrong to make it right.

Edit: just in case it comes into question, I do have import javax.swing.*; at the very tippy top. It compiles fine, it gives no errors when it runs. The only problem seems to be the math.

[GregBrannon]

Add print statements to the do{} loop to see the results each time through. That may give you some insight into what's happening.

Hints: Your algorithm doesn't know when to stop, and the logic to assign GCD is wrong.

Edit: When checking a program, choose some simple functionality that you know should cause a result and test that. For example, build logic that presents a result for the GCF of 1. Though you may not have intended it, your current logic should work for 1, but it doesn't. Why not? Once you've gotten that working, then modify it so that 1 is the default answer, not a calculated answer. For 15 and 25, 2 should not be a GCF, so verify that that 2 is not presented as a result for 15 and 25, etc. Consider testing initially with two simple numbers like 3 and 3 and then increase the difficulty to see how your program responds.

[mattig89ch]

ok, I'm with you so far. I think.

its supposed to stop when the counter reaches the smallest number. And only assign anything to the GDC variable if the firstResult and secResult are both 0.

The print statement in the for loop (when the GCD is assigned to the counter) produced 1, 2, 3, 5, 6, 10, 15. I feel like I'm missing something in that for loop. Some other conditional statement that would say dont assign counter to gcd unless it produces whole numbers. Because when you do the math by hand, some of the results are decimals. Is there a way to say something like 'if first result and second result are 0 and whole numbers'?

[GregBrannon]

I feel like I'm missing something in that for loop.

Get in touch with your feelings. They're right.

As for your "whole numbers" comment, when would the % operator result in other than a whole number? I'm not sure that thinking is relevant here.

However, your question, "Is there a way to say something like 'if first result and second result . . ." IS relevant. What is the if() statement condition currently? Does it agree with your question?

This illustrates that it's often a good idea to write out what you want your code to do in your native language in code comments and then write code to match the comments. Your sense of what the if() condition should be is stated correctly in English above, but you didn't code it that way.

[mattig89ch]

As for your "whole numbers" comment, when would the % operator result in other than a whole number? I'm not sure that thinking is relevant here.

At this point, I'm getting decimals in my returns. no idea why. For example, if you divide 25 by 10 the result is 2.5. But when its saying that 25 % 10 = 0, so its storing 10 in GCD.

However, your question, "Is there a way to say something like 'if first result and second result . . ." IS relevant. What is the if() statement condition currently? Does it agree with your question?

At the moment its saying that if the firstNumber % counter = 0 AND secNumber % counter = 0 then store counter in the GCD variable. My understanding of these math equations is that firstNumber % counter finds the remainder. Is it possible for 25 % 10 to equal 0? Shouldn't it be 5 (20/10 = 2 with remainder of 5)?

[GregBrannon]

This is what it says unless you've changed your code and NOT posted an update:

if (firstResult == 0 || secResult == 0)

|| != AND

If you've updated your code, then post the update. It's impossible to help you with code we can't see and talking about old code and new code as though they're the same when they're not is a complete waste of time. I prefer you post the update in a new post so that the evolution of the code is clear and the conversation in between the updates makes sense.

[mattig89ch]

oooooohhhhhhh, thats where the problem is then. I thought that || meant and. um....what does it mean?

Edit: just updated the code, 25 and 30 now produce a result of 5! Woo! Thanks for your help my good man!

Now to test some other numbers to see if there are other problems.

[GregBrannon]

Good! Keep pluggin'.