Why Does This Java Function Crash?

Question

I have a simple Java method, which is suppose to compute a list of prime divisors of a certain number.

public class Factors {



public static List<Integer> fac(List<Integer> factors, int number) {
    if(number < 2) {
        throw new IllegalArgumentException("Number must be greater than one");
    }


    for (int i = 2; i <= number; i++) {
        while (number%i == 0) {
            factors.add(i);
            number /= i;
        }
    }
    return factors;
}
public static void main(String [] args)
{
final long startTime = System.currentTimeMillis();

    ArrayList<Integer> factors = new ArrayList<>();
    System.out.println(fac(factors, 2147483647));

final long endTime = System.currentTimeMillis();
System.out.println("Total execution time: " + (endTime - startTime) );
}
}

This code works fine, except you feed Integer.MAX_VALUE into it; in that case giving:
java.lang.OutOfMemoryError: Java heap space
Initially, I thought, that this is due to, that ArrayList initialization was inside a method, but after removing, the same error persists.
Moreover, this:

public static List<Long> facrec2(List<Long> list, long number) {
    if (number < 2) {
        return list;
    }

    if (number == 2) {
        list.add(2L);
        return list;
    }

    for (long i = 2; i <= number; i++) {
        while (number % i == 0) {
            number /= i;
            list.add(i);
            return facrec2(list, number);
        }
    }
    return null;
}

method works for max values (after changing signature to Integer, works for Integer max value too). Logic of both suppose to be the same, only recursive implementation of the second makes the difference...

+1. I think you could have done a better job debugging (or at least demonstrating your debugging), but it's surprisingly subtle how this bug leads to this exception. — ruakh, Oct 19 '16 at 23:19
Yes, but I got both function from someone else, just as an example, and impatiently posted on stackoverflow, instead of get myself to work:) — , Oct 19 '16 at 23:44
`Logic of [iterative and recursive handling of any given trial divisor supposed] to be the same` - with recursion, you _never_ get to increment (and re-check) `i` after discovering `i` divides what's left of `number`. — greybeard, Oct 20 '16 at 05:23

score 1 · Answer 1 · edited Oct 19 '16 at 23:13

1

for (int i = 2; i <= number; i++) {

The problem is here. If number == Integer.MAX_VALUE this loop will never terminate. Once i gets to Integer.MAX_VALUE, the next increment sets it to Integer.MIN_VALUE, which is very negative, and the loop continues to execute, so you will keep adding to the list forever and run out of memory.

The simplest solution is to change the loop condition to < and handle the case where number still has its original value separately (i.e. the case where number is prime). You can also exit the loop once number == 1.

edited Oct 19 '16 at 23:13

ruakh

175,680
26
273
307

answered Oct 19 '16 at 23:05

user207421

305,947
44
307
483

1

+1. Note that when `i` gets to `Integer.MAX_VALUE`, `number` gets set to `1`; but since `i` gets set to `Integer.MIN_VALUE` immediately afterward, it still stays less than `number`. And then `i` eventually reaches `1`, at which point `number % i == 0` is permanently true, so the list gets filled with arbitrarily many `1`'s until you run out of memory. It's just bad luck that `Integer.MAX_VALUE` happens to be prime. :-) – ruakh Oct 19 '16 at 23:16
Yes, exactly this happen. first function when changed while to if yields [2147483647, -1], but gives wrong answers, for 120, for example, returns 2, 3, 4, 5 (4 is not a prime). So while is important, and function needs fix which you proposed. The second seems be fine. – Oct 19 '16 at 23:33
The `while/if` change that was proposed, not by me, now deleted, is not correct. You need the `while` to get prime factors. – user207421 Oct 20 '16 at 00:34
2

You can speed it up consideraby by testing `i*i < number`, again being careful about wraparound. – user207421 Oct 20 '16 at 00:52

score 0 · Answer 2 · answered Oct 19 '16 at 23:08

0

This loop never terminates. When counter i reaches Integer.MAX_VALUE it rolls over. You should not allow equality in the loop condition.

answered Oct 19 '16 at 23:08

Benjámin Budai

115
8

Why Does This Java Function Crash?

2 Answers2