How to make this code faster

Write here if you have problems with your C++ source code

Moderator: Board moderators

Post Reply
cthompson
New poster
Posts: 7
Joined: Sat Apr 17, 2004 4:23 am

How to make this code faster

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

SpinLinkDom
New poster
Posts: 1
Joined: Fri Apr 23, 2004 8:56 pm

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

Post Reply

Return to “C++”