3
$\begingroup$

I am trying to generate primitive Pythogorean triples using Euclid's parametrization. I basically want a list of pairs with ordered pairs $(m,n)$ such that $m$ and $n$ are coprime.

My first approach was

AbsoluteTiming[
 list1 = Flatten[Table[{m, n}, {m, 1, 20000, 2}, {n, 2, 20000, 2}], 1];
 list2 = Select[list1, (GCD[#[[1]], #[[2]]] == 1) &];]

(*{223.175, Null}*)

in which I first produce a list of pairs where $m$ is always odd and $n$ is always even. Then I use Select to select the pairs where both coordinates are coprime. I quit and restarted a local kernel with a simple computation like 2+2 to make sure there are no effects due to caching, garbage cleanup, or something like that. I then timed the whole thing and got 223 seconds.

My second approach was

AbsoluteTiming[
 list1 = Flatten[
   Table[{m, n, GCD[m, n]}, {m, 1, 20000, 2}, {n, 2, 20000, 2}], 1];
 list2 = Select[list1, #[[3]] == 1 &];]

(*{161.464, Null}*)

in which I compute a third column inside the Table which is the GCD of $m$ and $n$. Then I used Select to simply pick the lists where the third coordinate is one. Restarting the kernel as before and timing it gives me only 161 seconds, which is almost 40% faster.

Why is the first method slower? I don't care about the memory usage. Obviously storing the third column will take more memory.

My thoughts,

  • I would expect both of them to take roughly the same amount of time. If anything, I would expect the second approach to be slower. We are flattening an array with more elements.
  • They are both vectorized approaches.
  • The kernel is doing all of the work (instead of the front-end) in both cases.
  • The number of GDC operations is the same in both cases.
  • The number of comparisons is the same in both cases.
  • In the first case, Select is scanning row-by-row, computing the GCD, and comparing it to one.
  • In the second case, Table is computing the GCD row-by-row and Select is only scanning the third column and comparing it to one.

Which of these, if any, is wrong? The only thing I can think of is that in the first approach Select is scanning both the first and the second column. In the second approach Select is only concerned with the third column ignoring the first two columns completely. Is this true?

What is going on here? What are the lesson to be learned here, in the context of writing fast MMA code?

$\endgroup$
5
  • 3
    $\begingroup$ Use Pick[list1, GCD[list1[[All, 1]], list1[[All,2]]], 1] instead. GCD[list, list] is vectorized, while Select is not. $\endgroup$
    – Carl Woll
    Commented Sep 17, 2020 at 0:30
  • 1
    $\begingroup$ The array unpacking happening with the first example will take a chunk of time.... $\endgroup$
    – ciao
    Commented Sep 17, 2020 at 4:31
  • $\begingroup$ @ciao Isn't the second approach also unpacking the array? I understand the fact that Pick is a better option. But why is the first Select slower than the second Select? $\endgroup$ Commented Sep 17, 2020 at 18:46
  • $\begingroup$ @CarlWoll If you can please elaborate and add an answer. Why isn't Select considered a vectorized function? $\endgroup$ Commented Sep 17, 2020 at 18:48
  • 1
    $\begingroup$ @FixedPoint - nope, in the second example list1 is created unpacked. BTW Pick[list1, DeveloperToPackedArray@GCD[list1[[All, 1]], list1[[All, 2]]], 1]` will cut time quite a bit using list1 from first example - to about 1/2 the time of your second example total. $\endgroup$
    – ciao
    Commented Sep 17, 2020 at 19:07

0

Your Answer

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