Prev: JPA+hibernate merge vs find fetching lazy collection
Next: java basics
From: Albretch Mueller on 1 Jan 2010 21:42
~
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
From: Arne Vajhøj on 1 Jan 2010 22:00
On 01-01-2010 21:42, Albretch Mueller 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?
> ~

There are no super good solution. They mad a mistake 15 years
ago in the design and did not make array indexes long.

The most obvious workaround must be to segment the
data in multiple arrays.

Arne
From: markspace on 1 Jan 2010 22:10
Albretch Mueller wrote:

> 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:


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> ....

Or a Set<BigInteger>. But I guess you might need a LinkedList or
TreeMap too. Don't forget about LinkedHashMap.




From: Arne Vajhøj on 1 Jan 2010 22:32
On 01-01-2010 22:10, markspace wrote:
> Albretch Mueller wrote:
>> 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:
>
> 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?

> Or a Set<BigInteger>. But I guess you might need a LinkedList or TreeMap
> too. Don't forget about LinkedHashMap.

Those probably don't, but big O for access by index is bad.

Arne

From: John B. Matthews on 1 Jan 2010 22:40
In article
<f1e8ef52-5e87-4310-beff-173a9b3a4ba9(a)m25g2000yqc.googlegroups.com>,
Albretch Mueller <lbrtchx(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?

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.

Alternatively, this looks promising: Dunten, Jones, Sorenson, "A
Space-Efficient Fast Prime Number Sieve."

--
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>
 |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: JPA+hibernate merge vs find fetching lazy collection
Next: java basics