Page 1 of 1

How to make this code faster

Posted: Fri Apr 23, 2004 3:37 am
by cthompson
Can anyone offer any suggestions for how to speed this code up?

I am looking but failing to see anything (probably due to my inexperience in C++). I have a little program that works with Visual Basic to show how long each section of code runs, does anyone know of anything like that for C++?



[cpp]
#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;
}
}
[/cpp]

Posted: Fri Apr 23, 2004 9:14 pm
by SpinLinkDom
The problem isn't your code, it's your algorithm.

As you see, you have 5 imbriqued for boucle so it look like your have a complexity about O(N**5). It look like your are triying to find if a number is relative prime to an other, so it like checking if the gcd is different is 1. So, I would suggest to try for that en efficient algorithm like the Euclid one or the binary version. Here the fonction (standart version, go search the web for the binary one (use no division, so it's faster)) using template. (If you use float number (float, double, long double), you need to specialize it since % isn't defined))

Instead, you may search for an efficient function to factor number and save the result for later number

[cpp]
template<class _T>
_T ABS(_T n) {
return n>=0?n:-n;
}

template<class _T>
_T gcd(_T a, _T b) {

while(b!=0) {
_T c=a % b;
a=b;
b=c;
}
return ABS(a);
}
[/cpp]