Message Boards Message Boards

0
|
4081 Views
|
1 Reply
|
0 Total Likes
View groups...
Share
Share this post:

Boost code efficiency in residue classes 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.

Attachments:
POSTED BY: Alayt Issak

I'll suggest avoiding Append or AppendTo for large scale computations.

POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract