Page 1 of 2 12 LastLast
Results 1 to 20 of 25
  1. #1
    jayant3001's Avatar
    jayant3001 is offline Member
    Join Date
    Oct 2008
    Posts
    22
    Rep Power
    0

    Arrow challenging problems

    hi
    i ve tried to solve this prob using java:
    For a positive integer n, let σ2(n) be the sum of the squares of its divisors. For example,

    σ2(10) = 1 + 4 + 25 + 100 = 130.
    Find the sum of all n, 0 n 64,000,000 such that σ2(n) is a perfect square.

    but its taking long long time to run
    can anybody help??
    this is my code:
    Java Code:
    import java.math.*;
    import static java.lang.Math.*;
    public class prob211
    {
    	public prob211()
    	{
    		BigInteger sum = BigInteger.ZERO;
    		
    		for(BigInteger i = BigInteger.valueOf(1);i.compareTo(BigInteger.valueOf(64000000))<0;i=i.add(BigInteger.ONE))
    		{
    			BigInteger x = BigInteger.ZERO;
    			BigInteger sqsum = BigInteger.ZERO;
    			for(BigInteger j = BigInteger.valueOf(1);j.compareTo(BigInteger.valueOf((i.divide(BigInteger.valueOf(2))).longValue()))<=0;j=j.add(BigInteger.ONE))
    			{
    				if((i.mod(j)).equals(BigInteger.ZERO))
    				{
    					sqsum = sqsum.add(j.multiply(j));
    				}
    			}
    			sqsum=sqsum.add(i.multiply(i));
    			long y =(long) sqrt(sqsum.longValue());
    			for(BigInteger k= BigInteger.ONE;k.compareTo(BigInteger.valueOf(y))<=0;k=k.add(BigInteger.ONE))
    			{
    			  x = x.add(((k.multiply(BigInteger.valueOf(2))).subtract(BigInteger.ONE)))	;
    			}
    			if(x.equals(sqsum))
    			{
    			sum = sum.add(i);
    			}
    			}
    		System.out.println(sum);
    	} 
    	public static void main(String[] args)
    	{
    	  new prob211();
    	}
    }

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,305
    Rep Power
    25

    Default

    Have you tried debugging your code by adding println() statements to print out every so often to show progress?

  3. #3
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    Yes debug and see, I think you are working on a Java IDE. Check about the following loop you are using.

    Java Code:
    		if((i.mod(j)).equals(BigInteger.ZERO))
    		{
    			sqsum = sqsum.add(j.multiply(j));
    		}
    it may take a long time to execute.

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,305
    Rep Power
    25

    Default

    I'd rewrite the program to use int or long variables anywhere they work. All those method calls will take time.
    To see where the code is eating CPU time use the -Xprof option on the java command. You only need a few 1000 loops to get an idea where the time is being spent, not 64M

  5. #5
    jayant3001's Avatar
    jayant3001 is offline Member
    Join Date
    Oct 2008
    Posts
    22
    Rep Power
    0

    Default

    i checked using println(). upto 10000 its going well but after that its taking long time

  6. #6
    jayant3001's Avatar
    jayant3001 is offline Member
    Join Date
    Oct 2008
    Posts
    22
    Rep Power
    0

    Default

    ya mod i m working on java IDE .Is there any other way to do that ?

  7. #7
    jayant3001's Avatar
    jayant3001 is offline Member
    Join Date
    Oct 2008
    Posts
    22
    Rep Power
    0

    Default

    hi norm
    but number is too big to work with long or int thats why i m using BigInteger

  8. #8
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,305
    Rep Power
    25

    Default

    Have you tried a version that uses int or long?
    How long to they take?

  9. #9
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,305
    Rep Power
    25

    Default

    What number is too big? How big? Why are all the numbers BigInteger? Do the loop control variables get that large?

    What does the for loop on k compute? Does it always have to start at 1?

    For tests I ran you code for 10000 loops - it took 48 secs.
    I rewrote the code to use a modified version of BigInteger and changed the for(k) loop to return y*y and it took 3 secs. Both versions get the same answer:
    //sum=36446 for 10000, time=48859 your code
    //sum=36446 for 10000, time=3172 my version
    Last edited by Norm; 10-26-2008 at 07:44 PM.

  10. #10
    jayant3001's Avatar
    jayant3001 is offline Member
    Join Date
    Oct 2008
    Posts
    22
    Rep Power
    0

    Default

    BigInteger is needed only for variable sum.but i easy other place for easy .I think where u use long or int instead of BigInteger its does not make any difference .
    k is for checking perfect square n its necessary to start from 1.
    can u just tell what modified version of BigInteger u used so that it took less time ??any way main prob is for loop containing
    j.

  11. #11
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,305
    Rep Power
    25

    Default

    Instead of rewriting your code to use long, I wrote this class hoping that it would be faster than Sun's version.
    Java Code:
       static class BigInteger {
          final static BigInteger ZERO = new BigInteger(0);
          final static BigInteger ONE = new BigInteger(1);
          final static BigInteger TWO = new BigInteger(2);
          long value;
    
          BigInteger() {
          }
          BigInteger(long v){
             value = v;
          }
          //-----------------------------
          long longValue(){
             return value;
          }
          static BigInteger valueOf(long ln) {
             if(ln == 0) return ZERO;
             else if(ln == 1) return ONE;
             else if(ln == 2) return TWO;
             else return new BigInteger(ln);
          }
          int compareTo(BigInteger bi) {
             return (int)(value - bi.value);
          }
          BigInteger divide(BigInteger bi) {
             return new BigInteger(value/bi.value);
          }
          BigInteger multiply(BigInteger bi) {
             return new BigInteger(value*bi.value);
          }
          BigInteger mod(BigInteger bi) {
             long mod = value % bi.value;
             return valueOf(mod);
          }
          BigInteger add(BigInteger bi) {
             return new BigInteger(value + bi.value);
          }
          BigInteger subtract(BigInteger bi) {
             return new BigInteger(value - bi.value);
          }
          public boolean equals(BigInteger bi) {
             return (value == bi.value);
          }
          public String toString() {
             return ""+value;
          }
       } // end class BigInteger
    What is the size of the number that is too big for long? long is 2^64
    using primitives will make your code much faster.
    Also you could move some expressions outside of the loop:
    Java Code:
             final BigInteger endJ = BigInteger.valueOf((i.divide(BigInteger.valueOf(2))).longValue()); 
     ...
    BigInteger BIy = BigInteger.valueOf(y)
               ...
               k.compareTo(BIy) <= 0;
    instead of computing them over and over.


    I replaced the for(k) loop with y*y and I get the same answers as your code with the loop. And its much faster.

    Have you tried the -Xprof operand to get a profile of where you code is executing? You'll need to break the constructor up into a couple of methods to see which code.

  12. #12
    jayant3001's Avatar
    jayant3001 is offline Member
    Join Date
    Oct 2008
    Posts
    22
    Rep Power
    0

    Default

    yes i did -Xprof operation but actually i m new to this so i could not understand this .can u explain it plz.
    Java Code:
    36446
    
    Flat profile of 65.57 secs (4428 total ticks): main
    
      Interpreted + native   Method                        
      0.0%     1  +     0    java.math.BigInteger.subtract
      0.0%     1  +     0    Total interpreted
    
         Compiled + native   Method                        
     21.4%   949  +     0    java.math.MutableBigInteger.divide
     17.6%   732  +    46    java.math.BigInteger.add
     10.9%   436  +    46    java.math.BigInteger.valueOf
      7.6%   287  +    49    java.math.BigInteger.subtract
      7.4%   236  +    91    java.math.BigInteger.add
      7.1%   313  +     0    prob211.<init>
      5.0%   185  +    36    java.math.BigInteger.multiplyToLen
      4.7%   164  +    45    java.math.BigInteger.multiply
      4.1%   180  +     0    java.math.BigInteger.compareTo
      4.1%   167  +    13    java.math.BigInteger.subtract
      2.6%    47  +    66    java.math.BigInteger.divide
      2.4%    45  +    63    java.math.BigInteger.remainder
      2.1%    93  +     2    java.math.BigInteger.trustedStripLeadingZeroInts
      1.4%    64  +     0    java.math.MutableBigInteger.copyValue
      0.9%    39  +     0    java.math.MutableBigInteger.clear
      0.7%     0  +    30    java.math.BigInteger.<init>
      0.1%     3  +     0    java.math.BigInteger.mod
    100.0%  3940  +   487    Total compiled
    
    
    Flat profile of 6.40 secs (1 total ticks): DestroyJavaVM
    
      Thread-local ticks:
    100.0%     1             Unknown: thread_state
    
    
    Global summary of 71.99 seconds:
    100.0%  4927             Received ticks
      7.1%   349             Received GC ticks
      2.5%   122             Other VM operations
      0.0%     1             Unknown code

  13. #13
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,305
    Rep Power
    25

    Default

    21.4% 949 + 0 java.math.MutableBigInteger.divide
    17.6% 732 + 46 java.math.BigInteger.add
    10.9% 436 + 46 java.math.BigInteger.valueOf
    7.6% 287 + 49 java.math.BigInteger.subtract
    Of the 66 seconds for your program to execute, over 50% was spent in the above 4 methods.
    Most of you usages of valueOf (11%) are for constants and should be final and outside of the loops.

    You still have NOT stated how large the numbers are you are working with.
    Using classes for the repeated computations in your code is VERY EXPENSIVE!!!
    Last edited by Norm; 10-27-2008 at 01:50 AM.

  14. #14
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

    Default

    Quote Originally Posted by jayant3001 View Post
    ya mod i m working on java IDE .Is there any other way to do that ?
    No I'm just asking. Because it's too easy to debug your code and see what happen. You can use the watch list as well.

  15. #15
    jayant3001's Avatar
    jayant3001 is offline Member
    Join Date
    Oct 2008
    Posts
    22
    Rep Power
    0

    Default

    norm
    in code above i ve written that loop should be up to 64000000
    and if we take a number near it and add square of its factors then certainly it will be very large

  16. #16
    jayant3001's Avatar
    jayant3001 is offline Member
    Join Date
    Oct 2008
    Posts
    22
    Rep Power
    0

    Default

    thanks for explanation .............

  17. #17
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    SW Missouri
    Posts
    17,305
    Rep Power
    25

    Default

    How long does it take on your computer to run your code for 64M loops?

  18. #18
    jayant3001's Avatar
    jayant3001 is offline Member
    Join Date
    Oct 2008
    Posts
    22
    Rep Power
    0

    Default

    i wait for 4 hrs but could not get answer

  19. #19
    jayant3001's Avatar
    jayant3001 is offline Member
    Join Date
    Oct 2008
    Posts
    22
    Rep Power
    0

    Default

    hi norm i ve written code using long n int but same prob here
    Java Code:
    import static java.lang.Math.*;
    public class prob211a
    {
    	public prob211a()
    	
    	{
    		long sum = 0L;
    		for(int i = 1;i<64000000;i++)
    		{
    			 long sqsum = 0L;
    			final int rem = i/2;
    			for(int j=1;j<=rem;j++)
    			{
    				if(i%j==0)
    				{
    					sqsum += j*j; 
    				}
    			}
    			sqsum+= i*i;
    			long sqr = (long)sqrt(sqsum);
    			if(sqsum == (sqr*sqr))
    			{
    				sum+= i;
    			//	System.out.println(i);
    			}
    		}
    		System.out.println(sum);
    	}
    	public static void main(String[] args)
    	{
    		new prob211a();
    	}
    }

  20. #20
    Eranga's Avatar
    Eranga is offline Moderator
    Join Date
    Jul 2007
    Location
    Colombo, Sri Lanka
    Posts
    11,372
    Blog Entries
    1
    Rep Power
    20

Page 1 of 2 12 LastLast

Similar Threads

  1. Replies: 24
    Last Post: 07-29-2008, 04:04 PM
  2. Problems in JSP : Need help
    By raj4u in forum JavaServer Pages (JSP) and JSTL
    Replies: 1
    Last Post: 02-07-2008, 10:06 AM
  3. GUI problems.
    By saytri in forum New To Java
    Replies: 1
    Last Post: 12-16-2007, 10:27 PM
  4. many to many problems
    By cecily in forum JDBC
    Replies: 1
    Last Post: 08-02-2007, 05:51 PM
  5. problems with JPA
    By Ed in forum New To Java
    Replies: 2
    Last Post: 07-04-2007, 05:34 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •