posted 8 years ago

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.

Here's the code:

Any insights will help. Thanks.

Hunter M.

"If the facts don't fit the theory, get new facts" --Albert Einstein

Clyde DeSouza

Greenhorn

Posts: 26

Campbell Ritchie

Marshal

Posts: 56530

172

Campbell Ritchie

Marshal

Posts: 56530

172

posted 8 years ago

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

Try missing out the print statements; that may speed things up.

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

posted 8 years ago

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.

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.

"If the facts don't fit the theory, get new facts" --Albert Einstein

Campbell Ritchie

Marshal

Posts: 56530

172

posted 8 years ago

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?

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?

posted 8 years ago

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.

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.

"If the facts don't fit the theory, get new facts" --Albert Einstein

Garrett Rowe

Ranch Hand

Posts: 1296

posted 8 years ago

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.

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

Campbell Ritchie

Marshal

Posts: 56530

172

posted 8 years ago

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).

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).

posted 8 years ago

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.

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.

"If the facts don't fit the theory, get new facts" --Albert Einstein

posted 8 years ago

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).

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).

Steve

Campbell Ritchie

Marshal

Posts: 56530

172

posted 8 years ago

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.

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.

Campbell Ritchie

Marshal

Posts: 56530

172

Campbell Ritchie

Marshal

Posts: 56530

172

posted 8 years ago

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

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

Steve