3

I have some small piece of software that calculates the number of factors of each triangle number to see what is the first one of them has more than X number of factors (yes, it's a projecteuler problem, number 12,, although i didn't solve it yet)... as am trying making X some random values to see what the code does and in how much time, I noticed something strange (to me at least): until X=47 the execution time increases in obviously normal way, but when X = 48 it increases more than normal, and function calls are much greater than the rate, it (explodes) if I would say that.. why does it do that??

the code:

def fac(n): c=0 for i in range (1,n+1): if n%i==0: c=c+1 return c n=1 while True: summ=0 for i in range (1,n+1): summ=summ+i if fac(summ)>X: break n=n+1 print summ

and when profiling:

when X=45 : 314 function calls in 0.027 CPU seconds when X=46 : 314 function calls in 0.026 CPU seconds when X=47 : 314 function calls in 0.026 CPU seconds when X=48 : 674 function calls in 0.233 CPU seconds when X=49 : 674 function calls in 0.237 CPU seconds

I assume that if I continued I would meet other points that system calls increases and time increases suddenly, and previously there were points like that but time was so small so it did't matter so much.. Why function calls suddenly increases?? Isn't it supposed just to call the function one more time for the new value??

P.S. am using cProfile as a profiler, and X in the code here is just for demonstration, I write the value directly in the code... thank you in advance...

Improve this question
4
  • I was asking if the sudden performance difference may be due to the garbage collector being invoked. I'm just guessing. Commented Aug 6, 2011 at 23:41
  • 1
    @Chris: garbage collection can't be the explanation here because Python's garbage collector only runs when excess allocations exceed a threshold. The code given here does not accumulate allocated data, so the threshold won't be reached, and the collector won't be invoked. Commented Aug 7, 2011 at 0:08
  • Actually it does. Integers are immutable, so the statement c=c+1 does indeed accumulate in memory. However I admit that it's a very small accumulation. I repeat: it's a guess. Commented Aug 7, 2011 at 3:35
  • @Chris: even though integers are immutable, their memory still gets reused. Commented Aug 7, 2011 at 11:34

2 Answers 2

Reset to default
6

Have you looked at the actual values involved?

The first triangular number with more than 47 factors is T(104) = 5460, which has 48 factors.

But the first triangular number with more than 48 factors is T(224) = 25200, which has 90 factors. So no wonder it takes a lot more work.

If your code runs up to T(n), then it calls range 2n times and fac n times, for a total of 3n function calls. Thus for T(104) it requires 312 function calls, and for T(224) it requires 672 function calls. Presumably there are 2 function calls of overhead somewhere that you're not showing us, which explains the profiling results you get.

Your current strategy is not going to get you to the answer for the Project Euler problem. But I can give some hints.

  • Do you have to start over again with summ=0 each time you compute a triangular number?
  • Do you have to loop over all the numbers up to n in order to work out how many divisors it has? Could there be a quicker way? (How many divisors does 216 = 65536 have? Do you have to loop over all the numbers from 1 to 65536?)
  • How many divisors do triangular numbers have? (Look at some small triangular numbers where you can compute the answer.) Can you see any patterns that would help you compute the answer for much bigger triangular numbers?
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Yes.. These points where function calls (explodes) are when the number actually changes.. I was silly not noticing that :)
and +1 for the notes, specially no.3
3

If you check the output you'll see several spikes (sudden increasement) in execution time.

The reason is that the number of loops needed is not going up gradually but abruptly. Print out n after you while True loop and you'll see it.

Note: Euler is math site, don't write brute force algorithms ;)

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.