I used data=Table[{i,f[i]},{i,1,n}] to produce a list, here n is greater than 2^20 = 1048576. The function f(N) runs in time O(N*Log(N)), it is defined as:

Mod[PowerMod[i,n,n]-i,n] (n is an argument in a function which use this)

Now I want to give a table which shows the values of i that f(i) is 0, and another table for f(i) non-zero.

I used zero = Select[data,#[[2]]==0&], but it is slow in the following sense:

n=2^22, timing for data =  10.171, timing for zero =  4.508
n=2^23, timing for data =  21.606, timing for zero =  9.250
n=2^24, timing for data =  43.399, timing for zero = 17.971
n=2^25, timing for data =  84.209, timing for zero = 34.523
n=2^26, timing for data = 167.420, timing for zero = 71.885

The hardest computation is the data, But after that I want to have a much faster way to know the zeros of the function f.

Of course I can use For or Do to append the zeros i each time f(i) is zero. But we know that AppendTo is slow, and For or Do is slower than Table.

Is there any way to construct a list + exact data fast?


Thanks for all the suggestion. Here is a table of comparison. The green columns is to find i such that f[i]=0 and the white columns (excluding the 1st and 2nd column) is to find i such that f[i]!=0. The last 2 columns are in fact using "NonzeroPositions" (the last column) as mentioned by ubpdqn, then do the complement (the second last column). This method is faster.

enter image description here

  • $\begingroup$ Can you please give f[i]? And how can you take #[[3]] while Length@data[[1]] is 2? $\endgroup$
    – Öskå
    Feb 24, 2014 at 10:06
  • $\begingroup$ @Öskå:Sorry, it is a typo. In my actual code, it should be 3, but I simplify the code here, so it should be 2. Thanks. $\endgroup$
    – user565739
    Feb 24, 2014 at 10:11
  • $\begingroup$ @user565739 thank you for the update and performance assessment. rasher answer more thoughtful and analytical than mine. Just wanted to post an alternative exploiting "NonzeroPositions". $\endgroup$
    – ubpdqn
    Feb 24, 2014 at 23:27

2 Answers 2


Positions of zeros and non-zeros:

dataZeros = SparseArray[1 - Unitize[data[[All, 2]]]]["AdjacencyLists"]; // Timing

dataNonZeros = SparseArray[Unitize[data[[All, 2]]]]["AdjacencyLists"]; // Timing


That's for a 1M entry table, on a netbook. Just use the result with Part or Extract to get the actual data. The first for zero positions can also be done (with slightly faster results via verbosity) as:

dataZeros = SparseArray[Unitize[data[[All, 2]]], Automatic, 1]["AdjacencyLists"]

You can also use

Pick[data, Unitize[data[[All, 2]]], 0]
Pick[data, Unitize[data[[All, 2]]], 1]

to do the same, and get datasets directly.

For ideas on how the (sparsely documented) feature of SparseArray and things like Unitize have potentially huge performance benefits, search for the terms on the site, have a look an Mr. Wizard's posts regarding them, and see my answer here where using it made a problem solvable thousands of times more quickly.

As far as creating it more quickly, short of going parallel with multiple kernels, doing it as


might save 10% or so in time.

Edit: I've found this quite a bit faster for creation:

n = 1000000

data = Table[{i, Mod[PowerMod[i, n, n] - i, n]}, {i, 1, n}]; // Timing

data2 = Transpose[{l = Range[n], Mod[PowerMod[l, n, n] - l, n]}]; // Timing

data == data2


Timings again on lounge-netbook, curious what your results are...

  • 1
    $\begingroup$ Compile can also speed up the creation a lot...but be careful with large integer handling! $\endgroup$ Feb 24, 2014 at 10:43
  • $\begingroup$ @PlatoManiac: good point - I forget about compile since I mostly deal symbolically or arbitrary precision. $\endgroup$
    – ciao
    Feb 24, 2014 at 10:45
  • $\begingroup$ @rasher +1 , link very useful $\endgroup$
    – ubpdqn
    Feb 24, 2014 at 13:54
  • $\begingroup$ @rasher : I found that Array[{#, f[#]} &, n]][[1] is a litte bit slower than Table[{b, f[b]}, {b, 1, n}], which is 124.426 vs 105.565 when n = 25. $\endgroup$
    – user565739
    Feb 24, 2014 at 19:09
  • 1
    $\begingroup$ @user565739: check update re: creation. $\endgroup$
    – ciao
    Feb 24, 2014 at 23:23

Just exploiting another feature of SparseArray and for sample of size $10^6$.

Setting up:

fun[n_] := Table[{i, Mod[PowerMod[i, n, n] - i, n]}, {i, 1, n}];
data = fun[1000000];

Using "NonzeroPositions":

nozero= SparseArray[Last@Transpose@data]["NonzeroPositions"]; // Timing
zero = Complement[List /@ Range[Length@data], ans]; // Timing

yielded:{0.078125, Null}, {0.093750, Null} respectively.


Extract[data, zero]


{{1}, {109376}, {890625}, {1000000}}
{{1, 0}, {109376, 0}, {890625, 0}, {1000000, 0}}
  • $\begingroup$ +1 - I feel like a dufus forgetting that property, that I use in the answer I linked... DOH! $\endgroup$
    – ciao
    Feb 24, 2014 at 23:28
  • $\begingroup$ @rasher sadly but productively DOH moments are how I learn $\endgroup$
    – ubpdqn
    Feb 25, 2014 at 1:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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