Re: [Algorithm] Sum of Primes < 1000000

So to make a long story short, the algorithm is:

* Make array of booleans of length max_num - 1, whose zeroth element corresponds to 2 and whose max_num - 2nd element corresponds to maxnum. Clear it (all false). (Java clears it for you if you use Java.)
* Take square root of maxnum and store it somewhere.
* for i = 2 to that square root
* if (array[i - 2]) continue;
* for j = i*i to max_num step i
* set array[j - 2]
* end
* end

Note the optimization of starting the inner loop at i*i. All the composites smaller than i*i have a prime factor smaller than i and so are already marked at that point. Note also skipping the inner loop for composite values of i.

In fact, using the square root of max_num is a less significant optimization after the i*i optimization, as it just stops the outer loop testing every remaining value for compositeness and then entering the inner loop for the primes but without the inner loop actually doing anything (as i*i >= max_num the loop terminates immediately).

The algorithm does sqrt(max_num) bit tests (using the sqrt(max_num) opt) and sum{primes p up to sqrt(max_num}(max_num/p). The number of primes is O(log sqrt(max_num)) from what I've seen of primes, which is O(log max_num) since the log of the square root is simply half the log and the half disappears into the constant factor. The average prime from this set will be O(1) (integral of log x is log x - x, approximates sum of primes; divide by log x for 1 - 1/log(x) is O(1)). So the number of bit sets is O(max_num log max_num) -- O(max_num) per prime as it's max_num/p with average p O(1), and O(log max_num) primes.

So the whole thing has complexity O(n log n) -- as good as quicksort, and without the quadratic worst-case behavior. :)

Removing the squaring/square rooting optimizations doesn't increase the complexity but does increase the running time by a factor of 2 or so. Note that square roots are expensive, but the only square root occurs outside any loops...i*i is just a multiplication, and multiplication of integers is cheap on any modern architecture. The inner loop does one imul, three iadds (one's actually the subtract in the loop test and one computes the array index), one icmp (the rest of the loop test), and one boolean assignment. I expect the compiler to optimize "set array[j - 2]" to "*(foo + j) = true" or something equivalent -- i.e. to use a point two before the actual start of the array as the base for the pointer adds in this loop. Of course, using a BitSet instead of a boolean[] may change this a lot. A sensible implementation plus jit compiler will probably reduce it to a similar add and a bit mask operation, but I expect an idiv will sneak in there to get the array index into the underlying array, which may make BitSet worse-performing, and the subtraction of 2 definitely has to be done separately. Likely *(foo + (j - 2)/64) |= 2^(j - 2) under the hood with 2^(j - 2) sucked out of a lookup table, for a grand total of two extra iadds (j - 2 and the lookup into the 2^n table), one extra idiv, and two extra fetches (the lookup into the 2^n table and retrieving the stored word to |= with something) versus storing in a boolean[] which is probably the one add and a flat store, without bothering to retrieve whatever was in the array cell originally.

I'd be *very* surprised if BitSet actually comes out faster after you run it a few hundred times to get it all JITted and then a few hundred more to measure and average.
.

Relevant Pages

  • Re: [OT] Re: Teaching new tricks to an old dog (C++ -->Ada)
    ... >> A packed array of boolean allocates one storage element to each bit. ... >> provided by Ada so that the program will properly represent ... The following example starts with the creation of a generic package ...
    (comp.lang.ada)
  • Re: [OT] Re: Teaching new tricks to an old dog (C++ -->Ada)
    ... >> A packed array of boolean allocates one storage element to each bit. ... >> provided by Ada so that the program will properly represent ... The following example starts with the creation of a generic package ...
    (comp.lang.cpp)
  • Re: IF/THEN Structure Issues - "Error: Too Many Continuations" PLS
    ... Your boolean array suggestion sounds viable. ... Dim TxtBoxVal As Integer ... >> Else bla bla ...
    (microsoft.public.vb.general.discussion)
  • Re: Bit operations in Ada
    ... I'm new to Ada and bitwise operations is a new challenge in this ... I started with an array of booleans of size 2**n, ... I'm ought to use directly an array of boolean and ... procedure Set (Bit: in Bit_Number; ...
    (comp.lang.ada)
  • Re: Optimizing AND of an 2d boolean array
    ... LineMask: array of LongWord; ... // prepare line mask ... I don't use longword shifts to fill the array, ... T2DBooleanArray = array of array of Boolean; ...
    (borland.public.delphi.language.basm)