Optimizing and Parallel Computing for Large Dyadic Intervals

I need help with the efficiency of my code i.e. less time so I can compute for large range of values.

My function n[x] takes in a number x and outputs the difference between t and w. The idea behind this code: t = residue class of prime numbers modulo 4, and w = residue class of prime numbers below 3. n[x] calculates the difference between t and w for prime numbers below x and returns the difference.

n = Compile[{{x, _Integer}},
Module[{w = 0, t = 0, p = 3},
While[p <= x, {
If[Mod[p, 4] == 1, w += 1, t += 1];
p = NextPrime[p]}
];
Return[Round[t - w]]
], RuntimeAttributes -> {Listable}, Parallelization -> True,
CompilationTarget -> "C", RuntimeOptions -> "Speed"]

n[x] is my base code. I use it to create my function ncom[a,b]. The idea behind ncom[a,b]: outputs the maximum and minimum differences of n[x] for values between [a,b].

ncom = Compile[{{a, _Integer}, {b, _Integer}},
Module[{x = a, n0 = n[x], out = {}, cmax = n0, cmin = n0, p},
While[x < b,
{p = NextPrime[x];
n0 = n0 - Mod[p, 4, -2];
If[n0 > cmax, cmax = n0];
If[n0 < cmin, cmin = n0];
AppendTo[out, {p, n0}];
x = p}]; Return[cmin, cmax]], RuntimeAttributes -> {Listable},
Parallelization -> True, CompilationTarget -> "C"]

My goal is to create a table with five columns: a | b| b/a | Max[a,b] | Min[a,b], where the values of a and b are increasing by dyadic intervals. I generate the values for a and b using rand[x,y], where Min[a] = a & Max[a] = b.

rand[x_, y_] :=
Do[For[k = {}; j = x, j < y, j++,
a = {RandomInteger[{3 2^j, 3 2^(j + 1)}],
RandomInteger[{3 2^j, 3 2^(j + 1)}]};
AppendTo[k, {Min[a], Max[a]}]]; Return[k], 1]

My desired range of [a,b] (with greatest interval in powers of 10^12) occurs when I use rand[30,50]. However when I plug the a and b numbers I get from rand[x,y] into ncom[a,b], ncom fails to output because its too slow.

So far, I have tried to use floating numbers (which actually ended up insignificant to my code) and Compile (including many of its options such as parallelization). Any other ways of improving the efficiency, aside from those mentioned above, would be of great help. Ideally, my goal is to use ncom for numbers up to 10^15.

• AppendTo is very slow. Try out=Join[out,{{p,n0}}] – Rom38 Jul 20 at 10:46
• Just did that. Improved my code slightly – Alayt Abraham Jul 22 at 0:23