Computing at compile time

22

I hereby nominate Arjen as Leader of the PACK Intrinsic (is groepsleider better?).

Here is a slight modification of his program, with two speed-ups:

  1. Avoid even numbers in candidates, except for 2.

  2. Avoid putting numbers larger than N in the multiples array.

! primesieve.f90 --
!     Is it possible to build a prime sieve using compile-time computation?
!
program primesieve
    implicit none

    integer, parameter :: N = 1000
    integer, parameter :: rtN = 31 ! isqrt(N)
    integer            :: i, j
    integer, parameter :: candidates(*) = [2,(i, i=3,N-1,2)]
    integer, parameter :: multiples(*)  = [(( i*j, i=j,N/j,2), j=3,rtN,2)]
    integer, parameter :: primes(*)     = pack( candidates, [(all(candidates(i) /= multiples), i = 1,size(candidates))] )

    write(*,'(10I8)') primes

end program primesieve

This version should work with more compilers, while retaining the attribute of “all calculations done at compile time”.

This version, with N equal to 1000, compiled with GFortran 12 (Windows Cygwin64) in less than 3 s (i7-10710U CPU). Intel’s Ifort and Ifx compilers took less than 1 second to compile and run. For this value of N, the size of the multiples array in this version is 563, whereas Arjen’s original version had it at nearly one million!

7 Likes