Asked by Mohsin Shah
on 3 Mar 2018

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 by John D'Errico
on 3 Mar 2018

Edited by John D'Errico
on 5 Mar 2018

Accepted Answer

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
on 3 Mar 2018

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

John D'Errico
on 3 Mar 2018

Why thank you.

Mohsin Shah
on 5 Mar 2018

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

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.