Results 1 to 20 of 25
Thread: challenging problems
 10262008, 09:13 AM #1
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(); } }
 10262008, 03:03 PM #2
Have you tried debugging your code by adding println() statements to print out every so often to show progress?
 10262008, 03:25 PM #3
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 23
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)); }
 10262008, 05:08 PM #4
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
 10262008, 05:14 PM #5
i checked using println(). upto 10000 its going well but after that its taking long time
 10262008, 05:17 PM #6
ya mod i m working on java IDE .Is there any other way to do that ?
 10262008, 05:18 PM #7
hi norm
but number is too big to work with long or int thats why i m using BigInteger
 10262008, 05:19 PM #8
Have you tried a version that uses int or long?
How long to they take?
 10262008, 08:23 PM #9
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 versionLast edited by Norm; 10262008 at 08:44 PM.
 10262008, 10:21 PM #10
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.
 10272008, 12:07 AM #11
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
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;
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.
 10272008, 12:43 AM #12
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 Threadlocal 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
 10272008, 02:46 AM #1321.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
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; 10272008 at 02:50 AM.
 10272008, 04:34 AM #14
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 23
 10272008, 08:39 AM #15
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
 10272008, 08:41 AM #16
thanks for explanation .............
 10272008, 02:39 PM #17
How long does it take on your computer to run your code for 64M loops?
 10272008, 02:52 PM #18
i wait for 4 hrs but could not get answer
 10282008, 05:12 PM #19
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(); } }
 10282008, 05:21 PM #20
 Join Date
 Jul 2007
 Location
 Colombo, Sri Lanka
 Posts
 11,370
 Blog Entries
 1
 Rep Power
 23
Can you explain what's your question is. Is that take a long time to get a result?
Similar Threads

Is it possible to make this in Java? Challenging question.
By matt_well in forum New To JavaReplies: 24Last Post: 07292008, 05:04 PM 
Problems in JSP : Need help
By raj4u in forum JavaServer Pages (JSP) and JSTLReplies: 1Last Post: 02072008, 11:06 AM 
GUI problems.
By saytri in forum New To JavaReplies: 1Last Post: 12162007, 11:27 PM 
many to many problems
By cecily in forum JDBCReplies: 1Last Post: 08022007, 06:51 PM 
problems with JPA
By Ed in forum New To JavaReplies: 2Last Post: 07042007, 06:34 AM
Bookmarks