# Loops get slower as they run

Hello, I am trying to run a simulation in sage as part of my homework. The simulation itself is pretty fast and working fine. The problem starts when i try to run the simulation several times in a loop, then sage becomes incredibly slow in each repeat.

The program I wrote:

def poisson(lmu):
var('mu n')
g(mu,n)=(e^-mu * mu^n)/factorial(n)
num=random()
sum=g(lmu,0)

for i in xrange(1000):
if num<sum:
return i-1
else:
sum=sum+g(lmu,i)

def galtonwatson(mu,s,gens):
deaths=0
for i in range (gens):
N=1
n=0
while n<s and N!=0:
N=poisson(N*mu)

n=n+1
if N==0:
deaths=deaths+1
return (deaths/gens).N()


both of the functions works fine, then telling sage to fill a list of 10 arrays with the values, and checking how much time it took for each repeat:

L=np.array([[0,0]for i in range(9)])
for i in xrange (9):
t=time.time()
print i
L[i]= (i,galtonwatson(2,i,100))
print (time.time()-t)


Sage output is:

0
0.000202894210815
1
0.393799066544
2
0.893945932388
3
1.54169392586
4
2.87310600281
5
4.84653711319
6
9.23449707031
7
18.3007540703
8
35.5397469997


It ain't the first time that sage loops becomes slower and slower on the run, and I could'nt understand the reason when searching the net.

edit retag close merge delete

Sort by » oldest newest most voted

There are (at least) two reasons why your computations get slower when i increases.

First, in the galtonwatson function, the while loops is basically run i times. For example, you can print i,n after leaving the while loop to see this. So of course the bigger i is, the more computation there will be. But this only explains a linear grow in the time of your computation.

Second, when you write g(mu,n)=(e^-mu * mu^n)/factorial(n) in the poisson function, you define a symbolic expression, hence the variable sum is also a symbolic expression. The size of this expression can (and actually does) grow with your computation. If you add a print sum in your first function just before returning i-1, you will see that it starts with small expressions such as 14*e^(-4), but when the number i of loops increases, N also increases so that poisson() gets huge entries and has to deal with long symbolic expression, that require more work to be dealt with (comparisons and additions in your case). For example at some point in your computation, the poisson function has to deal with expressions like 2550238050428406819213469230186796710457038334913297649020437009290776623587690225849958231171422547635982429757061594176295874263901615544026377448805360196385122323653063241084162785437552154577478465216934451591637439914252547465299853699560543796189133899256924947210666913788957676219447233148368101219341018550501213846576116206037455500877981155501490135406458094080344650729126/70844983299568090322110112742920523338416993100768511830154325532394931272007563144745759540627587853267356431624585717416519870692624578946059813830541826543646017674726402935877414919947084600537371110174386759651317089097190938443583025355782216979691251401707319246270344592630863189697265625*e^(-204) and it gets even worse after that.

The same issue appears with rational numbers: they do not have a constant size, so it is likely that iterated computation will lead to rationals with bigger and bigger numerators and denominators. If you want to avoid such explosion of the size of the data that you manipulate, you can work with floating point numbers instead, since those keep constant size along the computation.

sage: a
2550238050428406819213469230186796710457038334913297649020437009290776623587690225849958231171422547635982429757061594176295874263901615544026377448805360196385122323653063241084162785437552154577478465216934451591637439914252547465299853699560543796189133899256924947210666913788957676219447233148368101219341018550501213846576116206037455500877981155501490135406458094080344650729126/70844983299568090322110112742920523338416993100768511830154325532394931272007563144745759540627587853267356431624585717416519870692624578946059813830541826543646017674726402935877414919947084600537371110174386759651317089097190938443583025355782216979691251401707319246270344592630863189697265625*e^(-204)
sage: RDF(a)
0.9124252826570382

more

Thank you very much! I did learnt a lot from your answer =]

Sorry for the late response to your answer, actually I just now realized that i forgot to reply earlier

( 2015-04-23 23:46:24 +0100 )edit