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 <goodwillh...@googlemail.com> wrote:
> On 10 Sep, 07:18, Robert Bradshaw <rober...@math.washington.edu>
> 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 <nbr...@sfu.ca> 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 sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
