Clever way to sum

General Usage
1

I was wondering whether there’s an efficient way to calculate sums of the form:

Sn = a1-n + a2-n + … + an-n

Currently, I’m just doing something like:

sum(x->x^(-n), a)

I would require all the sums from 1 to n.
The elements of a are complex and, in general, can be small. Is there a particular representation which can reduce floating point error?

2

Yes. The functions sum_kbn and sum_oro exported from AccurateArithmetic.jl.
For a smaller dependency (likely with slower throughput), the function sum_kbn is exported from KahanSummation.jl.

3

You’ll get better answers here with more information. Some questions:

  1. Is there anything special about your a values (e.g. roots of unity?)
  2. Is the n in the a_n the same as the n in the power?
  3. When you say “I would require all the sums from 1 to n” do you mean all the different powers from 1 to n? If so, is n an integer?
4

Should have mentioned that. In order of your questions:

  1. There’s nothing “special” about a[j]. They’re complex-valued random variables drawn from a known (but not standard) distribution.
  2. That was a typo. Sorry! That’s aN (Not used to HTML).
  3. Yes, I do mean that n is an integer. I have some multinomials in Si, which are known to contain at least one power of Si for i in {1,2,3,…,n}.

Thanks, @JeffreySarnoff, for your comment on reducing finite precision error.

5

In that case, I think this is pretty easy. Just use DoubleFloats.jl which will give you an extra 53 bits of accuracy, and instead of computing S_n = sum a_i^-n, compute S_1 = sum inv(a_i) and then just do S_i = sum a_1*a_i-1.