cumsum(): Cumulative Sum in Maxima

Yesterday I needed a cumulative sum function in Maxima to do the job of cumsum() in R and MATLAB, but couldn’t find anything.  So here’s a one-liner that does the trick for a list:




2 thoughts 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)),

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

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

    How much does compiling help?
    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?
    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

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

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

Facebook photo

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

Connecting to %s

%d bloggers like this: