Implementing Remainder Tree

Question

I want to implement Remainder Tree based on this. With the answers on SE I've come up with:

listProduct2[list_] := Times @@@ Partition[list, 2, 2]

T = NestList[listProduct2, Prime[Range[2^7]], 7]

n = 31415926535;

r = {n};
Do[r = Outer[Mod, r, T[[i]]], {i, 7, 1, -1}];

The final desired output is to calculate n mod p for all first 2^n primes using remainder tree but it's very slow rather than being fast. I don't know where I was wrong!

Updated

I have read somewhere that this method can be used for faster sieve implementation, around 10 times faster than any available sieve method!!.

Primo[n_] := Product[i, {i, Prime[Range[n]]}]

primeslist = Prime[Range[10^6]];

prod = Primo[10^6];

n = Primo[205000] + 1;

Timing[MemberQ[listMod[n, primeslist],0]]

{36.719, False}

Timing[GCD[n, prod] != 1]

{2.14, False}

Answer 1

It's meant to be done divide-and-conquer style. Here is one way to go about that.

listMod[n_, {val_}] := {Mod[n, val]}

listMod[n_, vals : {_, __}] := 
 With[{len = Length[vals], rem = Mod[n, Times @@ vals]},
  Join[listMod[rem, Take[vals, Floor[len/2]]], 
   listMod[rem, Drop[vals, Floor[len/2]]]]
  ]

Your example:

n = 31415926535;
primeslist = Prime[Range[2^7]];

Timing[rems = listMod[n, primeslist]]

(* Out[27]= {0., {1, 2, 0, 0, 4, 6, 9, 12, 8, 16, 0, 20, 25, 29, 39, 45, 
  6, 6, 60, 37, 1, 11, 81, 53, 28, 58, 50, 5, 54, 111, 35, 12, 51, 
  134, 79, 92, 141, 100, 95, 12, 84, 161, 145, 82, 59, 112, 18, 73, 
  31, 27, 169, 86, 154, 232, 72, 39, 265, 47, 66, 85, 32, 79, 79, 295,
   99, 62, 251, 314, 118, 166, 8, 239, 242, 43, 281, 324, 231, 83, 
  179, 131, 399, 122, 355, 369, 10, 319, 440, 338, 29, 36, 138, 220, 
  192, 48, 303, 205, 142, 92, 96, 271, 49, 281, 130, 379, 450, 34, 
  580, 406, 424, 179, 543, 199, 561, 283, 153, 530, 412, 435, 544, 
  114, 499, 510, 149, 123, 568, 263, 407, 212}} *)

Here is a more strenuous example.

n = RandomInteger[10^(10^7)];

Timing[rems = listMod[n, primeslist]]

(* Out[33]= {0.030000, {0, 2, 0, 1, 6, 2, 11, 17, 12, 20, 14, 29, 25, 10,
   17, 3, 49, 4, 61, 52, 32, 78, 14, 8, 79, 4, 83, 96, 82, 49, 111, 
  125, 106, 8, 111, 77, 74, 127, 62, 2, 176, 81, 48, 88, 160, 191, 
  119, 153, 210, 1, 25, 11, 125, 154, 126, 256, 240, 258, 214, 56, 
  254, 205, 89, 105, 234, 51, 172, 191, 43, 34, 60, 151, 127, 158, 
  345, 87, 184, 372, 15, 286, 259, 278, 365, 78, 292, 367, 302, 185, 
  75, 236, 199, 28, 26, 266, 1, 256, 40, 497, 513, 61, 88, 29, 447, 
  484, 474, 280, 20, 172, 238, 254, 112, 569, 407, 115, 65, 231, 126, 
  532, 367, 112, 278, 18, 349, 133, 178, 644, 407, 143}} *)

Compare to straight iteration over the moduli.

Timing[rems2 = Table[Mod[n, p], {p, primeslist}]]

(* Out[34]= {0.610000, {0, 2, 0, 1, 6, 2, 11, 17, 12, 20, 14, 29, 25, 10,
   17, 3, 49, 4, 61, 52, 32, 78, 14, 8, 79, 4, 83, 96, 82, 49, 111, 
  125, 106, 8, 111, 77, 74, 127, 62, 2, 176, 81, 48, 88, 160, 191, 
  119, 153, 210, 1, 25, 11, 125, 154, 126, 256, 240, 258, 214, 56, 
  254, 205, 89, 105, 234, 51, 172, 191, 43, 34, 60, 151, 127, 158, 
  345, 87, 184, 372, 15, 286, 259, 278, 365, 78, 292, 367, 302, 185, 
  75, 236, 199, 28, 26, 266, 1, 256, 40, 497, 513, 61, 88, 29, 447, 
  484, 474, 280, 20, 172, 238, 254, 112, 569, 407, 115, 65, 231, 126, 
  532, 367, 112, 278, 18, 349, 133, 178, 644, 407, 143}} *)