Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Need help optimizing solution for Project Euler problem #12

I've been having my fun with Project Euler challenges again and I've noticed that my solution for number 12 is one of my slowest at ~593.275 ms per runthrough. This is second to my solution for number 10 at ~1254.593 ms per runthrough. All of my other answers take less than 3 ms to run with most well under 1 ms.

My Java solution for Problem 12:

main():

int index = 1;
long currTriangleNum = 1;

while (numDivisors(currTriangleNum) <= 500) {
    index++;
    currTriangleNum += index;
}

System.out.println(currTriangleNum);

numDivisors():

public static int numDivisors(long num) {  
    int numTotal = 0;

    if (num > 1)
        if (num % 2 == 0) {
            for (long i = 1; i * i <= num; i++)
                if (num % i == 0)
                    numTotal+=2;
        } else {
            // halves the time for odd numbers
            for (long i = 1; i * i <= num; i+=2)
                if (num % i == 0)
                    numTotal+=2;
    }
    else if (num == 0)
        return 0;
    else if (num == 1)
        return 1;
    else (num < 0)
        return numDivisors(num *= -1);

    return numTotal;
 }

.

Looking around the solutions forum, some people found that these formulas (n = (p^a)(q^b)(r^c)... & d(n) = (a+1)(b+1)(c+1)...) worked for them, but I personally don't see how it'd be any faster; faster by hand, perhaps, but not in a program.

.

The basic thought process is as follows:

We want to calculate the number of divisors in 48. By looking at the factor tree below, we can conclude that 48 = (2^4)(3^1) [n = (p^a)(q^b)(r^c)...].

  48
 /  \
2   24
   /  \
  2   12
     /  \
    2   06
       /  \
      2    3 

Knowing this, we construct the formula d(48) = (4+1)(1+1) [d(n) = (a+1)(b+1)(c+1)...] to determine that 48 has 10 factors.

d(n)  = (a+1)(b+1)(c+1)...
d(48) = (4+1)(1+1)
d(48) = (5)(2)
d(48) = 10

.

How can I optimize my code? Are these formulas the best solution? I feel that finding all the prime factors, then implementing the formulas would take longer than the program that I already have in place.

Many thanks,

Justian

EDIT:

Before anyone starts posting links, I have looked around similar questions in SO without any luck - I just can't think up implementations of their methods that would run quicker than what I already have in place.

EDIT2:

My 2nd attempt at the Sieve of Eratosthenes (for Problem 10):

int p = 3, n = 2000000;
long total = 0;
boolean[] sieve = new boolean[n];

for (int i = 3; i < n; i += 2)
    sieve[i] = true;

sieve[2] = true;

while (p * p < n) {
    for (int i = p; i < n; i++)
        if (sieve[i] && (i % p) == 0)
            sieve[i] = false;
    p++;

    while (!sieve[p])
        p++;
}

for (int i = 0; i < n; i++)
    if (sieve[i])
        total += i;

System.out.println(total);

Runs at ~985.399 ms - not too much faster than other method, but hasn't been optimized yet. It works, however.

like image 634
Justian Meyer Avatar asked Aug 01 '10 15:08

Justian Meyer


People also ask

Does Project Euler have solutions?

Problems are of varying difficulty, but each is solvable in less than a minute of CPU time using an efficient algorithm on a modestly powered computer. As of 27 April 2021, Project Euler has more than 1,000,000 users who have solved at least one problem, in over 100 different programming languages.

How do you submit a solution in Project Euler?

You submit the answer to your question, not the program. Step 2: Get a result from your code (the questions are structured such that each problem has a single correct answer you can put in the box. Step 3: Try putting in the result and see if it's correct.

What are Project Euler problems?

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.


1 Answers

Use the underlying mathematical structure, this will dramatically change your program's running time. This also applies to problem 10, by the way; if you can't do it in a few milliseconds, you've used a massively inefficient algorithm. In fact, I advise you to work on problem 10 first, because problem 12 builds on it.

I'm going to give a better algorithm for problem 12 below, but first, here's an observation that should speed up your program significantly. If two numbers x and y are coprime (i.e. they have no common divisor other than 1), then d(x·y) = d(x)·d(y). In particular, for a triangle number, d(n·(n+1)) = d(n)·d(n+1). So instead of iterating over the triangle numbers n·(n+1), iterate over n: this will significantly reduce the size of the arguments passed to d(n).

If you do that optimization, you'll notice that you compute d(n) twice in a row (once as d((n-1)+1) and once as d(n)). This suggests that caching the result of d is a good idea. The algorithm below does it, but also computes d bottom-up rather than top-down, which is more efficient because multiplying is a lot faster than factoring.


Problem 10 can be solved by a simple application of the sieve of Eratosthenes. Fill up an array of booleans (i.e., a bit vector) of size 2000000 such that with sieve[i]==true if i is prime; then sum up the numbers for which sieve[i]==true.

Problem 12 can be solved by a generalization of the sieve of Eratosthenes. Instead of making sieve[i] a boolean indicating whether i is prime, make it a number indicating the number of ways in which it is non-prime, i.e. the number of divisors of i. It is easy to modify the basic sieve of Eratosthenes to do that: rather than set sieve[x*y] to false, add 1 to it.

Several subsequent project Euler problems benefit from a similar approach.

One issue you may have is that in problem 12, it's not clear when to stop computing the sieve. You can go two ways about it:
1. compute the sieve by chunks on demand, a worthwhile programming exercise in itself (this will require more complex code that the second method)
2. or start by overestimating a bound: find some triangle number that has over 500 divisors, you know you'll stop before or at that number.

You can gain more time if you realize that you only need to care about odd numbers, since d(2^k·n) = (k+1)·d(n) if n is odd, and finding k and n given only (2^k·n) is fast on a binary computer. I'll leave the details of that optimization as an exercise.

like image 83
Gilles 'SO- stop being evil' Avatar answered Sep 21 '22 14:09

Gilles 'SO- stop being evil'