----------------------------------- Naveg Wed Nov 02, 2005 6:45 pm Array length of a long value ----------------------------------- Is it at all possible to have an array that has a length of a long value?? So far all my research has shown that only ints can be the index of an array.... If not, how would I go about storing a "long" number of things? ----------------------------------- wtd Wed Nov 02, 2005 7:01 pm ----------------------------------- ArrayList also appears to be limited to "int" length. I'd suggest reconsidering why you're storing that much at one time. That would be using massive amount of memory. ----------------------------------- Naveg Wed Nov 02, 2005 7:22 pm ----------------------------------- well, i have an assignment to find all the primes up to an inputted number...and i thought i would use the sieve of eratosthenes. Use a boolean array, start all at true, gradually eliminate composite numbers, output all remaining "true" indexes ----------------------------------- wtd Wed Nov 02, 2005 7:36 pm ----------------------------------- Do you expect such a large input number? ----------------------------------- Naveg Wed Nov 02, 2005 9:10 pm ----------------------------------- My teacher said to use longs so he can test the efficiency with larger numbers. ----------------------------------- wtd Wed Nov 02, 2005 9:38 pm ----------------------------------- Then you may have to try a different strategy. :) ----------------------------------- Naveg Wed Nov 02, 2005 10:20 pm ----------------------------------- Well...would there be any other way to implement the sieve of eratosthenes without using an array? ----------------------------------- beard0 Wed Nov 02, 2005 11:21 pm ----------------------------------- Well...would there be any other way to implement the sieve of eratosthenes without using an array? No. You could however use the sieve of eratosthenes using a two dimmensional array where virtualArray[longValue] = actualArray[longValue / maxInt][longValue % maxInt] ----------------------------------- GlobeTrotter Wed Nov 02, 2005 11:37 pm ----------------------------------- What about using a linked list? ----------------------------------- rizzix Thu Nov 03, 2005 1:53 am ----------------------------------- What about using a linked list? That would slow the algorithm down... the faster alternatives would be ArrayList or Vector.. but then again.. i think they too fall under the same restriction. ----------------------------------- wtd Thu Nov 03, 2005 1:59 am ----------------------------------- What about using a linked list? That would slow the algorithm down... the faster alternatives would be ArrayList or Vector.. but then again.. i think they too fall under the same restriction. They do. ----------------------------------- Naveg Thu Nov 03, 2005 5:31 pm ----------------------------------- how then do people have programs that can find primes up to massively huge numbers like 100000000000 using the sieve of eratosthenes? Do they not use arrays? I'm researching a different algorithm for finding primes to try and accomodate a larger range of values without sacrificing speed.... ----------------------------------- wtd Thu Nov 03, 2005 5:36 pm ----------------------------------- how then do people have programs that can find primes up to massively huge numbers like 100000000000 using the sieve of eratosthenes? Do they not use arrays? They don't use Java? ----------------------------------- Naveg Thu Nov 03, 2005 5:45 pm ----------------------------------- how then do people have programs that can find primes up to massively huge numbers like 100000000000 using the sieve of eratosthenes? Do they not use arrays? They don't use Java? Figured you'd say that. But in a language like C++, do arrays take up less RAM? Or are the other data structures in C++ just far faster than those of Java? ----------------------------------- wtd Thu Nov 03, 2005 5:48 pm ----------------------------------- Well, in C and C++, the problem is that arrays are glorified pointers. On a 32-bit machine, array indexes can only be 32-bit integers. ----------------------------------- [Gandalf] Thu Nov 03, 2005 5:48 pm ----------------------------------- What makes you think he was talking about C++? Maybe he was, but I'm sure you could make some even faster optimised Assembly code. Try to keep your mind open on things like this. ----------------------------------- rizzix Thu Nov 03, 2005 5:57 pm ----------------------------------- it's simple actually... here's how you'd implement it.. #1: use a multi-dimensional rectangular array (let's take a 2D array, as a 2D array will provide for storing a maximum of (2^32 - 1)*(2^32 - 1) values... *a huge number!!* #2: fix the ROW and COL dimension to MAX_INT #3: create a class.. that will handle the 1D -> 2D conversion for you. now i'm not going to create this class for you but... here's the basic mechanics behind such a class:long[][] primes = new long[Integer.MAX_INT][Integer.MAX_INT]; basically the Nth value in the emulated 1D-array is the (row*Integer.MAX_INT+col)th value in the 2D "primes" array. so in ur long get(long n); you should basically have **refer to beard0's post** (edit: sorry dude didn't see ur post) note: the code is not tested... it could be wrong.. but hopefully you get the idea ;) also note: long may not be a large type to encompass all those values.. -,-'' You might have to use the BigDecimal class.. Or even better reduce the size of the 2D "primes" array. ----------------------------------- Naveg Thu Nov 03, 2005 6:10 pm ----------------------------------- Well the total size of the array only needs to be a number specified by the user. As well, the array type can be boolean (ie. is the index of this value prime of not). ----------------------------------- rizzix Thu Nov 03, 2005 6:12 pm ----------------------------------- ah well all the better then.. but you get the idea.. ----------------------------------- beard0 Fri Nov 04, 2005 3:44 pm ----------------------------------- Err... did nobody read my post about 2D arrays on the previous page? ----------------------------------- wtd Fri Nov 04, 2005 3:50 pm ----------------------------------- Hey, you know what might work? Using a two dimensional array. ;) ----------------------------------- rizzix Fri Nov 04, 2005 4:42 pm ----------------------------------- there's a way to do it with a 2D array?? cool!! how? :P ----------------------------------- Naveg Fri Nov 04, 2005 4:43 pm ----------------------------------- would it though? In theory it would yes, but I'm still restricted by java's memory limitations...which are currently reached even before an array of MAX_INT values. ----------------------------------- rizzix Fri Nov 04, 2005 8:41 pm ----------------------------------- ok here's my shot at a solution... import java.util.*; import java.math.*; class test { final static BigInteger ONE = BigInteger.ONE; final static BigInteger ZERO = BigInteger.ZERO; public static void main(String Notice i've used the BigInteger class... So it should work with arbitrary long numbers... either way.. this is not the "fastest" solution (especially cuz of the BigInteger class)... but.... gah! ----------------------------------- HyperFlexed Sat Nov 05, 2005 6:23 pm ----------------------------------- I've never seen the purpose of computing primes. I sure hope I never get the project.