Programming Forums > Application Development > C++

ergawy · Apr 8th, 2006, 12:14 PM

I solved this problem but my solution is very slow for numbers such as 10000.
If anybody has an enhanced mechanism or method to solve such problem, please I need your help.

Here you are the problem:
Given a positive integer N, you are to write a program that computes two quantities regarding the solution of
x^2 + y^2 = z^2
where x, y, and z are constrained to be positive integers less than or equal to N. You are to compute the number of triples (x,y,z) such that x<y< z, and they are relatively prime, i.e., have no common divisor larger than 1. You are also to compute the number of values 0<p<=N such that p is not part of any triple (not just relatively prime triples).

The Input
The input consists of a sequence of positive integers, one per line. Each integer in the input file will be less than or equal to 1,000,000. Input is terminated by end-of-file.

The Output
For each integer N in the input file print two integers separated by a space. The first integer is the number of relatively prime triples (such that each component of the triple is <= N ). The second number is the number of positive integers that are not part of any triple whose components are all <= N . There should be one output line for each input line.

Sample Input
10
25
100

Sample Output
1 4
4 9
16 27

and here you are my code:

(Toggle Plain Text)

#include <iostream>
#include <cmath>
using namespace std;


long gcd(long A, long B);


int main()
{
   int N;
   while(cin>>N)
   {
      bool* found;
      found = new bool[N+1];
      for(int i=0 ; i<=N ; i++)
	      found[i] = false;
      int not_found = N;   //discards the numbers that are part of any triple
                           //by decrementing it if we encountered any number
                           //in a triple for the first time
      int num_triples = 0;
      for(i=1 ; i<=N-2 ; i++)
	      for(int j=i+1 ; j<=N-1 ; j++)
	          if(   pow(pow((double)i, 2)+pow((double)j, 2), 0.5) == (int)pow(pow(i, 2)+pow(j, 2), 0.5)
	           && pow(pow(i, 2)+pow(j, 2), 0.5) <= N)
	          {
		  int k = pow(pow(i, 2)+pow(j, 2), 0.5);
		  //cout<<i<<" "<<j<<" "<<k<<endl;
		  if((pow(i, 2) + pow(j, 2)) == pow(k, 2))
		  { 
	                  if(!found[i])
		     { 
		         found[i] = true;
		         not_found--;
	                  }
		     if(!found[j])
		    { 
		        found[j] = true;
		        not_found--;
		    }
		    if(!found[k])
		   { 
		       found[k] = true;
		       not_found--;
		   } 
		if((gcd(i, k) == 1) && (gcd(j, k) == 1) && (gcd(i, j) == 1)) 
		     num_triples++;
	     }
       }
      cout<<num_triples<<" "<<not_found<<endl;
   }
   return 0;
}


long gcd(long A, long B)
{
   if(B > A)
       gcd(B, A);
   if(B == 0)
       return A;
   return gcd(B, A%B);
}

OpenLoop · Apr 8th, 2006, 2:33 PM

just after a quick look, you can do some things to improve efficiency:

- don't use pow to square a number, just use x*x
- since 0<x<y<z<=N, z goes from 1 to N, y from 1 to Z-1, and x from 1 to Y-1. No need to go to N on all three.

that's all i have for now, hope it helps.

Kaja Fumei · Apr 8th, 2006, 3:58 PM

A better (and non-recursive) gcd algorithm would help:
http://en.wikipedia.org/wiki/Euclidean_algorithm
http://en.wikipedia.org/wiki/Binary_GCD_algorithm

ergawy · Apr 8th, 2006, 4:02 PM

thank you very much

andro · Apr 8th, 2006, 6:41 PM

Quote:

Originally Posted by Kaja Fumei

A better (and non-recursive) gcd algorithm would help:
http://en.wikipedia.org/wiki/Euclidean_algorithm
http://en.wikipedia.org/wiki/Binary_GCD_algorithm

The Euclidean algorithm is recursive, not to mention the same method he is using

OpenLoop · Apr 8th, 2006, 7:22 PM

Quote:

Originally Posted by andro

The Euclidean algorithm is recursive, not to mention the same method he is using

Hehe true.
By the way, that binary gcd algorithm is not as efficient as Euclidean. I implemented both algorithms and ran for N=10000:

Quote:

ali@asus:~$ time ./eucmath
1593 1669
real 12m5.579s
user 12m0.625s
sys 0m1.936s

ali@asus:~$ time ./binmath
1593 1669
real 15m47.258s
user 12m43.344s
sys 0m1.469s

(Toggle Plain Text)

#include <iostream>

struct Triple{long x,y,z;};


long gcd(long a, long b)						 //Eulidean Algorithm
{
	if (a < b)
		gcd(b,a);
	if (b == 0)
		return a;
	return gcd(b,a%b);
}

int main()
{
	long N = 10000;
	long prime_triples_count = 0, triples_count = 0, p_count = 0;
	
	Triple sols[50000];

	for (long z = 1; z <= N; z++)					 
	{		
		for (long y = 1; y < z; y++)
		{			
			for (long x = 1; x < y; x++)
		 {			 
			 if (z*z == (y*y) + (x*x))			 
			 {						 		
				    sols[triples_count].x=x; 
					sols[triples_count].y=y; 
					sols[triples_count].z=z;
				 triples_count++;													 
				 if (gcd(x,y) == 1 && gcd(x,z) == 1 && gcd(y,z) == 1)
					 prime_triples_count++;										 
				}
			}
		}
	}

	for (long p = 1; p <= N; p++)		 
	{		
		long i;
		for (i = 0; i < triples_count; i++)	
	 {				 		
			if (p == sols[i].x || p == sols[i].y || p == sols[i].z)
				break;
		}		
		if (i >= triples_count)		   
		{
			p_count++;		
		}
	}
	
	std::cout<<prime_triples_count<<&quot; &quot;<<p_count<<&quot;\n&quot;;	 
			
	return 0;
}

Kaja Fumei · Apr 8th, 2006, 8:59 PM

Quote:

Originally Posted by andro

The Euclidean algorithm is recursive, not to mention the same method he is using

True, but also on that page is the same algorithm written iteratively:

(Toggle Plain Text)

int gcd(int a, int b) {
  int t;
  while (b != 0) {
    t = b;
    b = a % b;
    a = t;
  }
  return a;
}

andro · Apr 8th, 2006, 10:36 PM

Quote:

Originally Posted by Kaja Fumei

True, but also on that page is the same algorithm written iteratively:

(Toggle Plain Text)

int gcd(int a, int b) {
  int t;
  while (b != 0) {
    t = b;
    b = a % b;
    a = t;
  }
  return a;
}

And immediately following, it says that the iterative solution is much less efficient.

OpenLoop · Apr 9th, 2006, 10:54 AM

Quote:

Originally Posted by andro

And immediately following, it says that the iterative solution is much less efficient.

that's the case always. I would only favor iterative if the operation causes a stack overflow.

Apr 8th, 2006, 12:14 PM	#1
ergawy Newbie Join Date: Feb 2006 Posts: 7 Rep Power: 0	can you solve it faster I solved this problem but my solution is very slow for numbers such as 10000. If anybody has an enhanced mechanism or method to solve such problem, please I need your help. Here you are the problem: Given a positive integer N, you are to write a program that computes two quantities regarding the solution of x^2 + y^2 = z^2 where x, y, and z are constrained to be positive integers less than or equal to N. You are to compute the number of triples (x,y,z) such that x<y< z, and they are relatively prime, i.e., have no common divisor larger than 1. You are also to compute the number of values 0<p<=N such that p is not part of any triple (not just relatively prime triples). The Input The input consists of a sequence of positive integers, one per line. Each integer in the input file will be less than or equal to 1,000,000. Input is terminated by end-of-file. The Output For each integer N in the input file print two integers separated by a space. The first integer is the number of relatively prime triples (such that each component of the triple is <= N ). The second number is the number of positive integers that are not part of any triple whose components are all <= N . There should be one output line for each input line. Sample Input 10 25 100 Sample Output 1 4 4 9 16 27 and here you are my code: (Toggle Plain Text) #include <iostream> #include <cmath> using namespace std; long gcd(long A, long B); int main() { int N; while(cin>>N) { bool* found; found = new bool[N+1]; for(int i=0 ; i<=N ; i++) found[i] = false; int not_found = N; //discards the numbers that are part of any triple //by decrementing it if we encountered any number //in a triple for the first time int num_triples = 0; for(i=1 ; i<=N-2 ; i++) for(int j=i+1 ; j<=N-1 ; j++) if( pow(pow((double)i, 2)+pow((double)j, 2), 0.5) == (int)pow(pow(i, 2)+pow(j, 2), 0.5) && pow(pow(i, 2)+pow(j, 2), 0.5) <= N) { int k = pow(pow(i, 2)+pow(j, 2), 0.5); //cout<<i<<" "<<j<<" "<<k<<endl; if((pow(i, 2) + pow(j, 2)) == pow(k, 2)) { if(!found[i]) { found[i] = true; not_found--; } if(!found[j]) { found[j] = true; not_found--; } if(!found[k]) { found[k] = true; not_found--; } if((gcd(i, k) == 1) && (gcd(j, k) == 1) && (gcd(i, j) == 1)) num_triples++; } } cout<<num_triples<<" "<<not_found<<endl; } return 0; } long gcd(long A, long B) { if(B > A) gcd(B, A); if(B == 0) return A; return gcd(B, A%B); } #include <iostream> #include <cmath> using namespace std; long gcd(long A, long B); int main() { int N; while(cin>>N) { bool* found; found = new bool[N+1]; for(int i=0 ; i<=N ; i++) found[i] = false; int not_found = N; //discards the numbers that are part of any triple //by decrementing it if we encountered any number //in a triple for the first time int num_triples = 0; for(i=1 ; i<=N-2 ; i++) for(int j=i+1 ; j<=N-1 ; j++) if( pow(pow((double)i, 2)+pow((double)j, 2), 0.5) == (int)pow(pow(i, 2)+pow(j, 2), 0.5) && pow(pow(i, 2)+pow(j, 2), 0.5) <= N) { int k = pow(pow(i, 2)+pow(j, 2), 0.5); //cout<<i<<" "<<j<<" "<<k<<endl; if((pow(i, 2) + pow(j, 2)) == pow(k, 2)) { if(!found[i]) { found[i] = true; not_found--; } if(!found[j]) { found[j] = true; not_found--; } if(!found[k]) { found[k] = true; not_found--; } if((gcd(i, k) == 1) && (gcd(j, k) == 1) && (gcd(i, j) == 1)) num_triples++; } } cout<<num_triples<<" "<<not_found<<endl; } return 0; } long gcd(long A, long B) { if(B > A) gcd(B, A); if(B == 0) return A; return gcd(B, A%B); }

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Apr 8th, 2006, 2:33 PM	#2
OpenLoop Expert Programmer Join Date: May 2005 Location: East Lansing, MI Posts: 663 Rep Power: 4	just after a quick look, you can do some things to improve efficiency: - don't use pow to square a number, just use x*x - since 0<x<y<z<=N, z goes from 1 to N, y from 1 to Z-1, and x from 1 to Y-1. No need to go to N on all three. that's all i have for now, hope it helps.

Apr 8th, 2006, 3:58 PM	#3
Kaja Fumei Hobbyist Programmer Join Date: Oct 2005 Posts: 134 Rep Power: 3	A better (and non-recursive) gcd algorithm would help: http://en.wikipedia.org/wiki/Euclidean_algorithm http://en.wikipedia.org/wiki/Binary_GCD_algorithm

Apr 8th, 2006, 4:02 PM	#4
ergawy Newbie Join Date: Feb 2006 Posts: 7 Rep Power: 0	thank you very much

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

can you solve it faster