How can I make this code faster?

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++;
                     }
                   
               }    

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

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
   }  


//***********Example 2 - Your replacement
if(ii*ii+jj*jj < NN)
{
    //etc      
 }    

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

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.

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

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!

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.

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

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

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

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

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

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.
 

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.

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

Oops,

Correction:

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

b.

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

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

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.

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


 

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.

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.

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.

calebS:

Did you get the program to pass the judges test?

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!!!)

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.

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

Regards, Alex