One thought on “cumsum(): Cumulative Sum in Maxima”

  1. Although that is a correct, simple solution, it is horribly inefficient for large lists. Selecting the ith element of a list takes time O(i), summing n elements takes time O(n), and you’re doing that O(n) times — so it’s an O(n^3) algorithm. And if the addition operation on your list elements is expensive (say they’re rationals or bigfloats), things are even worse because you’re performing n^2 sums rather than n (though O(n^2) is smaller than O(n^3), the constant may be large).

    A slightly less simple, but much more efficient solution is:

    cs(l) :=
    block([res : [], s : 0],
    while l # [] do (
    s : s + first(l),
    l : rest(l),
    res : cons(s, res)),
    reverse(res))$

    Let’s try the two functions out on some medium-sized examples:

    showtime:true$
    l1000: makelist(i,i,1,1000)
    cumsum(l1000) — 1.26 s
    cs(l1000) — 0.03 s

    How much does compiling help?
    compile(cs,cumsum)
    cumsum(l1000) — 1.05 s
    cs(l1000) — 0.00 s

    What happens with rationals?
    rl1000: 1/l1000
    cumsum(rl1000) — 2.41 s
    cs(rl1000) — 0.00 s

    How about bigfloats?
    bl1000:bfloat(rl1000),fpprec:100$
    cumsum(bl1000) — 2.11 s
    cs(bl1000) — 0.00 s

    Let’s get a better time estimate for cs(bl1000):
    for i thru 1000 do cs(bl1000) — 1.81 s
    i.e. 0.0018 s each, about 1000x faster than cumsum.

    Liked by 1 person

Leave a Reply to Stavros Macrakis Cancel reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s