On Mon, Mar 31, 2008 at 1:04 AM, Simon King <[EMAIL PROTECTED]> wrote:
>
> Dear Sage team,
>
> i made a few timings with the "sum" function:
>
> sage: L2=range(100)
> sage: L3=range(1000)
> sage: L4=range(10000)
> sage: L5=range(100000)
> sage: L6=range(1000000)
> sage: timeit('a=sum(L2,0)')
> 625 loops, best of 3: 299 µs per loop
> sage: timeit('a=sum(L3,0)')
> 125 loops, best of 3: 1.35 ms per loop
> sage: timeit('a=sum(L4,0)')
> 25 loops, best of 3: 13.6 ms per loop
> sage: timeit('a=sum(L5,0)')
> 5 loops, best of 3: 138 ms per loop
> sage: timeit('a=sum(L6,0)')
> 5 loops, best of 3: 1.37 s per loop
>
> So, it seems that the time grows about linearly in the length of the
> list. Shouldn't it be possible to have it growing logarithmically?
> Namely when sum(L) splits L into two sub-lists L0,L1 of about the same
> size and returns sum(L0)+sum(L1)? Or would this introduce a huge
> overhead?
>
> I am not a computer scientist, so perhaps i am mistaken. Where is the
> source code of the sum function?
Hi,
I'm not a computer scientist either, but I was as an undergrad, and
I learned in Computer Science 101 that if the size of the input to an
algorithm is n, then it is impossible to have better complexity
than linear in n, since it takes n steps to *read in the input*.
(Same goes for the size of the output.)
Thus it is nuts to think that you can add the
elements of a (random) list of length n in less than n steps.
That said, it might be a good idea to use a tree like algorithm if
balanced arithmetic helps out (for computing factorials this is
dramatically the case, since multiplying a big and small number
is way worse asymptotically than multiplying two big numbers).
-- William
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
