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:
cumsum(L):=makelist(sum(L[i],i,1,n),n,1,length(L))$
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:
cumsum(L):=makelist(sum(L[i],i,1,n),n,1,length(L))$
The MaximaList 
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.
LikeLiked by 1 person