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 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?


Update:

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

share|improve this question
    
Can you please give f[i]? And how can you take #[[3]] while Length@data[[1]] is 2? –  Öskå Feb 24 at 10:06
    
@Ö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. –  user565739 Feb 24 at 10:11
    
@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". –  ubpdqn Feb 24 at 23:27

2 Answers 2

up vote 5 down vote accepted

Positions of zeros and non-zeros:

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

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

(* 
{0.249602,Null}
{0.374402,Null}
*)

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

Array[{#,f[#]}&,n]

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

(*
{18.064916,Null}
{8.205653,Null}
True
*)

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

share|improve this answer
1  
Compile can also speed up the creation a lot...but be careful with large integer handling! –  PlatoManiac Feb 24 at 10:43
    
@PlatoManiac: good point - I forget about compile since I mostly deal symbolically or arbitrary precision. –  rasher Feb 24 at 10:45
    
@rasher +1 , link very useful –  ubpdqn Feb 24 at 13:54
    
@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. –  user565739 Feb 24 at 19:09
1  
@user565739: check update re: creation. –  rasher Feb 24 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.

Example:

zero
Extract[data, zero]

yields:

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

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.