array_int8.cr

def sozcore2(num, start_num, mod)
  residues, rescnt = make_residues_rescnt(mod)              # parameters for the PG
  maxprms, x = pcs_to_num(num, mod, rescnt, residues, true) # num pcs <= end_num

  # for start_num pc, find num pcs <, residue index, and resgroup mod value
  pcs2start, rs, modks = pcs_to_num(start_num, mod, rescnt, residues, false)

  sqrtN = Math.sqrt(num).to_i                                   # sqrt of end_num (end of range)
  pcs2sqrtN, y = pcs_to_num(sqrtN, mod, rescnt, residues, true) # num pcs <= sqrt

  split_arrays = start_num > sqrtN  # flag, true if two arrays used for sieve
  maxpcs = maxprms                  # init array size for all pcs to end_num
  max_range = 0                     # need to define first for crystal compiler
  prms_range = [] of Int8           # need to define first for crystal compiler
  if split_arrays                   # if start_num > sqrtN create two arrays
    maxpcs = pcs2sqrtN              # number of pcs|array size, for pcs <= sqrtN
    max_range = maxprms - pcs2start # number of pcs in range start_num to end_num

    # prms_range = Array.new(max_range, 0)
    prms_range = Array.new(max_range, 0_i8)

    puts "ERROR1: range size too big for available memory." unless prms_range
  end

  # prms = Array.new(maxpcs, 0)
  prms = Array.new(maxpcs, 0_i8)

  puts "ERROR2: end_num too big for available memory." unless prms

  if prms_range && prms
    # residues offsets to compute a pcs address in its resgroup in prms
    pos = Hash(Int32, Int32).new; rescnt.times { |i| pos[residues[i]] = i - 1 }

    # Sieve of Zakiya (SoZ) to eliminate nonprimes from prms and prms_range
    modk, r, k = 0, 0, 0
    nonprm = 0             # need to define first for crystal compiler
    pcs2sqrtN.times do |i| # sieve primes from pcs upto sqrt(end_num)
      r += 1; if r > rescnt
        r = 1; modk += mod; k += 1
      end
      next unless prms[i] == 0     # when a prime location found
      prm_r = residues[r]          # its residue value is saved
      prime = modk + prm_r         # its value is numerated
      prmstep = prime * rescnt     # its primestep computed
      kcon = k * prmstep           # its inner loop constant computed
      residues[1..-1].each do |ri| # now perform sieve with it
      # convert (prime * (modk + ri)) pc value to its address in prms
      # computed as nonprm = (k*(prime + ri) + kn)*rescnt + pos[rr]
        kn, rr = (prm_r * ri).divmod mod             # residues product res[group|track]
        nonprm = kcon + (k*ri + kn)*rescnt + pos[rr] # 1st prime multiple address with ri

        while nonprm < maxpcs
          prms[nonprm] = 1_i8; nonprm += prmstep
        end
        # while nonprm < maxpcs; prms[nonprm] = 1_8; nonprm += prmstep end

        if split_arrays                            # when start_num > sqrtN
          nonprm = (pcs2start - nonprm) % prmstep  # (start_num - last multiple) pcs
          nonprm = prmstep - nonprm if nonprm != 0 # location in range, or beyond

          while nonprm < max_range
            prms_range[nonprm] = 1_i8; nonprm += prmstep
          end
          # while nonprm < max_range; prms_range[nonprm] = 1_i8; nonprm += prmstep end

        end
      end
    end
  end
  # determine prms array parameters and starting location value m for start_num
  m = pcs2start; (prms = prms_range; maxprms = max_range; m = 0) if split_arrays
  {prms, m, modks, residues, rescnt, pcs2start, maxprms, rs} # parameters output
end

def make_residues_rescnt(mod)
  residues = [] of Int32
  residues << 1; 3.step(to: mod, by: 2) { |r| residues << r if mod.gcd(r) == 1 }
  residues << mod + 1
  {residues, residues.size - 1} # return residues array and rescnt
end

def pcs_to_num(num, mod, rescnt, residues, lte)
  num -= 1; lte ? (num |= 1; k = num.abs/mod) : (k = (num - 1).abs/mod)
  modk = mod*k; r = 1
  while num >= modk + residues[r]
    r += 1
  end
  {rescnt*k + r - 1, r, modk} # [num pcs, r index, num modulus}
end

data = sozcore2(5000, 4900, 30)
puts data.class
puts data
prms, m, modks, residues, rescnt, pcs2start, maxprms, rs = data
puts "prms arrray = #{prms} \nm = #{m} \nmaxprpms = #{maxprms} \nresidues = #{residues}"

# require "bit_array"
# a = BitArray.new(50)
# a[15] = true
# puts a, a.size