I’m finishing a math paper proving Goldbach Conjecture’s (1742).
It states: every even n > 2 can be wriiten as the sum of at least one prime pair.
Here is a Crystal program that will provide the count of all the prime pairs for n,
and the first|last prime pair values (within the limits of your hardware and time).
What I want to do is speed it up (it’s already blazing fast) by doing in
parallel the code blocks for the residue powers and residue cross-products.
I tried doing it using fibers and waitgroups, but it didn’t operate in parallel.
- Can Crystal currently do what I want to do in parallel with fibers.
- If so, can someone show me how.
# Compile: $ crystal build --release --mcpu native prime_pairs_lohi.cr
# Run as: $ ./primes_pairs_lohi <n>
def prime_pairs_lohi(n)
return puts "Input not even n > 2" unless n.even? && n > 2
return (pp [n, 1]; pp [n//2, n//2]; pp [n//2, n//2]) if n <= 6
# generate the low-half-residues (lhr) r < n/2
lhr = 3u64.step(to: n//2, by: 2).select { |r| r if r.gcd(n) == 1 }.to_a
ndiv2, rhi = n//2, n-2 # lhr:hhr midpoint, largest residue val
lhr_mults = [] of typeof(n) # for lhr values not part of a pcp
# store all the powers of the lhr members < n-2
lhr.each do |r| # step thru the lhr members
r_pwr, root = r, 2 # for this lhr, and its square power
break if r > rhi ** (0.5) # exit if r^2 > rhi, as all others are too
while r < rhi ** (1.0/root) # if r < nth root of rhi
lhr_mults << (r_pwr *= r) # store its nth power of r
root = root.succ # check for next power of r
end
end
# store all the cross-products of the lhr members < n-2
lhr_res = lhr.dup # make copy of the lhr members list
while (r = lhr_res.shift) && !lhr_res.empty? # do mults of 1st list r w/others
break if r > rhi ** (0.5) # exit if r^2 > rhi; all other mults are > too
break if r * lhr_res[0] > rhi # exit if product of consecutive r’s > rhi
lhr_res.each do |ri| # for each residue in reduced list
break if (r_mult = r * ri) > rhi # compute cross-product with current r
lhr_mults << r_mult # store value if < rhi
end
end
# remove lhr_mults duplicates, convert vals > n/2 to their lhr complements,
# store them, and those < n/2, in lhr_del; lhr_del now holds non-prime lhr vals
lhr_del = [] of typeof(n)
lhr_mults.uniq.each do |r_del|
lhr_del << (r_del > ndiv2 ? n - r_del : r_del)
end
lhr -= lhr_del # remove from lhr its non-pcp residues
lo, hi = lhr.first, lhr.last # lhr first|last prime residue pcp of n
pp [n, lhr.size] # show n and its number of pcp prime pairs
pp [lo, n-lo] # show first pcp prime pair of n
pp [hi, n-hi] # show last pcp prime pair of n
end
def tm; t = Time.monotonic; yield; Time.monotonic - t end
def gen_pcp
n = (ARGV[0].to_u64 underscore: true)
puts tm { prime_pairs_lohi(n) }
end
gen_pcp
