NegativeArraySizeException ... IndexOutOfBoundsException ...
in [Java Programming]
|
From: markspace on 1 Jan 2010 23:58 Arne Vajh�j wrote: >> >> Map<BigInteger,something> .... > > You don't think that uses an array as backing storage? Well, I'm assuming he's not storing every single integer, just some of them. Maybe only primes, since non-primes could be determined by being absent from the list.
From: rem on 2 Jan 2010 04:31 On Jan 2, 7:42 am, Albretch Mueller <lbrt...(a)gmail.com> wrote: > ~ > java only uses int indexes which is giving me a hard time since I > need to index values over Integer.MAX_VALUE. The size of the data > array itself is not a problem at all and I am using a BitSet > ~ > I need indexes greater than Integer.MAX_VALUE in connection to > dynamic sieves to calculate prime numbers. You are gonna get bitten by > these exceptions if you go as far as: > ~ > ( 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 ) = 6469693230 > ~ > That number is risibly small but you cannot use it as an index in > Java ... > ~ > How do you deal with such issues? > ~ > Thanks > lbrtchx Well, if you really need such big arrays you can model them using several small arrays that fit in Integer.MAX_VALUE. Related to the original problem of finding prime numbers with sieve. Can you describe the problem in more details? Why do you multiply all primes up to 29? If the problem is to find all primes up to some N greater than Integer.MAX_VALUE then you can split interval 1..N into smaller subintervals of size for example <= 1000000, and then apply sieve to each such interval. To apply sieve to interval A..B you need to know all primes upto sqrt(B), so initially precalculate all primes upto sqrt (N).
From: Albretch Mueller on 2 Jan 2010 05:40 >> If your calculating really large primes, I suspect you'll need >> BigInteger eventually. (Hint: BigInteger has a nextProbablePrime() >> method. Cool, huh?) >>> How do you deal with such issues? >> Probably >> Map<BigInteger,something> .... >You don't think that uses an array as backing storage? ~ ;-) ~ > Dunten, B., Jones, J., Sorenson, J. P.: A space-efficient fast prime number sieve. ~ Unfortunately I couldn't have access to that article (I am not an institutionalized person) ~ >>> Map<BigInteger,something> .... >> You don't think that uses an array as backing storage? >Well, I'm assuming he's not storing every single integer ~ Well, your assumptions are right, but you will need to somehow "mark" your sieve and for that you need "every single integer" within a sieve window. Don't you? ~ > Can you describe the problem in more details? Why do you multiply all primes up to 29? ~ The non-naive (faster/more efficient ;-)) algorithm I am coding uses as sieve windows the gap between the squares of consecutive primes, which you clobbered by multiplying consecutive primes ~ This discussion started with comp.lang.java.programmer: "java.lang.Rational" I will publish the algorithm/results of my code within a week. Some of use believe such a library should be included by Sun ~ I think I will have to deal with this annoying "only ints for array indexes" thing from sun by using a mappedbuffered file and marking the bits within each byte ~ lbrtchx
From: Tom Anderson on 2 Jan 2010 06:53 On Sat, 2 Jan 2010, Albretch Mueller wrote: >> Dunten, B., Jones, J., Sorenson, J. P.: A space-efficient fast prime number sieve. > ~ > Unfortunately I couldn't have access to that article (I am not an > institutionalized person) You don't have to be: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.3936&rep=rep1&type=pdf >> Well, I'm assuming he's not storing every single integer > ~ > Well, your assumptions are right, but you will need to somehow "mark" > your sieve and for that you need "every single integer" within a sieve > window. Don't you? Ah, there might be a more efficient representation of the windows where you just store a base and a size. Keep them in an interval tree. That gives you a compact representation, but still pretty fast lookup. > This discussion started with comp.lang.java.programmer: > "java.lang.Rational" I will publish the algorithm/results of my code > within a week. Some of use believe such a library should be included by > Sun The problem of a bigger-than-int list has certainly come up before, and a general-purpose implementation would be useful. In fact, i'd be mildly surprised if there wasn't already one in either the Apache or Google collections libraries - have you checked those? tom -- The square-jawed homunculi of Tommy Hilfiger ads make every day an existential holocaust. -- Scary Go Round
From: John B. Matthews on 2 Jan 2010 06:54
In article <nospam-2B3D93.22402401012010(a)news.eternal-september.org>, "John B. Matthews" <nospam(a)nospam.invalid> wrote: > If only one bit is needed for each sieve element, you can pack 32 in an > int to get 2^63 elements, which is indexable by long. Oops, you can pack 32 in an int to get (2^5)(2^31) elements or 64 in a long to get (2^6)(2^31) elements. -- John B. Matthews trashgod at gmail dot com <http://sites.google.com/site/drjohnbmatthews> |