I timed the C version with an older GMP, equivalent to what Magma uses
and it is only 0.5s slower, so that is close to irrelevant. Also in
Magma "interpreter" overhead is most of the time.
Bill.
On 10 Sep, 07:51, Bill Hart <goodwillh...@googlemail.com> wrote:
> 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
-~----------~----~----~----~------~----~------~--~---
