Ask Your Question
1

Loops get slower as they run

asked 2015-01-07 05:01:41 -0500

OaaH gravatar image

updated 2015-01-07 07:52:07 -0500

tmonteil gravatar image

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.

Thanks in advanced, David

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
5

answered 2015-01-07 09:30:50 -0500

tmonteil gravatar image

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
edit flag offensive delete link more

Comments

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

OaaH gravatar imageOaaH ( 2015-04-23 16:46:24 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2015-01-07 05:01:41 -0500

Seen: 110 times

Last updated: Jan 07 '15