programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Loop/Boolean question

Eddie Gerlach
Greenhorn
Posts: 22
Hi!

I'm teaching myself Java w/Dr. Liang's Intro to Java, 9th Ed., Comprehensive.....Chapter 4, Loops....in attempting to find the greatest common divisor (gcd) of two integers, n1 and n2, whereas k is a possible gcd and gcd is initialized to 1, the following code has been entered:

for (int k = 2; k <= n1 && k <= n2; k++) {
if ( n1 % 2 == 0 && n2 % 2 == 0)
gcd= k;
}

When asked to change the previous line of code to this:

for (int k = 2; k <= n1 / 2 && k < n2 / 2; k++){

the questions states this revision is wrong and to find the reason.....well, I've changed it, entered "3" (per the answer key) for n1 and n2....

now I can see logically where k (2 in this example) is not <= n1/2, which is 3/2 or 1, since we're dealing w/integers, yet when I compile and run, my answer is indeed, gcd = 1. However, since this is a Boolean expression where && is being used, since the first portion evaluates to "false", the 2nd portion isn't executed and thus my result of 1?......sorry, loops are throwing me for one, for sure....can someone clarify, please?

Thanks!

Knute Snortum
Sheriff
Posts: 4289
127
I'm confused by your question. Could you post the actual, working code, with code tags, so we can see what's happening? As you've described it, I don't see how k could be 1.

Winston Gutkowski
Bartender
Posts: 10575
66
Knute Snortum wrote:I As you've described it, I don't see how k could be 1.

We also don't know what the values of n1 and n2 are. [Edit: Duh. Of course we don't. Forget I wrote that. ]

Are you familiar with Euclid's algorithm? Because the way they've shown you seems very primitive.

But it could be that they're trying to show you some good stuff about for loops first, so don't worry too much about it.

Winston

Eddie Gerlach
Greenhorn
Posts: 22
Winston,...he shows a link to that in the book.. however, I haven't looked at it yet...and will try not to worry too much.... ;)

here's the exercise...
import java.util.Scanner;

public class Listing4_9GreatestCommonDivisor {
//** Main method */
public static void main(String[] args) {
//Create a Scanner
Scanner input = new Scanner(System.in);

//Prompt the user to enter two integers
System.out.print("Enter first integer: ");
int n1 = input.nextInt();
System.out.print("Enter second integer: ");
int n2 = input.nextInt();

int gcd = 1; //initial gcd is 1

for (int k = 2; k <= n1/2 && k <= n2/2; k++) {
if (n1 % k == 0 && n2 % k == 0)
gcd = k; //update gcd

}

System.out.println("The greatest common divisor for " + n1 +
" and " + n2+ " is " + gcd);
}
}

So I ran the program in NetBeans, entered 3 for both integers and my gcd was 1, yet was told the current 'for' loop was wrong by illustration....if one takes out the "/2" in the for loop, then it's correct.....yet I come up with the same answer w/o '/2' and if I used a 'while' loop as follows;

while (k <= n1 && k <= n2) {
if (n1 % 2 == 0 && n2 % 2 == 0)
gcd = k;
k++;

Hope this helps and illustrates things a bit better for everyone...

Winston Gutkowski
Bartender
Posts: 10575
66
Eddie Gerlach wrote:now I can see logically where k (2 in this example) is not <= n1/2, which is 3/2 or 1, since we're dealing w/integers, yet when I compile and run, my answer is indeed, gcd = 1.

Right. So the question is: can you think of ANY two values for n1 and n2, where 2 is less than or equal to n1/2 and less than n2/2, and the answer should NOT be 1? I can think of 1 (actually, 2 now that I've read the post correctly ).

Hint: I think they've deliberately made the question difficult by putting k on the left-hand side of the expression because, for most people, it's not the way we think (well, not me). So, to help you out (maybe):
k <= n1/2 can be rewritten as n1/2 >= k
k < n2/2 can be rewritten as n2/2 > k

you should also remember that these are conditions for continuing the loop, so if either of them is false when k=2, the loop will never get executed.

HIH

Winston

Eddie Gerlach
Greenhorn
Posts: 22
Winston,

thanks for the follow-up, but if I enter 3 and 6 (which means the answer should be 3 as the gcd), I still get 1.....however, when I enter 125 and 2525, I get 25....so it works part of the time....hmmmm, when I remove the divisor '/2' from both sides of the Boolean expression, I come up with 3.....I've done something foul and need to re-examine my code...God, I love and hate this all at the same time..

Eddie Gerlach
Greenhorn
Posts: 22
• 1
Gosh, I'm a boob....the gcd of 3 and 3 is 3, not 1! Went back and examined my code.....when I enter the '/2' divisor in the 'for' loop and re-evaluate, it's an incorrect process to determine the "%" remainder, yes? swimming, swimming, swimming.....

Winston Gutkowski
Bartender
Posts: 10575
66
Eddie Gerlach wrote:Gosh, I'm a boob....the gcd of 3 and 3 is 3, not 1! Went back and examined my code.....when I enter the '/2' divisor in the 'for' loop and re-evaluate, it's an incorrect process to determine the "%" remainder, yes? swimming, swimming, swimming.....

Well done! That's what programming is about.

Winston

Emil Jennings
Ranch Hand
Posts: 75
1
The issue, as I see it, is in your conditions. Using n1 = 24 and n2 = 16:

The gcd will be 16, which we know isn't correct, it's 8. However, when k reaches 16:
k <= n1 && k <= n2 is true because k = 16 and 16 <= 24 and 16 <= 16
and
n1 % 2 == 0 && n2 % 2 == 0 is also true because 24 % 2 is 0 and 16 % 2 is 0.

So gcd becomes 16. On the next iteration k becomes 17 and the loop stops because k > n2.

Using

The gcd will be 7, which we know isn't correct, it's still 8. However, when k reaches 7:
k <= n1 / 2 && k < n2 / 2 is true because 7 <= 24 / 2 <= 12 and 7 < 16 / 2 <= 8
and
n1 % 2 == 0 && n2 % 2 == 0 is also true because 24 % 2 is 0 and 16 % 2 is 0.

So gcd becomes 7. On the next iteration k becomes 8 and the loop stops because k = n2.

Take what you know from the problem:
The user is entering two numbers, so you don't know which is larger.
At a minimum, a gcd will start with 1, so 1 can be used to start the for loop.
If the index for the for loop is greater than the smaller number then it cannot be a gcd.

What does this mean to do:
Determine the smaller of the two numbers.
Start your for loop at 1.
Stop the for loop when its index equals the smaller number.

Make sense?

Piet Souris
Master Rancher
Posts: 2044
75
hi Emil,

thanks for the comprehensive explanation. Before Eddie replies, can you explain me
the following, for that's where I get lost:

1) you write "So gcd becomes 7. On the next iteration k becomes 8 and the loop stops because k = n2. "

Now, isn't n2 equal to 16 in your example? See above the first code.

2) in your second code, line 02, I see:

Can you explain why both n1 and n2 must be even for gcd to be increased? For example, if n1 = 22
and n2 = 11, do I get: gcd = 11?

Greetz,
Piet

Winston Gutkowski
Bartender
Posts: 10575
66
Piet Souris wrote:2) in your second code, line 02, I see:...

@Emil: Piet got in before me, but that code is wrong. Eddie's code says
if ( n1 % k == 0 && n2 % k == 0) { ...
and k is incremented every time, so you can't assume a constant.

Nevertheless, you get a cow for effort!

Winston

Eddie Gerlach
Greenhorn
Posts: 22
Emil n Piet,

From what I can gather, 'while' these two conditions exist, AND if (n1 % k == 0 && n2 % k == 0), then 'k' is incremented by 1...since it started at 2, shouldn't it then be incremented by 1 and then gcd is 3? However, since this is a Boolean statement that requires the first statement to evaluate as true, and if it doesn't, it ignores the 2nd condition? Then the loop starts anew until a new value is stored for gcd (or 'k') or k becomes >= n1 or n2?

Sorry, but noobie brainfarts and perhaps a bit "loop"y...

Eddie

Eddie Gerlach
Greenhorn
Posts: 22
Winston,

Thanks for catching that...I was simply reading from my textbook and I could've entered the code incorrectly....

Emil Jennings
Ranch Hand
Posts: 75
1
Hi Piet,

Given:
n1 = 24
n2 = 16

In the second example, using the OPs code:

As the loop iterates and k becomes 7, the condition in the for loop, k <= n1 / 2 && k < n2 / 2, essentially becomes:
k = 7
n1 = 24
n2 = 16
k <= n1 / 2 && k < n2 / 2
7 <= 24 / 2 && 7 < 16 / 2
7 <= 12 && 7 < 8
The condition is true, so go into the loop body, where we see

which is
24 % 2 = 12 remainder 0 and 16 % 2 = 8 remainder 0
This condition is true so k (which is 7) is being assigned to gcd. On the next iteration, k is 8 and the second part of the loop condition (k < n2 / 2) is false because 8 is not less than 8. So gcd remains at 7.

In my example, n2 is always 16, but the second part of the loop condition is k < n2 / 2 which is the same as k < 16 / 2 which is the same as k < 8. I should have wrote:
"So gcd becomes 7. On the next iteration k becomes 8 and the loop stops because k = n2 / 2."

For your second question, n1 and n2 don't have to be even, however when one is not even such as your example of 22 and 11, the gcd will always be its initialized value because one of the n1 % 2 == 0 && n2 % 2 == 0 conditions will be false. I was refering to the OPs code to illustrate where the issues with the conditions are (hence, gcd's of 16 and 7 when they should be 8).

Emil Jennings
Ranch Hand
Posts: 75
1
@Winston I was addressing issues in the original post. Simple fixes can be made when the problem is understood better and logic problems are identified. In the case of the original code, it can be greatly simplified to come up with the correct answer.

Winston Gutkowski
Bartender
Posts: 10575
66
Emil Jennings wrote:@Winston I was addressing issues in the original post.

Quite right. I was looking at the second post, where it had been corrected.

Winston

Winston Gutkowski
Bartender
Posts: 10575
66
Eddie Gerlach wrote:Winston,
Thanks for catching that...I was simply reading from my textbook and I could've entered the code incorrectly....

Well, if your second post is from your textbook then it looks like you got it right. It should be:
n1 % k == 0 && ...

Winston

Emil Jennings
Ranch Hand
Posts: 75
1
Eddie,
'while' these two conditions exist, AND if (n1 % k == 0 && n2 % k == 0), then 'k' is incremented by 1...since it started at 2, shouldn't it then be incremented by 1 and then gcd is 3?

Yes
since this is a Boolean statement that requires the first statement to evaluate as true, and if it doesn't, it ignores the 2nd condition?

Yes
Then the loop starts anew until a new value is stored for gcd (or 'k') or k becomes >= n1 or n2?

Yes

Sorry, but noobie brainfarts and perhaps a bit "loop"y...

No need to be sorry, we're all here to learn...as long as you understand it then everything is good to go.

Eddie Gerlach
Greenhorn
Posts: 22
Sorry for my confusion, ya'll....went out for a run to clear my head...I think it may have helped....

the original code used a while loop:

int gcd = 1; // initial gcd is 1
int k = 2; //possible gcd
while (k <= n1 %% k <= n2) {
if ( n1 % 2 == 0 && n2 % 2 == 0)
gcd = k;
k++;
}

I then replaced it with a for loop:

int gcd =1; //initial gcd is 1
for (int k = 2; k <= n1 && k <= k2; k++) {
if (n1 % k == 0 && n2 % k == 0)
gcd = k;
}

Finally, when asked to insert the "/2" into the loop-continuation-condition, I was instructed that this is wrong and was asked why..(in the book)

for (int k =2; k <= n1 / 2 && k <= n2 / 2 ; k++) {
if (n1 % k == 0 && n1 % k == 0)
gcd = k;

For all 3 conditions, when I used the example 125 and 2525, gcd = 25...so this obviously left me wondering why the 3rd set of code was incorrect...however, when I enter 3 and 3 for the 3rd set of code, gcd is 1....it should be 3, correct? Same goes for 2 and 2..gcd should be 2, not 1...Hence my inquiry here...

BTW, Emil, when I take your parameters (n1 = 16 and n2 = 24) into the 3rd set of code, my answer is indeed 8...so there is my nightmare, folks.... isn't this fun?!

Appreciate the assistance everyone.
.....swimming, swimming, swimming.....

Eddie Gerlach
Greenhorn
Posts: 22
See what I mean? Even in my reply, I'm not coding correctly, (k2 instead of n2) but can see where the issue is...in my fat fingers!

Thanks again everyone for your help! Taking a break and will be back at it tomorrow..

Cheers!

Winston Gutkowski
Bartender
Posts: 10575
66
Eddie Gerlach wrote:From what I can gather, 'while' these two conditions exist, AND if (n1 % k == 0 && n2 % k == 0), then 'k' is incremented by 1...since it started at 2, shouldn't it then be incremented by 1 and then gcd is 3? However, since this is a Boolean statement that requires the first statement to evaluate as true, and if it doesn't, it ignores the 2nd condition? Then the loop starts anew until a new value is stored for gcd (or 'k') or k becomes >= n1 or n2?

I have a feeling you're overthinking this and getting caught up in the code.

Go back to basics and FORGET about Java: Given two numbers, n1 and n2, what is gcd(n1, n2)? What does it mean?
Why, for example is gcd(24, 16) == 8? Explain it in English.

Now, back to Java. Your starter for 10:
If x % y == 0, and both x and y are integers, what does that mean?

Now, taking that knowledge, go back and look at the algorithm from your second post (the one from your book; not your change), using
for (int k = 2; k <= n1 && k <= n2; k++) {   (ie, forget the '/2')

What is it trying to do? Try and describe it; if need be, get some paper and pencil and try it out with 16 and 24.

As it happens, the version with the '/2' is very nearly correct. It's missing only a couple of checks (oddly enough, one of the the combinations you tested with is one of them, which actually makes it a very good "corner" case ).

See if you can work out what those checks are.

Winston