Thread: Few things with my Cardano triplet algorithm

I'm trying to work through problem 251 on Project Euler. Problem 251 - Project Euler

I've got a working algorithm with a few shortcuts while maintaining 100% accuracy. However, it isn't fast enough finding all triplets such that a+b+c <= 100,000 in 35.557 seconds. If I want to find all triplets such that a+b+c<= 110,000,000, then my algorithm has to much faster.

long start = System.currentTimeMillis();
		long end = System.currentTimeMillis();
		int tot = 0;
int lim = 100000;
		for(long a = 2; a <= lim; a+=3)
		{
			for(long b = 1; a+b <= lim; b++)
			{
				if(b!=a)
				{
					double c = (Math.pow(a+1,2)*(8*a-1))/(27.0*Math.pow(b, 2));
					if(Algorithms.isInt(c)&&a+b+c<=lim)
					{
						tot++;
						//end = System.currentTimeMillis();
						//System.out.println("a = " + a + " ; b = " + b + " ; c = " + c + " ; a + b + c = " + (a+b+c) + " ; tot = " + tot + " ; Time = " + ((double)(end-start)/1000.0) + " sec.");
					}
				}
			}
			if(a%1000==0)
			{
				end = System.currentTimeMillis();
				System.out.println("a = " + a + " ; tot = " + tot + " ; Time = " + ((double)(end-start)/1000.0) + " sec.");
			}
		}
 
		System.out.println(tot);
 
		end = System.currentTimeMillis();
 
		System.out.println("Elapsed time: " + (double)(end-start)/1000.0 + " sec.");

Algorithms.isInt()

public static boolean isInt(double val)
	{
		return ((int)val==val);
	}

The output when run right now:

a = 2000 ; tot = 2135 ; Time = 1.388 sec.
a = 5000 ; tot = 4514 ; Time = 3.455 sec.
a = 8000 ; tot = 6616 ; Time = 5.446 sec.
a = 11000 ; tot = 8262 ; Time = 7.376 sec.
a = 14000 ; tot = 9756 ; Time = 9.244 sec.
a = 17000 ; tot = 11268 ; Time = 11.043 sec.
a = 20000 ; tot = 12699 ; Time = 12.803 sec.
a = 23000 ; tot = 14110 ; Time = 14.473 sec.
a = 26000 ; tot = 15187 ; Time = 16.084 sec.
a = 29000 ; tot = 15587 ; Time = 17.63 sec.
a = 32000 ; tot = 15943 ; Time = 19.108 sec.
a = 35000 ; tot = 16277 ; Time = 20.523 sec.
a = 38000 ; tot = 16572 ; Time = 21.875 sec.
a = 41000 ; tot = 16767 ; Time = 23.164 sec.
a = 44000 ; tot = 16914 ; Time = 24.391 sec.
a = 47000 ; tot = 16916 ; Time = 25.555 sec.
a = 50000 ; tot = 16916 ; Time = 26.653 sec.
a = 53000 ; tot = 16916 ; Time = 27.684 sec.
a = 56000 ; tot = 16916 ; Time = 28.658 sec.
a = 59000 ; tot = 16916 ; Time = 29.568 sec.
a = 62000 ; tot = 16916 ; Time = 30.412 sec.
a = 65000 ; tot = 16916 ; Time = 31.189 sec.
a = 68000 ; tot = 16916 ; Time = 31.904 sec.
a = 71000 ; tot = 16916 ; Time = 32.553 sec.
a = 74000 ; tot = 16916 ; Time = 33.14 sec.
a = 77000 ; tot = 16916 ; Time = 33.663 sec.
a = 80000 ; tot = 16916 ; Time = 34.121 sec.
a = 83000 ; tot = 16916 ; Time = 34.52 sec.
a = 86000 ; tot = 16916 ; Time = 34.852 sec.
a = 89000 ; tot = 16916 ; Time = 35.12 sec.
a = 92000 ; tot = 16916 ; Time = 35.324 sec.
a = 95000 ; tot = 16916 ; Time = 35.465 sec.
a = 98000 ; tot = 16916 ; Time = 35.542 sec.
16916
Elapsed time: 35.557 sec.

Would threading help any?

Not gone into it in serious depth, but the number of possible answers stops long before the program does. Is there a maximum value of a beyond which there cannot be any new solutions for a given ceiling? If so, then on this one run of the program you could have saved 10 seconds, or approx 30% running time. Going up to 110,000,000,000,000 or whatever number you go to would see a massive improvement in speed if 30% runtime saving is achieved.

Of course this is only going to help if the first supposition is correct.

Unfortunately, your hypothesis isn't correct. I ran the algorithm such that a+b+c<=1,000,000 but a <= 10,000 to save time. Here's the output:

a = 2000 ; tot = 2993 ; Time = 14.277 sec.
a = 5000 ; tot = 6747 ; Time = 34.872 sec.
a = 8000 ; tot = 10170 ; Time = 55.333 sec.
12292
Elapsed time: 68.886 sec.

Now, if we could figure out a maximum for b relative to max possible, then this would speed up the algorithm.

Some observations:

1. If your CPU has Q processors, then figuring out how to split the problem into Q parallel tasks could result in a time savings with a factor that could be a little less than Q. How to split the problem into Q equal parallel tasks (so that the run time is optimally reduced) might be an interesting exercise in itself.
   
   
2. When looking for efficiency in integer problems, I think it's almost always worthwhile to avoid floating point operations (and floating point math functions) whenever possible.
   
   Try what you have so far (no threads) and compare times with the slight modification that doesn't call the double precision floating point function Math.sqrt. That is, try something like the following in the loop where you calculate c
   
                       double c = ((a+1)*(a+1)*(8*a-1))/(27.0*b*b);

   
   Also, instead of doing floating point division and seeing if the result is an integer value, can't you just use integer arithmetic to see whether one integer is evenly divisible by another integer?
   
   
3. I think your implementation is O(N-squared), where N is the value of lim in your program. (You have two nested loops, each of which depends on the value of lim.) Go with your best effort so far and set lim = 110000000, which is the real target. What are the run times for the first few values of a that your program prints?
   
   Tired of waiting? Try with lim equal to a million. How long does it take to arrive at the final count?
   
   Try again with lim equal to ten million.
   
   Etc...

Now, if the run times are O(N-squared), then the times for lim = 1100000 will be greater than the time for lim = 100000 by a factor of something like a million.

Bottom line: Even if you figure out how to split the problem into threads, run time obtained by dividing the projected total time by the fairly small integer number of processors still might be excessive.

I am pretty sure that your implementation doesn't have much of a chance of doing the deed in a reasonable amount of time. Maybe I'm wrong.

Anyhow...

You seem to have made an important first step: You have discovered that the problem can be reduced algebraically into two conditions.:
Namely:

For integer k = 0, 1, 2, ...
All Cardano triplets (a, b, c) have the relationships

1. a = 3*k + 2
2. b*b*c = ((a+1)*(a+1) * (8*a-1))/27

Your implementation, for a given value of a, lets b go over all possible values within the range defined by lim, calculates the value of the right-hand size of equation 2, divides by b-squared, and counts values for which the result is an integer within the range determined by lim.

Instead of that, maybe you can figure out other ways of factoring the right-hand size and determining divisors within the range defined by lim.

So, think about it (don't start coding just yet):
Maybe start by determining prime factors of a+1 and 8*a-1. Then what?

Bottom line: Just about all of the problems in Project Euler have a "brute-force" approach that might not be too onerous for small problems but require more mathematical sophistication when scaling to larger values. In other words, the key is not necessarily to try to optimize the brute-force method, but to look at alternative approaches.

Finding integer factors of b*b*c within a certain range falls into that category.

I mean, systematic approaches to finding solutions of first order Diophantine equations have been covered fairly well in the literature (still not generally trivial). Second order, well, that's a whole 'nother ballgame. Solutions tend to be very specific.



Cheers!

Z

Well, I've got the run-time for a lim of 100,000 down from 35.5 seconds to 24-25 seconds with a few tweaks I found, Like the maximum value of a that contains any triplets at all approaches lim/2.

lim = 100,000 ; max A = 44,147
lim = 10,000 ; max A = 4,397
lim = 1,000 ; max A = 422

So I set an upper bound on A so that it runs until A == lim/2. Furthermore, I set the limit on B so that instead of all B's < lim, it checks all Bs such that A+B < lim. Could you further explain your explanation about the math side of this problem?

public static void main(String[] args) {
 
		long start = System.currentTimeMillis();
		long end = System.currentTimeMillis();
		int tot = 0;
int lim = 1000;
		for(long a = 2; a <= lim/2; a+=3)
		{
			for(long b = 1;a+b<=lim; b++)
			{
				if(b!=a)
				{
					double c = (Math.pow(a+1,2)*(8*a-1))/(27.0*Math.pow(b, 2));
					if(Algorithms.isInt(c)&&a+b+c<=lim)
					{
						tot++;
						end = System.currentTimeMillis();
						System.out.println("a = " + a + "   \t b = " + b + "  \t c = " + c + "\t a+b+c = " + (a+b+c) + "\t\t tot = " + tot + "\t Time = " + ((double)(end-start)/1000.0) + " sec.");
					}
 
				}
 
			}
			/*if(a%1000==0)
			{
				end = System.currentTimeMillis();
				System.out.println("a = " + a + " ; tot = " + tot + " ; Time = " + ((double)(end-start)/1000.0) + " sec.");
			}*/
		}
 
		System.out.println(tot);
 
		end = System.currentTimeMillis();
 
		System.out.println("Elapsed time: " + (double)(end-start)/1000.0 + " sec.");
 
	}

Is it worth running 4 threads? One for a=1, one for a=upperLimit/4, one for a=upperLimit/2 and one for a=upperLimit*3/4 ?

Obviously the first stops at (upperLimit/4)-1, etc

Each thread would put its entries into a text file/csv. Use a bubble sort to order them and add the totals together

Originally Posted by Norm

aPlusOneSq = (a+1)*(a+1)
aTimes8M1= 8*a-1 or a<<3 - 1

Thanks for that one, it reduced the 100,000 time from 25.5 seconds to 16.4 seconds. Next thing I will try is threading. I have 8 usable cores, so how does 16 or 24 Threads sound (i7 3770 @ 3.4 GHz quad-core with HyperThreading)

Hyper threading means each physical core acts as two logical cores.

lim = 1,000,000
     threads = 32
          time = 418 seconds
          triplets = 163714
     threads = 16
          time = 431 seconds