CODEWITHSUNDEEP
javafor-loop
asdfasdf
asdfasdf

Reputation: 11

Does Java have a limit on loop cycles?

I solved the Project Euler problem #14 https://projecteuler.net/problem=14 on Java, but when I run it in Powershell, it stops iterating at exactly i = 113383 every time. I rewrote the solution on python, and it works perfectly fine, albeit slowly. According to my (identical) python solution, the answer is that the number that produces the longest chain is 837799 and the chain is 524 operations long.

Why does the Java solution not finish the for-loop? Is there some kind of limit in Java on how long it can stay in a loop? I cannot come up with any other explanation. Java code below. I wrote the System.out.println(i) there just to see what is going on.

class ProjectEuler14 {

    public static void main(String[] args) {

        int largestNumber = 1;
        int largestChain = 1;
        int currentNumber;
        int chainLength;

        for (int i = 2; i < 1000000; i++) {
            System.out.println(i);
            currentNumber = i;
            chainLength = 0;

            while (currentNumber != 1) {
                if (currentNumber % 2 == 0) currentNumber /= 2;
                else currentNumber = 3 * currentNumber + 1;
                chainLength++;
            }

            if (chainLength > largestChain) {
                largestChain = chainLength;
                largestNumber = i;
            }

        }

        System.out.println("\n\nThe number under million that produces the "
                           + "longest chain is " + largestNumber +
                           " and the chain's length is " + largestChain);
    }
}

Upvotes: 1

Views: 157

Answers (3)

toto
toto

Reputation: 1188

Do you hava problem overflow int. Change int to long.

        long largestNumber = 1;
        long largestChain = 1;
        long currentNumber;
        long chainLength;

        for (int i = 2; i < 1000000; i++) {
            //System.out.println(i);
            currentNumber = i;
            chainLength = 0;

            while (currentNumber != 1) {
               
                //System.out.println("# = " + currentNumber);
                if (currentNumber % 2 == 0) {
                    currentNumber /= 2;
                } else {
                    currentNumber = (3 * currentNumber) +1 ;
                }
                chainLength++;
                
                 

            }

           // System.out.println("################################ " + i);
            if (chainLength > largestChain) {
                largestChain = chainLength;
                largestNumber = i;
            }

        }

        System.out.println("\n\nThe number under million that produces the "
                + "longest chain is " + largestNumber
                + " and the chain's length is " + largestChain);

Upvotes: 0

belwood
belwood

Reputation: 3779

The currentNumber is exceeding size of int, use long instead.

Upvotes: 1

rzwitserloot
rzwitserloot

Reputation: 103244

It's not the for loop. It's the while loop. The condition currentNumber != 1 is always true; forever.

In java, an int is specifically defined as an integral number between -2^31 and +2^31 -1, inclusive, and operations 'roll over'. try it!

int x = 2^31 -1;
x++;
System.out.println(x);

this prints a large negative number (in fact, precisely -2^31).

It's happening in your algorithm, and that's why it never finishes.

A trivial solution is to 'upgrade' to longs; they are just as fast, really (yay 64-bit processors!) and use 64 bits, thus giving them a range of -2^63 to +2^63-1.

Python sort of scales up its numbers into slowness silently, java makes different choices (and, for crypto and other purposes, that rollover thing is in fact desired).

If you want to go even further, you can always use BigInteger, which grows as much as you need forever (becoming slower and taking more memory as it goes).

To know rollover occurred, the 3* operation would then result in a number that is lower than the original, and you can check for that:

replace:

else currentNumber = 3 * currentNumber + 1;

with:

else {
    int newNumber = currentNumber * 3 + 1;
    if (newNumber < currentNumber) throw new IllegalStateException("Overflow has occurred; 3 * " + currentNumber + " + 1 exceeds ints capacities.");
    currentNumber = newNumber;
}

and rerun it. You'll see your app nicely explain itself.

Upvotes: 3

Related Questions