Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 11 of 11

Thread: Few things with my Cardano triplet algorithm

  1. #1
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

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


  2. #2
    Junior Member
    Join Date
    Feb 2013
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default

    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.

  3. #3
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Few things with my Cardano triplet algorithm

    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.

  4. #4
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Few things with my Cardano triplet 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

  5. #5
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Few things with my Cardano triplet algorithm

    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.");
     
    	}

  6. #6
    Junior Member
    Join Date
    Feb 2013
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default

    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

  7. #7
    Junior Member
    Join Date
    Feb 2013
    Posts
    5
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default

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

  8. #8
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Few things with my Cardano triplet algorithm

    Another minor point: Do these expressions one time at the a loop level, not inside the b loop
    aPlusOneSq = (a+1)*(a+1)
    aTimes8M1= 8*a-1 or a<<3 - 1
    If you don't understand my answer, don't ignore it, ask a question.

  9. The Following User Says Thank You to Norm For This Useful Post:

    aesguitar (February 2nd, 2013)

  10. #9
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Few things with my Cardano triplet algorithm

    Quote Originally Posted by Norm View Post
    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)

  11. #10
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    25,042
    Thanks
    63
    Thanked 2,708 Times in 2,658 Posts

    Default Re: Few things with my Cardano triplet algorithm

    Having more threads than cores could cause excessive overhead switching between threads. One thread per core could be better.
    I don't know what HyperThreading means.

    Try some experiments and let us know what happens.
    If you don't understand my answer, don't ignore it, ask a question.

  12. #11
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Few things with my Cardano triplet algorithm

    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

Similar Threads

  1. A better way to do things?
    By SnarkKnuckle in forum What's Wrong With My Code?
    Replies: 4
    Last Post: January 18th, 2011, 12:52 PM
  2. Need help getting things to loop correctly
    By egruna2 in forum What's Wrong With My Code?
    Replies: 6
    Last Post: September 9th, 2010, 04:53 PM
  3. Something wrong with the import things
    By mingming8888 in forum What's Wrong With My Code?
    Replies: 3
    Last Post: August 25th, 2010, 07:30 AM
  4. XML, and other things.
    By Tortex in forum The Cafe
    Replies: 0
    Last Post: March 27th, 2010, 03:33 PM
  5. How would i do these things??
    By Curious in forum Java Theory & Questions
    Replies: 4
    Last Post: February 21st, 2010, 08:33 PM