When I try to make a very large boolean array using Java, such as:
boolean[] isPrime1 = new boolean[600851475144];
I get a possible loss of precision error?
Is it too big?
views:
1037answers:
9
+3
A:
An array index is an int, not a long, so your "array" is too big to fit into an array. One of the java Collection classses might be more suited. Never mind - Collection.size() returns an int as well, so Collection can't store more than MAX_INT items either.
Paul Tomblin
2009-01-19 17:52:41
do that maths Paul - this can't work no matter what
Alnitak
2009-01-19 17:58:37
@Alnitak - I realized that and was making the edit when you posted your comment.
Paul Tomblin
2009-01-19 18:00:05
Technically, a Collection may store more than Integer.MAX_VALUE elements --- size() just returns Integer.MAX_VALUE when this happens.http://java.sun.com/javase/6/docs/api/java/util/Collection.html#size()
Zach Scrivena
2009-01-19 18:54:27
Bitset really only reduces the needed size here by 1/8. The value the questioner is using is much more than 8 times the max value of an array length.
JaredPar
2009-01-19 17:59:51
True, a BitSet wouldn't get you the size needed. It's still a great collection to use in this kind of a situation, though.
Hilton Campbell
2009-01-19 18:19:02
+2
A:
Um... that would be about 70GB worth of booleans. Not gonna work. No way.
Michael Borgwardt
2009-01-19 17:56:46
+2
A:
You can use an array of longs, encapsulated in a class that would handle all the operations on the array. Something like your own implementation of BitSet.
Null303
2009-01-19 17:57:34
Not sure why this was voted down since it's pretty much the only way to get close to that number of bits in a single data structure in Java (assuming you have a 64-bit VM to be able to address that much memory). You would need at least 3 arrays of longs to be able to pack that number of bits.
Dan Dyer
2009-01-19 18:10:33
+7
A:
To store 600 billion bits, you need a minimum address space of 75 gigabytes!
Good luck with that!
In any case, I recognise that number from Project Euler #3. If it needs that much memory, you're doing it wrong...
Alnitak
2009-01-19 17:57:43
+2
A:
The problem is you are using a long value vs. an int value for the size of the array. Java does not support array lengths longer that the maximum value of an int. Java is treating your length as a long because the size you specified exceeds the maximum value for an int but fits within a long. Hence it must convert the length back to an int to create an array. The conversion from long -> int is producing the warning you are seeing
JaredPar
2009-01-19 17:58:58
+1
A:
Why not just store the values in a file, and then seek to the position in the file and pull up the right value. Like others have stated, that's 70GB of data. In most cases, you wouldn't even be able to hold that in memory. If you're going to store it to a file, you could even look at individual bits when storing and retrieving the data using bitwise operators to save on storage space.
Also, since the number of primes decreases with the size of the numbers, it's probably better just to store the prime numbers themselves in the file, in order, and then do a binary search for the number to see if it is one of the primes.
Kibbee
2009-01-19 18:00:05
+1
A:
What values do you have in the array? For a such large number I guess it's going to be a sparse array so maybe it would be best to use a Map/List and just allocate space and store a value for a 1 value for a bit. Or for a 0 value if most of your values will be 1.
deathy
2009-01-19 18:07:15
+1
A:
Since you're attempting to solve Euler-problem #3 the wrong way, here's a hint: You're supposed to find all the prime factors of a number, not all the prime numbers below a certain limit.
BTW: This particular Euler-problem can be solved using a very small amount of RAM.
JesperE
2009-01-19 18:22:24
yes i was quite misguided in my first attempt. thank you for the tip. at least i learned a bit from these comments.
Miamian
2009-01-19 18:58:26