6
$\begingroup$

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}
$\endgroup$
10
$\begingroup$

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}} *)
$\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.