Archive

Archive for June, 2009

fast java prime number generation

June 7th, 2009

So I found some old prime number generation code and decided to spruce it up. I also wanted to benchmark the BitSet vs a boolean array as I had previously had issues with a boolean array. Six methods tried:

Prime Generators - Source Download

  1. Simp - Simply check for all x’s 0 to maxPrime if x is prime. ie check x isn’t divisible by any number between 2 to x-1.
  2. SimpOdd - same as above, but add 2 to list of known primes, then check all x’s between 0 and maxPrime but stepping in 2’s. And only check for divisibles between 2 to x/2.
  3. S - Sieve - Sieve of Eratosthenes
  4. SS - SkippingSievePG - improve speed by taking advantage that even numbers are never prime except 2. Therefore when sieving using the prime 3, instead of sieving 6,9,12,15,18,21 we can actually sieve 9,15,21 ie jump double our prime each time.
  5. OSS - OddSkippingSievePG - Same as above BUT improve speed/memory making the boolean array represent odd numbers instead of all numbers.
  6. BSOSS - BitSetOddSkippingSievePG - Same as above but use BitSet instead of boolean array


Seconds taken to generate primes between 0 to 10,000,000

speed

Speed of simp’s were so slow as to be unusable for finding large numbers of primes, ie 1000’s of times slower than sieves.


Memory required to generate primes between 0 to 10,000,000

memory

Notice 1,120,000 Bytes needed to store arraylist of integers.

Size of boolean arrays / BitSets in Java

boolean arrays in java use 1 byte per true/false value. BitSets use 1 bit per true/false value (may depend on OS/VM). However BitSets are slower to access. This explains why BitSetOddSkippingSievePG was slower than OddSkippingSievePG but required less memory.

Use a sieve - to generate primes fast

Further Improvements

The idea of reducing the array size by letting the array represent odd numbers could be generalized. Further speed increases are also possible. If you want to know more see wheel factorization or segmented sieves. If you code a quicker prime generator please let me know.

Uncategorized