Magma seems to do something different (though note Magma uses GMP 4.2.1 not a recent GMP or MPIR which would be faster at the actual arithmetic.
function fibo(n) function> a:=1; function> b:=1; function> c:=0; function> for i := 1 to n do function|for> c:=a; function|for> a:=b; function|for> b:=c; function|for> end for; function> return b; function> end function; function test(n,m) function> for j := 1 to m do function|for> s:=fibo(n); function|for> end for; function> return 0; function> end function; > time test(4000,4000); 0 Time: 2.700 function fibo(n) function> a:=1; function> b:=1; function> c:=0; function> for i := 1 to n do function|for> c:=a; function|for> a:=a+b;; function|for> c:=b; function|for> end for; function> return b; function> end function; function test(n,m) function> for j := 1 to m do function|for> s:=fibo(n); function|for> end for; function> return 0; function> end function; time test(4000,4000); 0 Time: 3.460 function fibo(n) function> a:=1; function> b:=1; function> c:=0; function> for i := 1 to n do function|for> c:=a; function|for> a:=a+b;; function|for> b:=c; function|for> end for; function> return b; function> end function; function test(n,m) function> for j := 1 to m do function|for> s:=fibo(n); function|for> end for; function> return 0; function> end function; time test(4000,4000); 0 Time: 5.780 Bill. On 10 Sep, 07:34, Bill Hart <[email protected]> wrote: > On 10 Sep, 07:18, Robert Bradshaw <[email protected]> > wrote: > > > On Sep 9, 2009, at 10:38 PM, Bill Hart wrote: > > > > This program only takes 0.68s in C using a pretty naive mpz program on > > > sage.math. I doubt the memory allocation is really relevant. The > > > interpreter overhead is by far the greatest component > > > Not allocation of the mpz_t's themselves, but allocation of the > > wrapping objects (or, even if there's a pool, the recycling of them). > > Maybe you count this in interpreter overhead. > > Thanks, that occurred to me afterwards. So, I think you are right. If > there are no mpz's or adds the time drops dramatically. > > sage: def fibo(n): > a=1 > b=1 > c=0 > for i in range(n): > c=a > a=b > b=c > return b > ...: > sage: def test(n,m): > ...: for i in range(m): > ...: _=fibo(n) > ...: > sage: timeit("test(4000,4000)") > 5 loops, best of 3: 1.25 s per loop > > With additions but no mpz's > > sage: def fibo(n): > a=1 > b=1 > c=0 > for i in range(n): > c=a > a=a+b > c=b > return b > ...: > sage: def test(n,m): > ...: for i in range(m): > ...: _=fibo(n) > ...: > sage: timeit("test(4000,4000)") > 5 loops, best of 3: 2.66 s per loop > > Bill. > > > > > > > There's also coercion overhead--a+b must verify a and b are both > > integers before calling the integer add function. (I'd guess that's > > less than 10-20%.) > > > - Robert > > > > On 9 Sep, 17:57, Nils Bruin <[email protected]> wrote: > > >> Inspired by a little experiment we did to see if there is room to > > >> improve to ECL's bignum performance, we ran a little experiment > > >> computing fibonacci numbers (we wanted to test addition because it > > >> was > > >> mainly ECL's memory management that was under consideration) > > > >> with the following defs: > > > >> def fibo(n): > > >> a=1 > > >> b=1 > > >> c=0 > > >> for i in range(n): > > >> c=a > > >> a=a+b > > >> b=c > > >> return b > > > >> def test(n,m): > > >> for i in range(m): > > >> _=fibo(n) > > > >> sage: timeit("test(4000,4000)") > > >> 5 loops, best of 3: 6.99 s per loop > > >> sage: time test(4000,4000) > > >> CPU times: user 7.10 s, sys: 0.00 s, total: 7.10 s > > >> Wall time: 7.11 s > > >> sage: time test(4000,4000) > > >> CPU times: user 7.24 s, sys: 0.00 s, total: 7.24 s > > >> Wall time: 7.24 s > > >> sage: time test(4000,4000) > > >> CPU times: user 7.38 s, sys: 0.00 s, total: 7.38 s > > >> Wall time: 7.39 s > > >> sage: time test(4000,4000) > > >> CPU times: user 7.10 s, sys: 0.00 s, total: 7.10 s > > >> Wall time: 7.11 s > > >> sage: time test(4000,4000) > > >> CPU times: user 7.05 s, sys: 0.00 s, total: 7.05 s > > >> Wall time: 7.06 s > > > >> In ECL, this took 14.8 sec (uncompiled) and 8.8 sec (compiled). Of > > >> course, this particular programming exercise was just to see how fast > > >> one can shove information into GMP and ECL at this point definitely > > >> doesn't claim to be particularly optimized for that particular task, > > >> but as you can see, straightforward python and sage do a good job. > > > >> For comparison, Magma takes about 8.4 secs, as does the code above > > >> when I initialize a=int(1) etc. --~--~---------~--~----~------------~-------~--~----~ To post to this group, send an email to [email protected] To unsubscribe from this group, send an email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
