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:

# question on loop logic

Haani Naz
Greenhorn
Posts: 23
Hi guys,

Reading up on some the loops to get a firm understanding. Can somebody please clarify the following for me:

In the following examples which do you think best decribes the result:
result: will finish
result: sometimes runs forever
result: unknown

(1).

The above looks like it will finish.

(2).

(3).

I'm struggling with the last two. Can somebody shed some light on this? thanks.

Zeeshan Sheikh
Ranch Hand
Posts: 144
(2.)

(3).

It all depends whats the value of n is ??? Try different values and you will see how loop reacts accordingly.

Jeff Verdegan
Bartender
Posts: 6109
6
Haani Naz wrote:Hi guys,

Reading up on some the loops to get a firm understanding. Can somebody please clarify the following for me:

In the following examples which do you think best decribes the result:
result: will finish
result: sometimes runs forever
result: unknown

"Unknown" and "sometimes runs forever" seem to be the same thing to me. In either of those, the loop might or might not finish.

(1).

The above looks like it will finish.

There is exactly one case where it will run forever.

(2).

What do you think, and why?

(3).

What do you think, and why?

I'm struggling with the last two. Can somebody shed some light on this? thanks.

I'm sure somebody will be happy to help, if you ShowSomeEffort.(⇐click) At least make an attempt, and explain your thoughts and where you get stuck.

Jeff Verdegan
Bartender
Posts: 6109
6
I will say, though, that the last one looks like it might be the Collatz conjecture.

Haani Naz
Greenhorn
Posts: 23
Jeff Verdegan wrote:I will say, though, that the last one looks like it might be the Collatz conjecture.

Thanks did a look up on that and i found my answer. Will focus on the 2nd one now!

Jeff Verdegan
Bartender
Posts: 6109
6
Haani Naz wrote:
Jeff Verdegan wrote:I will say, though, that the last one looks like it might be the Collatz conjecture.

Thanks did a look up on that and i found my answer. Will focus on the 2nd one now!

Be careful though. If you start Collatz with, say 987654321 on paper you will NOT get the same next value as you will in Java.

Also, did you figure out the case where the first one never finishes?

Haani Naz
Greenhorn
Posts: 23
Jeff Verdegan wrote:
Haani Naz wrote:
Jeff Verdegan wrote:I will say, though, that the last one looks like it might be the Collatz conjecture.

Thanks did a look up on that and i found my answer. Will focus on the 2nd one now!

Be careful though. If you start Collatz with, say 987654321 on paper you will NOT get the same next value as you will in Java.

Also, did you figure out the case where the first one never finishes?

Nah Jeff, i can't seem to figure it out. feel kinda stupid now lol.

Rob Spoor
Sheriff
Posts: 21135
87
Jeff Verdegan wrote:

(1).

The above looks like it will finish.

There is exactly one case where it will run forever.

I thought this was impossible, but you're actually right. The <= is the key to the running forever here, and it would be caused by int overflow.

Haani Naz
Greenhorn
Posts: 23
So i believe the 2nd one (below) will finish. Seeing how n only increments by 1 and i will multiplication of its own value - at some point it will be greater than n. I am right correct?

Campbell Ritchie
Marshal
Posts: 56598
172
Go through the execution with pencil and paper for 32 iterations and tell us the values of i and n at that stage. Then work out whether the loop will terminate.

Campbell Ritchie
Marshal
Posts: 56598
172
Jeff Verdegan wrote: . . . If you start Collatz with, say 987654321 on paper you will NOT get the same next value as you will in Java. . . .
What does that mean about its terminating in Java™?

Haani Naz
Greenhorn
Posts: 23
Campbell Ritchie wrote:What about No 2: What if you start with n = 2000000000;? What will happen then?
Go through the execution with pencil and paper for 32 iterations and tell us the values of i and n at that stage. Then work out whether the loop will terminate.

I did one better, i ran the program. At the end:

i was 2147483648
n was 2000000031

So it would finish?

Campbell Ritchie
Marshal
Posts: 56598
172
Haani Naz wrote: . . .
i was 2147483648
n was 2000000031 . . .
How did you get 2147483648? There is no such int. Have you missed out a -?

Campbell Ritchie
Marshal
Posts: 56598
172
Haani Naz wrote: . . . I did one better, i ran the program. . . .
I still think a pencil and paper would have been better. I also think you only ran it 31 times. Without running the program again, work out what the value of i would be after 32 iterations. Then you can work out whether the loop will terminate.

Jeff Verdegan
Bartender
Posts: 6109
6
Campbell Ritchie wrote:
Jeff Verdegan wrote: . . . If you start Collatz with, say 987654321 on paper you will NOT get the same next value as you will in Java. . . .
What does that mean about its terminating in Java™?

It means that since Collatz in Java produces a different sequence than "true" Collatz, we can't assume it will behave the same way in terms of how or if it terminates.

Jeff Verdegan
Bartender
Posts: 6109
6
Haani Naz wrote:
Jeff Verdegan wrote:
Also, did you figure out the case where the first one never finishes?

Nah Jeff, i can't seem to figure it out. feel kinda stupid now lol.

You understand that it will finish when i > n, right? So what is the situation in which int i > int n can never be true, no matter how many times we increment i?

Jeff Verdegan
Bartender
Posts: 6109
6
Actually, there's on potential snag in my reasoning so far. I've been assuming that i and n are Java ints, or at least Java primitive integers (byte, int, char, long). If they're not, then the picture changes. I still think they are, but the fact that the code doesn't show them declared and that it's worded as "any positive integer" makes me wonder if the author of the question is trying to be overly clever. (Or maybe I am. )

I'm going to continue on the assumption that we're talking about Java primitive integers, as that would be the most sensible way to test someone's understanding of Java looping. Just be aware that there is that possibility of a tiny loophole that could change the answers.

Haani Naz wrote:
In the following examples which do you think best decribes the result:
result: will finish
result: sometimes runs forever
result: unknown

(1).

Jeff Verdegan
Bartender
Posts: 6109
6
Haani Naz wrote:So i believe the 2nd one (below) will finish. Seeing how n only increments by 1 and i will multiplication of its own value - at some point it will be greater than n. I am right correct?

Yes, it will finish, but your reasoning applies more to actual integers than to Java ints or longs. (And, like I said, unless you come back and tell me otherwise, I'm going to assume we're dealing with Java primtives here.)

One very simple way to answer this question is to keep in mind that multiplying an int by 2 is the same as doing a bitwise left-shift of 1.

Think about what happens to the bit pattern when you do that. Better yet, follow Campbell's suggestion and work it out on pencil and paper. Do it with a single 8-bit byte to make your life simpler.

Haani Naz
Greenhorn
Posts: 23
Jeff Verdegan wrote:
Haani Naz wrote:So i believe the 2nd one (below) will finish. Seeing how n only increments by 1 and i will multiplication of its own value - at some point it will be greater than n. I am right correct?

Yes, it will finish, but your reasoning applies more to actual integers than to Java ints or longs. (And, like I said, unless you come back and tell me otherwise, I'm going to assume we're dealing with Java primtives here.)

One very simple way to answer this question is to keep in mind that multiplying an int by 2 is the same as doing a bitwise left-shift of 1.

Think about what happens to the bit pattern when you do that. Better yet, follow Campbell's suggestion and work it out on pencil and paper. Do it with a single 8-bit byte to make your life simpler.

i actually stole this question off a python quiz. Was trying to understand the general implications.

Campbell Ritchie
Marshal
Posts: 56598
172
Never mind where the question came from, you have at least two things you haven’t worked out.
• 1: Assuming i and n are Java™ ints, under which circumstances will i <= n always be true?
• 2: Under the same assumption, what do you get if you double one, 32 or more ×?
•
 It is sorta covered in the JavaRanch Style Guide.