Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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}
share|improve this question
add comment

1 Answer

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}} *)
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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