How to make my code run faster?

I have written a small piece of code for computing a list of numbers that are relatively prime to a big integer N. This code takes long when the given integer N is large. Please suggest me how to make the code run faster. Here is the code:

function result = coPrimes(N)
    result = [];
    for idx = 1 : N-1
        v(idx) = gcd(N,idx);
        if v(idx) == 1
            result = [result,idx];
        end
    end
end

Answer 1

[John D'Errico]

Well, you DID write code that does what you wanted. However, it employs a terribly poor choice of method to achieve your goal. That is not your fault. You wrote code that did what was requested in the assignment. What matters is to think here about what makes two numbers co-prime, or in this case, not co-prime. Two numbers are co-prime if they share no common prime factors. Even if both of them share just a single factor of 2 or 3, they are not co-prime.

GCD will be SLOW here, employed on EVERY number from 1 to n. Worse, then you are growing the vector dynamically! That forces MATLAB to reallocate memory and copy the entire array on EVERY iteration of the loop. This slows down quadratically as N gets large.

Instead, why not use a sieving scheme? The sieve here is much like that of the sieve of Eratosthenes for finding a list of primes. But the sieve will be based on only the distinct prime factors of N.

function result = coPrimes(N)
  % get the factors of N, but we don't care about replicates.
  % thus, even if 4 divides two numbers so they are not coprime,
  % all that really matters is that 2 also divides them.
  F = unique(factor(N));

    % start with a list of all numbers up to N-1.
    result = 1:(N-1);
    for f = F
      % zap them, flagging them as 0, but don't delete them until the end.
      % while many numbers will be flagged multiple times by this
      % operation, it is blindingly fast, so who cares?
      result(f:f:end) = 0;
    end
    % delete the elements of result that were zero.
    result(result == 0) = [];
  end

Thus, for N = 30, we get

result
result =
     1     7    11    13    17    19    23    29

A sieving operation as I have written will be far more efficient than using GCD in a brute force way.

In fact, for N as large as 340510170, this took only about 1/2 minute on my moderately old computer to compute the list of all 56770560 numbers coprime to N.

N = 2*3*5*7*11*13*17*23*29
N =
   340510170

When I used MY version of coPrimes on this value of N, I checked the time needed at the end. It might require days, if not years of time to solve for that value of N using the version of coPrime you had written.

Elapsed time is 38.869453 seconds.

size(result)
ans =
         1    56770560

Sieving operations are often a far better way to solve such problems. And, well, brute force is almost never a good way. Perhaps the important point to take away from this is that SOMETIMES it is correct to just look for a way to optimize code. So making it run more efficiently with or without loops, etc. But sometimes what is necessary is to look under the hood, understanding the real purpose of the code, and then find a better algorithm. When such a better algorithm exists, you will sometimes gain a vast increase in speed. That was the case here.

[Rik]

Much better than my answer, here, have a vote.

[John D'Errico]

Why thank you.

[Mohsin Shah]

Very nice explanation. Thank you so much, John D'Errico.