[Deanimon]

Good evening,

I am trying to do Project Euler problem 12, and I have the right code, but it's really slow.
This is the description of the problem (projecteuler.net):

Quote

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

This is my code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace Project_Euler
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 1;
            double triangleNumber;
            ArrayList divisors = new ArrayList();

            while (true)
            {
                triangleNumber = 0;
                divisors.Clear();

                for (int i = 1; i <= count; i++)
                {
                    triangleNumber += i;
                }

                for (int i2 = 1; i2 <= triangleNumber; i2++)
                {
                    if (triangleNumber % i2 == 0) divisors.Add(i2);
                }

                Console.Clear();
                Console.WriteLine("Triangle number checked: " + triangleNumber.ToString());
                Console.WriteLine("\nDivisors: " + divisors.Count.ToString());
                if (divisors.Count > 500) break;

                count++;
            }

            Console.ReadKey();
        }
    }
}

This code works (I've tried it with the example). The thing is, it's really slow.
I've let this code run for ~40 minutes and it didn't finish.
Programming is just a hobby of mine, so I didn't really learn how to optimize code.
Could anyone tell me how I could do this, or where I can find information on code optimization for these kind of subjects?

Thanks in advance.

[Skydiver]

To paraphrase something I read from "The Algoritm Design Handbook": Sometime the best optimization is not to optimize the code, but to change to a more efficient algorithm.

So back to your code: assuming that you are sticking with the same algorithm:
- Pre-initialize the capacity of the ArrayList by using the constructor that take the capacity. This save time having reallocate, and copy each time the internal array has to grow. http://msdn.microsof...y/k0bb9cb1.aspx
- Don't use an ArrayList. You are paying the cost of boxing and unboxing. Use a List<int> instead.
- Don't store the intermediate numbers. You are paying the cost of storing the numbers. The problem only requires for you to have the count.

[baavgai]

First, printing takes a while, so don't do it unless you're testing.

You don't need to store the divisors in an ArrayList to count them. Note, you should have used List<int>, if you went that route.

You don't need 1 and n, as they are a given. Just count rest and add 2.

You don't need to start at 0.

Notice the how primes play a role...

[macosxnerd101]

Factoring also helps. If you can factor n = pq, where p and q are relatively prime, then tau(n) = tau(p)tau(q), where tau is the function that counts divisors, defined as follows:
tau(n) = sum_{d|n} 1

Note that d|n reads that d divides n.

Alternatively, if you know how many factors two relatively prime integers have, then you know how many factors their product has.

Just to add some terminology as well. The tau function is multiplicative, but not completely multiplicative. That is, if p and q are not relatively prime, then the formula tau(n) = tau(p)tau(q) does not hold.

This post has been edited by macosxnerd101: 03 July 2013 - 12:51 PM
Reason for edit:: Needed tau, not sigma

[Deanimon]

Thanks for all the great, quick responses!

I thought the slowness was a result of bad code, not a bad algorithm.
My whole aproach was wrong and using an arraylist to count the divisors was just silly.

As you could probably see from my code, I am not experienced with writing efficiënt algorithms.
I am now trying to find a solution using this method.
I am trying to find the primes with the sieve of Eratosthenes.

If anyone sees a problem with this aproach, please let me know.
Otherwise, my question has been answered.
I will view this kind of problems from a whole different angle.

Thanks!

[macosxnerd101]

Your problem there is still factoring. Pollard-rho can factor in O(n^1/4 log(n)) time, which is really efficient. The Euclidean algorithm can test for coprimality in O(log(n)) time.

[Skydiver]

baavgai, on 03 July 2013 - 01:32 PM, said:

Notice the how primes play a role...

LOL! The first time I read that sentence, I read "role" as "factor" and I was about ready to applaud you for the pun!

[Skydiver]

Everybody jumped on changing the algorithm which is good. I noticed though that every suggestion focused on the code that figures out what the factors are for a triangle number. (ie. the second inner loop) This is good since most of your time is spent there.

I would like to point out that you could do better computing the next triangle number. (ie. the first inner loop) Notice the pattern for the i-th triangle number:

i   triangleNumber
1   1
2   3
3   6
4   10
5   15
:
i   triangleNumber[i-1] + i
:

You can apply some dynamic programming techniques in this case.

And then back to the all important second inner loop: One of my little algorithm changes other than taking advantage of prime numbers, was also to keep track of the last set of primes I had computed. That way I would recycle the previously found prime numbers, and only have to worry about the other primes.

This post has been edited by Skydiver: 03 July 2013 - 09:18 PM

[Deanimon]

I 'optimized' the algorithm some more, and it finished in 30 minutes.
I couldn't figure out a way to efficiently find the prime factors.
I looked into the Pollard Rho algorithm, but it was too complex for me to think of an efficient way to find the prime factors.

I did realize something that solved the problem completely: a divisor is a couple with another divisor.
1 divisor is below the square root of the triangle number and 1 divisor is above it (unless it's the square root ofcourse).
So I only had to check the whole numbers up until the square root and add 2 to the divisors whenever a divisor is found.
I implemented this into my code and the solution was found in just 394 ms:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Project_Euler
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = 1;
            int triangleNumber = 0;
            int sqrtTriangleNumber;
            short divisors;

            while (true)
            {
                triangleNumber += count;
                sqrtTriangleNumber = (int)Math.Floor(Math.Sqrt(triangleNumber));
                divisors = 2;
                
                for (int i = 2; i <= sqrtTriangleNumber; i++)
                {
                    if (triangleNumber % i == 0) divisors += 2;
                }

                if (divisors > 500) break;

                count++;
            }

            Console.WriteLine("Triangle number checked: " + triangleNumber.ToString());
            Console.WriteLine("Divisors: " + divisors.ToString());
            Console.ReadKey();
        }
    }
}

Again, thanks for the great help. It wil certainly help me analyze and solve future problems differently.

[macosxnerd101]

Great work! And thanks for sharing your solution!

[Momerath]

One way to optimize it more is to realize that the triangle number is n(n+1)/2. This gives you two numbers (n, n+1) to factor, subtract one from one of the 2^x (as one of the numbers will always be even) and use the method (linked) above to calculate the number of factors. Realize that one of the components of the next triangle number (n+1) will already have been factored from the previous round and you only have to factor one number at a time (that is smaller than factoring the entire triangle number).

If you do this right, your solution will show up in less than 4 seconds />/>

This post has been edited by Momerath: 04 July 2013 - 11:58 AM

[Skydiver]

<rant>
And this is one of the major reasons why I abandoned Project Euler. It has a heavy mathematical slant where optimal solutions rely on a (very) strong math background. I've been assured by people before that the problems can be solved without knowing any math beyond what one would learn in high school. Unfortunately, I think they were assuming that I went to a high school that was following the "High School College Preparatory Math Plan of Study" rather than the "High School Career Preparatory Math". ( http://712educators....h_studyplan.htm )

Without the more in depth theory provided by the college preparatory plan, I can only approach problems taking the naive approach of "plugging in the numbers, and let the computer do the hard computations". As shown above, the time it takes to solve the PE problems using the naive approach can take a long time. Major shortcuts can be made by gleaning more understanding from the relationships of the numbers. It was disheartening to leave my computer running a C/C++ programm overnight to come up with an answer while the people would post on PE's forums that they were finding solutions in minutes or seconds... with an interpreted language like Python, Ruby, or LISP!

I've been finding the Rosalind problems more satisfying to solve.
</rant>

[Deanimon]

Momerath, thanks for posting your insights! I did know of that formula, but I didn't think it would be this useful. I won't implement it though, because 0.4 seconds (394 ms = 0.394 s ) is good enough for me, and I want to focus on the other problems Project Euler has to offer (I have currently solved problems 1-20).

Skydiver, that's not really a problem for me, since I do this for practicing programming and maths to prepare myself for an assignment I have to do next year (I'm still in high school). Hard problems motivate me to learn more of the background behind the problem (even though I might not understand it with the knowledge I have now...).

[Psyguy]

Well, Deanimon...you are a much better student than I ever was. I didn't even get past Algebra until college, which wasn't for five or so years after I graduated from high school.

Skydiver, I too find the problems at Project Euler very frustrating because of the heavy math knowledge required to solve some of the problems. I have also left the computer running overnight, but at some point I decided that if it can't run in five minutes, there has to be a better way of doing it. I have solved 25ish problems on there. I've also noticed that the difficulty dramatically increases after the first twenty problems.

I think I'm going to go check out Rosalind.

[Momerath]

I took calculus in High School, then 4 more years of math in College. I've finished about 90 of the Project Euler problems. I don't find the math particularly difficult, what I do find difficult is that you need to know everything Euler ever worked on as the problems all relate back to math he's done. No course I took specialized in teaching just one mathematician's work. I've asked people with math degrees (up to PhD level) and they aren't much help on these either.

So, if you want solve a lot of the problems, study Euler