• Post Reply Bookmark Topic Watch Topic
  • New Topic

Need help making my implementation faster  RSS feed

 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok. so I've recently discovered the website www.projecteuler.net; and I'm trying to solve as many of them as I can. But I keep running into the problem of my implementation taking too long, 30 minutes or more to finish. I was wondering if someone could give me some insight into why that happens.

Here's the code:


Any insights will help. Thanks.

Hunter M.
 
Clyde DeSouza
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think you have posted this same query in intermediate section also!

Wait iam on to it would provide you the answer in a short while!
 
Campbell Ritchie
Marshal
Posts: 56530
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Joywish Man wrote:I think you have posted this same query in intermediate section also!
I don't think he has asked twice.
 
Campbell Ritchie
Marshal
Posts: 56530
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I might move you to the intermediate forum; Project Euler exercises are hardly beginners' material.

You may be using too much memory using an array.
For Project Euler, the interesting part is working out the algorithm; I think you may need to write that on paper and see what it looks like.
Did you get an answer? Was it correct? Will it fit into an int without having to use java.math.BigInteger?
Try missing out the print statements; that may speed things up.
 
Clyde DeSouza
Greenhorn
Posts: 26
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
aha i mistakenly confused it with other problem on ranch my mistake !
Ritchie did you try out his problem !!!
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I wasn't really sure which forum to post in so I just picked this one, I'll post in Intermediate from now on.
The result fit into a normal integer, so i didn't have to use java.Math.BigInteger.
I took out the print statements, but that didnt really affect the time taken that much.
The answer I got was correct.

Hunter M.
 
Campbell Ritchie
Marshal
Posts: 56530
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You are going to have to look at the algorithm, and see which bits you can omit. Try writing it out on paper.

You may be able to save a little time by not using the array, but at present your algorithm seems to have quadratic complexity.

What does it say about running time on the Project Euler website?
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well the trouble I'm having trying to compare solutions with other people on their website is that I can only really understand Java code and Ada code. Few People use java and I havent seen a post in Ada. Most of them are in languages I've never used like Ruby, Python, Delphi, or Assembler.

Number of Divisors(by hand):
Given a number n you divide n by all numbers from 1 to n, if the number divides evenly it means that it is a divisor of n.

Example:
n = 21

21/1 = 21 Divisor
21/2
21/3 = 7 Divisor
21/4
21/5
21/6
21/7 = 3 Divisor
21/8
21/9
21/10
21/11
21/12
21/13
21/14
21/15
21/16
21/17
21/18
21/19
21/20
21/21 = 1 Divisor

So all the divisors of 21 are:
1,3,7,21

Hunter M.
 
Garrett Rowe
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One minor optimization I see right away is, if you know 21 is a divisor, then you also know 21 / 21 == 1 so 1 must be a divisor also. So you really only need to do the trial division from 1 to √n. And since 1 is the trivial case, really you only need to go from 2 to √n.
 
Campbell Ritchie
Marshal
Posts: 56530
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As far as √n? Of course! Thank you, Garrett.

I had thought you could get away with going as far as n / 2, but √n is far better. Remember that if 21 divides by 1 and 21 divides by 21, that gives 2 to start with, then start counting from 2 till you get to √21. That will change its complexity from O(n^2) to O(n^1.5).
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Nice, I changed the upper bound to Math.sqrt(n) then incremented by two to account for n/1 and n/n;

now it looks like this:



This change got me the correct answer in a much faster amount of time. If i can ask though why do you only need to go from 1 to Math.sqrt(n). Is that because you assume there are no more factors of n after Math.sqrt(n)??

Thanks,
Hunter M.
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hunter McMillen wrote:Nice, I changed the upper bound to Math.sqrt(n) then incremented by two to account for n/1 and n/n;

now it looks like this:



This change got me the correct answer in a much faster amount of time. If i can ask though why do you only need to go from 1 to Math.sqrt(n). Is that because you assume there are no more factors of n after Math.sqrt(n)??

Thanks,
Hunter M.


Why do we only need to go to Sqrt(n)? Each even division of a number is between a 'low' number and a 'high' number, for example 1 - 21, 3 - 7. The square root is where the 'low' number = the 'high' number, so it represents the cutoff where if you already counted divisors on the 'low' side of the square root, then you already have accounted for their (the divisors') multipliers on the 'high' side of the square root.

One question, how many divisors do you get with your code when you use x = 9, or x = 25? How many should there be?

You may be able to make it a tad faster for some cases by checking if x % 2 == 0 first, and if it is not then you can cut your comparisons in half (increment your loop by 2, rather than 1).
 
Campbell Ritchie
Marshal
Posts: 56530
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And remember, unless the "middle" value is exactly √n (whole number a perfect square, eg 1+2+3+4+5+6+7+8 = 36, √36 = 6), each time you get a divisor, assume you have 2 divisors each time.
eg 3 is a divisor for 21, so you count it as 2 divisors, there being one >√21 (about 4.6) which you overlook. That number is of course 7.
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
For both 9 and 25 my method says they have 2 factors, but they actually each have 3.
9: 1,3,9 25:1,5,25

hmmm not really sure why that is.

Hunter.
 
Campbell Ritchie
Marshal
Posts: 56530
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hunter McMillen wrote:
If the number is a perfect square, eg 36 as stated previously, you need to catch the 6 in the middle. A < will miss that out.
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ok so I understand that now, but a <= will give me one more divisor than I need. Should I be checking if x is a perfect square before I increment??
 
Hunter McMillen
Ranch Hand
Posts: 492
Firefox Browser Linux VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok I think I have it now, see if this looks alright.



Thanks everyone for their help, I'll probably have more questions about projecteuler soon

Hunter M.
 
Campbell Ritchie
Marshal
Posts: 56530
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're welcome Following Garrett's suggestion about square root, I got it to complete in about 2 seconds.
 
Steve Luke
Bartender
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:You're welcome Following Garrett's suggestion about square root, I got it to complete in about 2 seconds.


Speed here is relative to the machine, but I was able to shave 25% of the execution time by skipping even numbers when n % 2 != 0 (I guess this is expected, save half the time, for half the tested values). My timing went from 984ms to 734ms
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!