1
$\begingroup$

I have read (58520), but the solutions there do not work when using a large maximum value because they rely on Range. For example, ByteCount[Range[10^9]] yields 8000000144(8GB). Plus, I would be repeating that operation several thousand times, so memory efficiency is necessary.

If the set of primes only consists of one prime, I could use the following:

f[max_, prime_] := Flatten[Range[Range[prime - 1], max, prime]]

This solution does not generate all numbers from 1 to max, thus saving some memory (though not much because the resulting list is only about 1 / prime shorter than Range[max]).

I have created the following solution, but it has a problem:

f[max_, primes_List] := 
  Block[{y = Range[Min[max, Times @@ primes]]}, 
   Scan[(y[[# ;; ;; #]] = Nothing) &, primes]; 
   If[max > Times @@ primes, Flatten[Range[y, max, Times @@ primes]], 
    y]];

The problem is that it may attempt to generate Range[max], which is undesirable.

What are some memory efficient ways to create a list of integers that are not divisible by a set of primes?

$\endgroup$
  • $\begingroup$ Please give me a practical example where fnHybrid fails. $\endgroup$ – Mr.Wizard Jul 20 '16 at 15:40
  • $\begingroup$ @Mr.Wizard f[10^10, Prime[Range[30]] fails. The output should be a list of length 1147700420. $\endgroup$ – JungHwan Min Jul 20 '16 at 15:41
  • $\begingroup$ fnHybrid[1*^9, 30] (my function, not yours) returns a list of 114,768,524 numbers in about 15 seconds on my system, but it does take about 12GB RAM. I'll see if I can reduce that. $\endgroup$ – Mr.Wizard Jul 20 '16 at 15:46
  • $\begingroup$ I think it should be possible to do this memory efficiently in blocks but I can't seem to think clearly about it at the moment and I need to get some other things done. $\endgroup$ – Mr.Wizard Jul 20 '16 at 16:21
3
$\begingroup$

Here is a block-based modification of the first method in my answer to the earlier question:

fnBlock[x1_, x2_, primes_List] := 
   Fold[
     # ~Complement~ Range[x1 + #2 - Mod[x1, #2, 1], x2, #2] &,
     Range[x1, x2],
     primes
   ]

fnMem[x_Integer, n_Integer, block_: 1*^6] :=
  With[{pr = Prime @ Range @ n}, 
    Join @@ Table[
      fnBlock[1 + i block, Min[x, (i + 1) block], pr],
      {i, 0, ⌊x/block⌋}]
  ] ~Monitor~ i

Test with the default block length of one million:

fnMem[1*^9, 30] // Length // Timing
MaxMemoryUsed[]

{60.0292, 114768524}

1883324160

So this was four times slower than Simon's method but took about one sixth the RAM.

A block-based version of Simon's sieve would presumably be faster in this case (small n) but I do not feel like coding that as well right now.


It appears that in many cases my use of Fold in fnBlock is counterproductive; it is far slower and doesn't save much memory until n is large, where it is very slow indeed. Here is a simpler alternative:

fnBlock2[x1_, x2_, p_List] :=
  Complement[
    Range[x1, x2],
    Join @@ Range[x1 + p - Mod[x1, p, 1], x2, p]
  ]

As an example here is a performance sample of the original fnBlock:

fnMem[1*^7, 7730] // Length // Timing
MaxMemoryUsed[]
{37.0502, 656850}

87750368

And again using the new fnBlock2 (starting as always with a fresh kernel):

(* using fnBlock2 in place of fnBlock *)

fnMem[1*^7 , 7730] // Length // Timing
MaxMemoryUsed[]
{1.31041, 656850}

124032312

So here it does use ~ 41% more memory but it is also 28 times faster.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.