macOS C: How to maintain speed?

[jsmwoolf]

In one of the problems that I'm solving on Project Euler, I'm trying to find the first triangle number that has 500 divisors. However, the thing is that my code slows to a crawl after three million. I only have two variables, no macros, no global variables, I'm not storing a triangle number but rather using a formula to determine it, and using only two printfs where one displays the triangle number and the other displays the final result.

How do I maintain that speed so that it'll be quicker? Would pointers do the trick or do I need to take a drastic measure such as learning assembly?

 

[Cromulent]

How do I maintain that speed so that it'll be quicker? Would pointers do the trick or do I need to take a drastic measure such as learning assembly?

9 times out of 10 slow downs are caused by inefficient algorithms. So go over the algorithm you are using and make sure that it is really doing what you think it is.

Also make sure you are not doing something stupid like malloc'ing memory on every iteration.

The other 1 time out of 10 you might benefit from threading.

 

[lee1210]

Are you looping from 0 to n and things go awry when n gets really large? You may need a better algorithm. If the algorithm is not great, implementing it in ASM won't help. Also, are you sure you can write faster ASM than the compiler you're using? I have no idea what these programs are, but I might keep a list of what I've calculated so far, count of its divisors, whatever. Working in parallel or using vector instructions could help, but the speed of one iteration of your code is likely not bad, but doing it millions of times might hurt.

-Lee

 

[jsmwoolf]

Are you looping from 0 to n and things go awry when n gets really large?

It's actually a while loop, but for checking divisors yes!

Also, are you sure you can write faster ASM than the compiler you're using?

I actually don't know anything about assembly. But I do know that the type depends on the hardware unlike C.

Here's what I have so far.

//Removed in order to prevent cheating on Project Euler

Can you guys point out flaws in this algorithm so that I can learn/fix them?

EDIT: It was actually three variables.

 

[lee1210]

You will never find a factor > half of the number you're factoring other than itself, so that will save some time.

I might try a binary search-like approach. Does 5050 have more or less than 500 factors? Does 500,500? Find a really high value that has > 500, and a pretty high value that has < 500. Start "splitting the difference" and adjusting.

I'm sure there's a way better algorithm for factoring, but I'm not a huge math guy, so I don't know what it is. You can likely do the current algorithm in parallel, but this only helps dramatically when you have a lot of cores. Basically you could divide your range to check by N where Nis you core count(maybe minus 1), and do every Nth number in an individual thread with each starting at +1 from the previous thread start. You'll need your divisor increment to be atomic, using a lock, or making it a counting semaphore, etc.

Others might have much better math-based alogorithm tweaks because they know better how math works when it comes to factoring.

-Lee

Edit: I'd make the + 1 in all instances of your triangle number + 1L so you get a long result, otherwise you might overflow. Maybe not an issue, if you know the triangle # closest to INT_MAX has > 500 factors.

 

[jpyc7]

I don't see anything obviously wrong with your algorithm. Obviously, you could calculate the triangleNumber = (n^2+n)/2 once in your loop and keep it in a variable, but the compiler might be smart enough to recognize the calculation anyway.

I would make sure that your variable type is large enough to hold the values being calculated. Obviously, the minimum value of a triangle number with 500 divisors is (500^2 +500)/2. In reality, it is probably a lot bigger. I would not be so sure that a 64 bit integer is large enough.

So when you say it has "slowed down", it might mean that the calculations have rolled-over and the exit condition for the loop will never be true.

 

[chown33]

First observation: for any number > 1, there are always two trivial divisors: 1 and the number itself. So you don't even have to test those, you get 'em for free.

Example:
21: 1,3,7,21
28: 1,2,4,7,14,28


Second observation: The number of divisors depends on the number of prime factors. Every divisor is either a prime factor, or the product of other prime factors. Should be obvious if you think about what it means to be a divisor of the triangle number.

Example:
21: 1,3,7,21
28: 1,2,4,7,14,28

21's prime factors: 3 * 7 = 21.
28's prime factors: 2 * 2 * 7 = 28.

The number of ways to combine prime factors is the number of distinct products you can obtain by multiplying every distinct factor by every other prime factor (distinct combinations, not permutations). "Distinct" means a value you haven't seen before. It's distinct: different from any previous value.

Example:
The prime factors of 28 = 2 * 2 * 7.
2 * 2 = 4, so 4 is another divisor.
2 * 7 = 14, so 14 is another divisor.

So if I was doing this, I'd probably start by finding the prime factors of the triangle number.

Oh, and I'd be testing the program on a much smaller problem, like the first triangle number with more than 6 divisors. Then more than 10. Going for 500 right away is like trying to climb Everest with no preparation. You don't know if your algorithm even works. Prove it works on smaller numbers first, then increase its range. Starting small and working up is a basic programming strategy.

Finally, after the algorithm starts to slow down, I'd try it with 'double' type instead of 'long' type. Because double uses floating-point hardware, and it's usually pretty fast. Whether it's faster than 'long' is worth testing. BUT, it's only worth testing after it's reached the point of noticeable delays. That might be stopping at the first triangle number with 100 divisors, or 150, or whatever. Experiment, but do so with a definite stopping point. You can't measure the elapsed time of an algorithm that doesn't stop.

 

[jsmwoolf]

Actually, I just made more modifies and I actually got my answer. It only took 3-4 seconds to generate.

Anyway, thanks for helping me.

However, I will need to remove the code now in order to prevent cheating.

 

[chown33]

However, I will need to remove the code now in order to prevent cheating.

Really? You think other people's answers can't be found by googling?

Spoiler: (76576500)

 

[jsmwoolf]

I know that you can simply google it, but I want to be one less contributor to cheating.

 

[gnasher729]

In one of the problems that I'm solving on Project Euler, I'm trying to find the first triangle number that has 500 divisors. However, the thing is that my code slows to a crawl after three million. I only have two variables, no macros, no global variables, I'm not storing a triangle number but rather using a formula to determine it, and using only two printfs where one displays the triangle number and the other displays the final result.

How do I maintain that speed so that it'll be quicker? Would pointers do the trick or do I need to take a drastic measure such as learning assembly?

With the Project Euler project, learning assembler will not help you one bit. What will help you is analyzing the problem and finding ways to solve it quickly. For example, you don't need to find the number of divisors, just whether the number is 500 or more or not.
A very little bit of mathematics will show you that for example a 16 digit number with 500 divisors must have a prime factor of 41 or less. For a sixteen digit number, it is quite hard to show that it is a prime (2 divisors) or the product of two large primes (4 divisors), but very easy to show that it doesn't have 500 divisors.

Just noticed: Since this is about finding factors, counting factors of (n^2 + n) / 2 = n * (n + 1) / 2 is especially easy, even if n itself is large (like a full 64 bit number): Either n or n+1 is even, but not both, so divide the even one by two. Then count the factors in each number and multiply the results. That works because n and n+1 have no common factors.

 

[Bill McEnaney]

I don't see anything obviously wrong with your algorithm. Obviously, you could calculate the triangleNumber = (n^2+n)/2 once in your loop and keep it in a variable, but the compiler might be smart enough to recognize the calculation anyway.

Does n's value change in the loop? I don't know whether it does because I haven't read the algorithm.

 

[dmi]

Triangular numbers are of the form n*(n+1)/2 for integer n
n and n+1 are relatively prime, so the number of divisors d(n*(n+1)/2)
= d(n/2)*d(n+1) when n is even and d(n)*d((n+1)/2) when n is odd

 

[dmi]

Another approach could be to find the first 500 divisor number that is triangular

500 divisor number numbers will be of the form
p1^(a1-1)*p2^(a2-1)*p3^(a3-1)*...
where p1,p2,... are prime and a1*a2*... = 500

 

[holmesf]

With the Project Euler project, learning assembler will not help you one bit. What will help you is analyzing the problem and finding ways to solve it quickly. For example, you don't need to find the number of divisors, just whether the number is 500 or more or not.
A very little bit of mathematics will show you that for example a 16 digit number with 500 divisors must have a prime factor of 41 or less. For a sixteen digit number, it is quite hard to show that it is a prime (2 divisors) or the product of two large primes (4 divisors), but very easy to show that it doesn't have 500 divisors.

Just noticed: Since this is about finding factors, counting factors of (n^2 + n) / 2 = n * (n + 1) / 2 is especially easy, even if n itself is large (like a full 64 bit number): Either n or n+1 is even, but not both, so divide the even one by two. Then count the factors in each number and multiply the results. That works because n and n+1 have no common factors.

Correct. Glad someone pointed this out. Note that the problem can also be sped up with dynamic programming. As you proceed, save how many divisors each number has (this can be done in a big array). You can also store an array which holds all of the prime numbers you've found so far (those with 2 divisors). To calculate how many divisors a number has, test for divisibility with primes less than the numbers square root. Once you have found a prime factor p, continue to divide the number by that prime until you no longer can. Now you've factored the number into x = (p^k)*b, where p is a prime and b is what's left over. Since p and b are relatively prime, div(x) = div(p^k)*div(b) = (1+k)*div(b). Since b < x, you've already computed div(b) and can just look up that value in your array.

 

[holmesf]

Another approach could be to find the first 500 divisor number that is triangular

500 divisor number numbers will be of the form
p1^(a1-1)*p2^(a2-1)*p3^(a3-1)*...
where p1,p2,... are prime and a1*a2*... = 500

That strikes me as much harder, but I would be curious if there is an easy way to do it.

It seems like the constraint that a1*a2*... = 500 provides a way to choose the values for ai. But how do we choose the primes to find those combinations that will result in a triangular number? Or barring that, is there a way we can test if the result is triangular?

 

[gnasher729]

That strikes me as much harder, but I would be curious if there is an easy way to do it.

It seems like the constraint that a1*a2*... = 500 provides a way to choose the values for ai. But how do we choose the primes to find those combinations that will result in a triangular number? Or barring that, is there a way we can test if the result is triangular?

For example, a factor that is the fourth power of a prime gives you five divisors (16 has divisors 1, 2, 4, 8 and 16). To have exactly 500 = 5 * 5 * 5 * 2 * 2 divisors, you could have for example prime factors a^4 * b^4 * c^4 * d * e, or a^4 * b^4 * c^4 * d^3, or a^9 * b^4 * c^4 * d, and so on.

As posted before, to calculate the number of divisors of n * (n+1) / 2, you divide the even of n and n+1 by 2, calculate the divisors of each, and multiply. One of them must have a number of divisors that is a multiple of 25, which means it is a multiple of p^4 * q^4, p^9 * q^4, p^9 * q^9, p^19 * q^4, p^24, p^49, p^99, p^124, p^249, or p^499.

We can easily find all numbers of these forms up to 2^63. Let's say x = p^4 * q^4. x is either the odd number out of n and n+1, or half of the even number out of n and n+1. So we can always have (n = 2x, n+1 = 2x+1), or (n = 2x-1, n+1 = 2x). If x is odd then it can be the odd one of n, n+1 so we can have (n = x, n+1 = x+1) or (n = x-1, n+1 = x).

So the number of divisors of x can be multiplied with the number of divisors of 2x+1, 2x-1, and for odd x the number of divisors of (x+1)/2 or (x-1)/2.

So the algorithm: Produce all numbers x where the number of divisors is a multiple of 25, and at the same time divides 500. Then examine the numbers 2x+1, 2x-1, and (x+1)/2 and (x-1)/2 if x is odd, calculate the number of divisors, and check if the product is 500.

Unless x has 125, 250, or 500 factors, the other number must be a factor that is a power of 4, which will be quite rare.

We can restrict the search to values x < 2^63 so the other number is < 2^64 and can be examined easily. That gets rid of the cases p^99, p^124, p^249 and p^499 already. p*q must be less than about 50,000 even for the case of p^4 * q^4, and p^q can be multiplied by a prime, the cube of a prime, or two primes.

 

[dmi]

Are we looking for numbers with 500 divisors, or numbers with more than 500 divisors?
(one of the previous posts suggested 76576500, which has 576 divisors, not 500)
If the latter, it would mean there would be a lot more numbers satisfying the divisor criterion that would need to be tested for triangularity, and a better chance that a given triangular number would meet the divisor criterion, both of which could undo the advantage of approaching it that way.

 

[gnasher729]

Another approach could be to find the first 500 divisor number that is triangular

500 divisor number numbers will be of the form
p1^(a1-1)*p2^(a2-1)*p3^(a3-1)*...
where p1,p2,... are prime and a1*a2*... = 500

Finding triangular numbers with exactly 500 divisors seems difficult, but I think there should be solutions:

Let p, q be odd primes. If pq = 16k + 7 or 16k + 9 then p^4 * q^4 = 32K + 1 for some odd K. If we are lucky and K is the product of two primes, say K = r*s, then we let n = 32K, and

n * (n+1) / 2 = 32K * (32K + 1) / 2 = 16 * r * s * p^4 * q^4

which has exactly 500 divisors.

 

[gnasher729]

Finding triangular numbers with exactly 500 divisors seems difficult, but I think there should be solutions:

Let p, q be odd primes. If pq = 16k + 7 or 16k + 9 then p^4 * q^4 = 32K + 1 for some odd K. If we are lucky and K is the product of two primes, say K = r*s, then we let n = 32K, and

n * (n+1) / 2 = 32K * (32K + 1) / 2 = 16 * r * s * p^4 * q^4

which has exactly 500 divisors.

Checked it. No solutions to be found that way with K < 2^64.
I found a triangular number with exactly 500 factors, and it is huge:

The Cunningham Project for factoring large integers found

2^125 + 1 = p * q = 229668251 * 5519485418336288303251

where the two numbers p and q are both primes.

If we let n = 2^125, then n * (n + 1) / 2 = 2^124 * p * q has exactly 500 divisors. The triangular number is 2^249 + 2^124.

 

[FluJunkie]

I know that you can simply google it, but I want to be one less contributor to cheating.

In the meantime obliterating the usefulness of the discussion for those who might have been interested, and care not the least bit about Project Euler.