Solved

# How can I make this code faster?

Posted on 2004-04-22
301 Views
The program below is quite short (written for http://acm.uva.es/problemset/ ). However it is exceeding the allowed time limit. Could anyone give me some pointers on how to speed up the code?

#include <iostream>

using namespace std;

main()
{
int NN;
bool relativePrimeFound;

while (cin >> NN)
{
bool numberUsed[NN];
for (int ii = 0; ii < NN; ii++)
numberUsed[ii] = false;

int relativeTally;
relativeTally = 0;

for ( int ii = 1; ii <= NN; ii++)
for (int jj = ii+1; jj <= NN; jj++)
for (int kk = jj + 1; kk <= NN; kk++)
if (ii*ii + jj*jj == kk*kk)
{
numberUsed[ii-1] = true;
numberUsed[jj-1] = true;
numberUsed[kk-1] = true;

relativePrimeFound = false;
for (int mm = 2; ((mm <= ii) && (relativePrimeFound == false)); mm++)
if ((ii % mm == 0) && (jj % mm == 0) && (kk % mm == 0))
{
relativePrimeFound = true;
relativeTally++;
}

}

int notUsedTally;
notUsedTally = 0;
for (int ii = 0; ii< NN; ii++)
if (numberUsed[ii] == false)
notUsedTally++;

cout << relativeTally << " " << notUsedTally << endl;
}
}

0
Question by:calebS
• 11
• 5
• 5
• +3

LVL 5

Expert Comment

ID: 10896350
i don't quite get why you use the third loop (kk)
think you can simple do

if(ii*ii+jj*jj < NN)
{
numberUsed[ii-1] = true;
numberUsed[jj-1] = true;
numberUsed[ii*ii+jj*jj-1] = true;

relativePrimeFound = false;
for (int mm = 2; ((mm <= ii) && (relativePrimeFound == false)); mm++)
if ((ii % mm == 0) && (jj % mm == 0) && ((ii*ii+jj*jj) % mm == 0))
{
relativePrimeFound = true;
relativeTally++;
}

}
0

LVL 5

Expert Comment

ID: 10896372
and you can save the last loop by including the notUsedTally in your main loop,
in the ii loop,
since that loops from 0 to nn-1 and at it's end,
numberUsed should be updated

and you can save loop length:

since we're only interested in ii*ii+jj*jj=kk*kk,
and we know the jj*jj > ii*ii, thus we know
that ii*ii < (nn*nn)/2,
meaning a maximum of ii<NN/(int)sqrt(2)
as loop length
0

LVL 1

Author Comment

ID: 10896407
Are you trying to say that the following to pieces of code do the same thing? I think you are wrong.

//**********Example 1 - My Code**********
for (int kk = jj + 1; kk <= NN; kk++)
if (ii*ii + jj*jj == kk*kk)
{
//etc
}

if(ii*ii+jj*jj < NN)
{
//etc
}
0

LVL 1

Accepted Solution

ravenscr98 earned 30 total points
ID: 10896478
Since this is not homework, here are some code suggestions.

You basically have 4 nested loops.  Their run time will explode.

The kk loop is looking for one integer value of kk such that ii^2 + jj^2 = kk^2 .  Try

for ( int ii = 1; ii <= NN; ii++)
for (int jj = ii+1; jj <= NN; jj++)
{
int kk = int (sqrt( ii*ii + jj*jj ) );   // cast the square root to an integer
if ( ii*ii + jj*jj == kk*kk ){          // if kk does not work, then ii*ii + jj*jj is not a perfect sqaure

to find that value of kk if it exists.

If you have a GCD (greatest common divisor) function, you could eliminate the mm loop with the test

relativePrimeFound = false;
if ( gcd( gcd(ii,jj), kk) > 1 )
{
relativePrimeFound = true;
relativeTally++;
}

C++ does not provide a gcd function, but Euclid's algorithm is easy to implement.  See

This definition is recursive, but it can easily be implemented in a while loop.  It is required that the arguments be positive integers and satisfy a>=b.  However, you know that jj > ii > 0, so you are all set.
0

LVL 1

Author Comment

ID: 10896685
>Since this is not homework, here are some code suggestions.

*grin*, I am 26 and hold a B. Computer Science.....This is just plain fun.
0

LVL 1

Expert Comment

ID: 10896716
It was fun to answer.  Algorithms and coding are two of my strengths.  I'm a prof. of CS and am very cautious about providing code.
0

LVL 1

Author Comment

ID: 10896774
I see now, and understand completely. I also feel more confident in your response.

Why would the greatest common demoninator work?

I mean say we have 3 numbers A B & C
gcd(A,B) = 7
gcd(7,C) = na

but say A, B & C were all divisible by 4.

Does that make sense?
Would the result indicate no common divisor?

Also, What would the complexity be? O(log((O((logA)( LogB)))(LogC))?
I forget my big O theory (though the textbook is fairly handy), but isn't this fairly big?\

The points are probably not high enough to ask so many questions...
0

LVL 1

Expert Comment

ID: 10896888
Think of GCD as greatest common factor!  If a, b, and c are divisible by 4, we have

gcd(a,b) = 4k, for integer k>0   (it's a multiple of 4)

and

gcd(4k, c) = 4m, for integer m>0  (it's also a multiple of 4).

Consider 16, 24, and 36.  gcd(16,24) = 8.  gcd(8,36) = 4.  The greatest common factor of 16, 24, and 36 is 4!

The complexity is easy.  There are two calls to gcd.  Figure the complexity of each, and add them together.
The complexity of gcd(a,b) is O( log(a) log(b) ) .  The complexity of gcd( gcd(a,b), c) is O( log(gcd(a,b)) log(c) ).  But we know that gcd(a,b) <= a, therefore the complexity is also bounded by O( log(a) log(c) ).  Adding we get a complexity of O( log(a) log(b) + log(a) log(c) ).  This is fast.  Even faster than your mm loop.  log_2(1,000,000,000) is only about 30!  Remember that binary search is O( log_2(n) ) and that is very fast!

0

LVL 1

Author Comment

ID: 10896905
Thanks for the notes on complexity.

What about say 28, 56, 60

gcd(28,56) = 7, gcd(7,60) = 1

Does this mean in code I couldn't just write

if ( gcd(gcd(a,b),c) != 1)
....

I am confused, but don't fear, after asking you a few questions I will go play with alot of figures.
0

LVL 12

Expert Comment

ID: 10897287
Hi calebS,
> if ( gcd(gcd(a,b),c) != 1)

Maybe it makes sense to serialize your gcd calls, so you have a more generic function which you can use to check an integer list of arbitrary size for being relative primes:

int are_relative_prime(int* list,int num){
int i;
int tmp;

assert(num>=2);

tmp=list[0];

for(i=1;i<num;i++)
tmp=gcd(tmp,list[i]);

return tmp==1;
}

(If you expect long lists, you can also take the shortcut of checking for tmp==1 in the loop)

Cheers,
Stefan
0

LVL 39

Expert Comment

ID: 10898911
I think gcd function is not necessary as we need only any common divisor (and not greatest)

So this code should be fastest:

#include <iostream>
#include <cmath>

using namespace std;

void main()
{
int NN = 0;
bool relativePrimeFound;

while (true)
{
cout << "Enter number ==>";
cin >> NN;
if (NN <= 0)
break;
bool* numberUsedArr = new bool[NN+1];
bool*& numberUsed   = numberUsedArr;
for (int nn = 0; nn < NN; nn++)
numberUsed[nn] = false;

int relativeTally;
relativeTally = 0;

for ( int ii = 1; ii <= NN; ii++)
{
for (int jj = ii+1; jj <= NN; jj++)
{
int kk = int (sqrt( ii*ii + jj*jj ) );   // cast the square root to an integer
if (kk > NN)
break;
if ( ii*ii + jj*jj == kk*kk )           // if kk does not work, then ii*ii + jj*jj is not a perfect sqaure
{
{
numberUsed[ii-1] = true;
numberUsed[jj-1] = true;
numberUsed[kk-1] = true;

relativePrimeFound = false;
int s  = 1;
int mm = 2;
while (mm <= ii)
{
if ((ii % mm == 0) && (jj % mm == 0) && (kk % mm == 0))
{
relativePrimeFound = true;
relativeTally++;
break;
}
mm += s;
s   = 2;
}
}
}
}
}
int notUsedTally;
notUsedTally = 0;
for (int mm = 0; mm< NN; mm++)
if (numberUsed[mm] == false)
notUsedTally++;

cout << relativeTally << " " << notUsedTally << endl;
delete [] numberUsedArr;
}
}

Regards, Alex
0

LVL 12

Expert Comment

ID: 10900424
itsmeandnobodyelse,
> I think gcd function is not necessary as we need only any common divisor
> (and not greatest)
Basically, yes. But if you have more than one value to compare, you can run into trouble.

Let's assume we have three numbers, a,b,c. You find any common divisor for the (ab) pair.
gcd(a,b) will find a product of two primes, p * q, whereas you stop with the first common divisor, p.
Now it's possible that c is a multiple of q, but not of p, and you'll get the wrong result that abc are relative prime.

Stefan
0

LVL 39

Expert Comment

ID: 10900671
Stefan, you may be right as i don't know the definition of a relative prime.

My code above does the same the author's code hade done (even better), and this code had stopped in the mm loop if found the first common divisor, stating that he had found a relative prime. If calebS was right gcd function isn't needed in this case. If he was wrong, we need gcd function or have to continue the loop til greatest common divisor was found.

Regards, Alex
0

LVL 1

Expert Comment

ID: 10901173
> Thanks for the notes on complexity.

> What about say 28, 56, 60

> gcd(28,56) = 7, gcd(7,60) = 1

> Does this mean in code I couldn't just write

> if ( gcd(gcd(a,b),c) != 1)

gcd(28,56) = 28, gcd(28, 60) = 4

Yes, you can write ( gcd(gcd(a,b),c) != 1)
0

LVL 1

Expert Comment

ID: 10901399
It is correct that that all you need to find is a common divisor of a, b, c.  But Stefan is correct that you cannot just find a divisor of a and b and test it against c because it may not be the divisor that a or b have in common with c. Thus, using GCD which finds the largest common factor is a sure to find any common factor.

That said, this piece of code from Alex

relativePrimeFound = false;
int s  = 1;
int mm = 2;
while (mm <= ii)
{
if ((ii % mm == 0) && (jj % mm == 0) && (kk % mm == 0))
{
relativePrimeFound = true;
relativeTally++;
break;
}
mm += s;
s   = 2;
}

will stop when it finds the first common factor.  It also reduces the number of values mm that are tested compared to calebS's original code by only considering the sequence of values mm = 2, 3, 5, 7, 9, etc. and by stopping once mm is bigger than ii.  However, in many cases it will run to completion without finding a common factor.

Its average run time is O(ii) and given that ii ranges to NN, it is actually an O(NN) loop.  The gcd, because a, b, and c are bounded by NN has a run time complexity O( log(NN) x log(NN) ) .  Because the mm loop is a third level nested loop within the ii and jj loops and runs for any Pythagorean triple whose values legs are <= NN, it can add considerably to the run time for even moderate values of NN.

I don't know what values of NN the program runs under.  If they are small and the run time limit is not too bad, Alex's solution will probably work fine.  If NN gets large and the run time limit is tight, the gcd implementation will prove superior.

0

LVL 39

Expert Comment

ID: 10901581
Maybe it would make sense to evaluate all primes less than NN before. Then, mm loop is O(log(NN)) - or better - if only uses primes list to iterate on.

Regards, Alex

BTW, could anybody tell me the definition of a relative prime. I had studied math's but never heard this term or only by another name.

0

LVL 1

Expert Comment

ID: 10902294
> Maybe it would make sense to evaluate all primes less than NN before. Then, mm loop is O(log(NN)) - or better - if only uses primes list to iterate on.

I thought of that, and actually he only needs all primes less than sqrt(nn). It would take O(n) to find them.  The loop to test would be quick as you said.  However, it's a bit more coding and requires another array.  It would be interesting to see how the two approaches perform.

> BTW, could anybody tell me the definition of a relative prime. I had studied math's but never heard this term or only by another name.

In math terms, two nonzero integers a, b are relatively prime if gcd(a,b)=1.

In English, two nonzero integers are relatively prime if their only common factor is 1.

If you encountered relative primes, it would have been in number theory or Discrete Math or maybe combinatorics.  It's also common to find them used in theory of algorithms courses.

0

LVL 4

Assisted Solution

booki earned 20 total points
ID: 10906990
FYI:

Maximum NN is 1,000,000.

From ACM Problem 106, Vol. I.

Other observations:

a) ii loop only need go from 1 to (NN-2)

b) jj loop only need go from (ii +1) to (sqrt(NN*NN - ii*ii))

c) calculation of ii*ii can be done before entering jj loop.

d) the notUsedTally can be done inside the ii loop, after the jj loop. (after ii loop you need to test the last 2 values)

b.
0

LVL 4

Expert Comment

ID: 10906995
Oops,

Correction:

a) ii loop need only go from 1 to (sqrt(NN) - 2)

b.
0

LVL 4

Expert Comment

ID: 10907001
Ok, it's late... scratch that last correction.  ...hmm can't seem to find that delete button...
b.
0

LVL 1

Expert Comment

ID: 10910062
> b) jj loop only need go from (ii +1) to (sqrt(NN*NN - ii*ii))

Good catch booki.  I was so worried about eliminating the kk loop I didn't pay attention to the limits.  What the program finds first are the integers ii < jj < kk <= NN, such that they form a Pythagorean triple.  Thus the limit on the jj loop can decrease as ii increases.  But you are also right that we can tighten the limit on the ii loop.  Once ii = sqrt(NN/2), we have that jj > sqrt(NN/2) and ii^2 + jj^2 > NN^2.  Thus kk = sqrt(ii^2 + jj^2 ) > NN.  The ii loop needs to only go to sqrt(NN/2) because of the limit on kk.
0

LVL 4

Expert Comment

ID: 10912767
ravenscr98,

Yes.. thanks.. That's what I was trying to get last night.  One clarification though.

>> Once ii = sqrt(NN/2), we have that jj > sqrt(NN/2) and ii^2 + jj^2 > NN^2.  Thus kk = sqrt(ii^2 + jj^2 ) > NN.

ravenscr98, did you mean  (Okay, it's not so late now.  hopefully my brain is working again..)?

Once ii = sqrt((NN^2)/2), we have that jj > sqrt((NN^2)/2) and ii^2 + jj^2 > NN^2.  Thus kk = sqrt(ii^2 + jj^2 ) > NN.

b.
0

LVL 39

Expert Comment

ID: 10913895
>> Once ii = sqrt(NN/2), we have that jj > sqrt(NN/2) and ii^2 + jj^2 > NN^2.  Thus kk = sqrt(ii^2 + jj^2 ) > NN.

The correct conclusion is

kk = sqrt(ii^2 + jj^2 ) > sqrt(NN).

So, ii loop has to go to NN-2, jj to NN-1 what gives kk the chance to match to NN.

And that would apply for NN == 5

ravenscr98,
thank you for the definition of a relative prime. But why do we need to detect perfect squares if relative primes only depend on gcd(x, y) == 1. For example 8 and 7 are relative primes - as all pairs (z, z+1) - but where is the perfect square?

Regards, Alex

Regards, Alex

0

LVL 1

Expert Comment

ID: 10914880
Sorry all.  I have to stop doing math late at night using function names.  I just did this on paper with real math symbols.  I guess I shouldn't yell at my students so much for not carefully writing out their solutions.

From calebS' original algorithm, we can deduce the following about integers ii, jj, and kk :

ii < jj < NN,
kk <= NN, and
ii^2 + jj^2 = kk^2 .

We can first conclude from this, that ii < jj < kk <= NN.  Thus, jj ranges from ii+1 to NN-1.  However, because jj is at least as large as ii, there is a point where ii becomes so large that kk will be bigger than NN. What is that value of ii?   Since jj > ii, we have that

ii^2 + jj ^2 > ii^2 + ii^2 .

we get that

2 ii^2 < ii^2 + jj^2 = kk^2 <= NN^2 .

Thus we see that 2 ii^2 < NN^2 and solving for ii, we finally find that

ii < NN/sqrt(2).

We can test this for NN=100.  100/sqrt(2) is 70.7.  Thus, the limit on ii is 70.  At ii = 70 and jj = 71, we get kk = 99.7.  It's not a valid triple, but kk is less than 100.  At ii=71 and jj=72, we get kk = 101.1 which is neither an integer nor is it small enough.

The math looks good.  Let's hope that I didn't make any typos.
0

LVL 4

Expert Comment

ID: 10914907
ravenscr98,

I just finished typing up the math.. but it looks like you beat me to it.. anyway.

As you've posted NN/sqrt(2) is an upperbound to ii however it may be faster (for the computer) to express it as:

sqrt( NN^2 / 2 )

or in C++

sqrt(  (NN*NN) >> 1)

Thus avoiding the division.

b.
0

LVL 1

Expert Comment

ID: 10914935
Alex,

Going by the original algorithm, there were two things happening.

First, find Pythagorean triples ii, jj, kk satisfying ii, jj, kk <= NN.  That's where the perfect squares came in.

Second, once a Pythagorean triple is found, determine if the three integers are relative primes.

The final output is the count of triples that are relative primes AND the count of integers from 1 to NN that are not part of a triple.

So the perfect squares play no roll in finding the relatively prime triples.

0

LVL 1

Expert Comment

ID: 10914936
calebS:

Did you get the program to pass the judges test?
0

LVL 1

Author Comment

ID: 10915177
ravenscr98,

I have been skimming the contents of this post. When I posted I was hoping for a simple answer (ie change cout to printf, all done), however instead I have received some interesting thoughts that I want to read, understand and try.

Consequently my allotted few hours (when I posted this topic) ran out, and I am back to doing assignments (a 2nd degree).

So the answer is no, I haven't even tried. I have not ignored this post, but neither do I just want to take someones solution if it is something that I could figure out myself (ie if it is a formula I want to understand it, as opposed to someone telling me to use printf rather then cout I would have just done it).

I will be back on it during the week, though more then likely on the weekend.

(Thanks for everyones help!!!)
0

LVL 1

Expert Comment

ID: 11200215
Tincho:

booki made some good contributions and caught my sloppy math errors.  I suggest that he gets the 50 points, even though he contributed more than 50 points worth to the answer.

0

LVL 39

Expert Comment

ID: 11256958
I think that ravenscr98 should get the points as he made the most qualified comments of all including mine.

Regards, Alex
0

## Featured Post

### Suggested Solutions

Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticallâ€¦
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a Gâ€¦
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relatâ€¦
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.