views:

978

answers:

11

Which programming language or a library is able to process infinite series (like geometric or harmonic)? It perhaps must have a database of some well-known series and automatically give proper values in case of convergence, and maybe generate an exception in case of divergence.

For example, in Python it could look like:

sum  = 0
sign = -1.0
for i in range(1,Infinity,2):
     sign = -sign
     sum += sign / i

then, sum must be math.pi/4 without doing any computations in the loop (because it's a well-known sum).

+17  A: 

Most functional languages which evaluate lazily can simulate the processing of infinite series. Of course, on a finite computer it is not possible to process infinite series, as I am sure you are aware. Off the top of my head, I guess Mathematica can do most of what you might want, I suspect that Maple can too, maybe Sage and other computer-algebra systems and I'd be surprised if you can't find a Haskell implementation that suits you.

EDIT to clarify for OP: I do not propose generating infinite loops. Lazy evaluation allows you to write programs (or functions) which simulate infinite series, programs which themselves are finite in time and space. With such languages you can determine many of the properties, such as convergence, of the simulated infinite series with considerable accuracy and some degree of certainty. Try Mathematica or, if you don't have access to it, try Wolfram Alpha to see what one system can do for you.

High Performance Mark
But I am not interested in generating infinite loops, I need answers, based on knowledge about already studied sums.
psihodelia
Then you need computer-algebra system, not programming language.
Łukasz
Mathematica is one of my favourite daily tools, and it or a similar algebra system is indeed required if you want to be able to pretty-print the symbol π as a symbolic answer. If you just want guaranteed correct processing of the limit, then lazy functional languages like SML/Haskell/OCaml provide the framework needed to build limit evaluators which can dynamically generate as many digits of the answer as needed so that arithmetic operations and comparisons are guaranteed to have the correct behaviour.
Nicholas Wilson
+1  A: 

I have worked in couple of Huge Data Series for Research purpose. I used Matlab for that. I didn't know it can/can't process Infinite Series.

But I think there is a possibility. U can try :)

Imrul
+15  A: 

One place to look might be the Wikipedia category of Computer Algebra Systems.

John
+8  A: 

For Python check out SymPy - clone of Mathematica and Matlab.

There is also a heavier Python-based math-processing tool called Sage.

rlotun
+3  A: 

Clojure and Haskell off the top of my head.

Sorry I couldn't find a better link to haskell's sequences, if someone else has it, please let me know and I'll update.

dsm
Haskell has infinite lists but it can't evaluate an infinite series to a single value...you'd have to write the function that predicts where a list converges to and I don't think that would be simple.
CiscoIPPhone
+11  A: 

Maxima can calculate some infinite sums, but in this particular case it doesn't seem to find the answer :-s

(%i1) sum((-1)^k/(2*k), k, 1, inf), simpsum;
                                 inf
                                 ====       k
                                 \     (- 1)
                                  >    ------
                                 /       k
                                 ====
                                 k = 1
(%o1)                            ------------
                                      2

but for example, those work:

(%i2) sum(1/(k^2), k, 1, inf), simpsum;
                                        2
                                     %pi
(%o2)                                ----
                                      6

(%i3) sum((1/2^k), k, 1, inf), simpsum;
(%o3)                                  1
fortran
I think there's a typo in your translation of the OP's formula: shouldn't it be sum((-1)^(k-1)/(2*k-1), k, 1, inf)? No idea if that makes a difference to maxima's ability to solve them :)
Mike Dinsdale
@Mike, yeah, I saw that after posting, but it doesn't make much difference, Maxima is still incapable of solving it :-( I tried decomposing it in two parts (the positive and negative sums), but it didn't help
fortran
Well, Mathematica can solve all 3 of these.
High Performance Mark
@HPM I bet so, that's why you have to pay for it xD
fortran
+11  A: 

There are two tools available in Haskell for this beyond simply supporting infinite lists.

First there is a module that supports looking up sequences in OEIS. This can be applied to the first few terms of your series and can help you identify a series for which you don't know the closed form, etc. The other is the 'CReal' library of computable reals. If you have the ability to generate an ever improving bound on your value (i.e. by summing over the prefix, you can declare that as a computable real number which admits a partial ordering, etc. In many ways this gives you a value that you can use like the sum above.

However in general computing the equality of two streams requires an oracle for the halting problem, so no language will do what you want in full generality, though some computer algebra systems like Mathematica can try.

Edward Kmett
+4  A: 

You need something that can do a symbolic computation like Mathematica. You can also consider quering wolframaplha: sum((-1)^i*1/i, i, 1 , inf)

Piotr Czapla
It should be sum `(-1)^i/(2*i+1), i, 0, inf` http://www.wolframalpha.com/input/?i=sum++%28-1%29^i%2F%282*i%2B1%29%2C+i%2C+0%2C+inf
J.F. Sebastian
+3  A: 

There is a library called mpmath(python), a module of sympy, which provides the series support for sympy( I believe it also backs sage).
More specifically, all of the series stuff can be found here: Series documentation

mpd
+2  A: 

The C++ iRRAM library performs real arithmetic exactly. Among other things it can compute limits exactly using the limit function. The homepage for iRRAM is here. Check out the limit function in the documentation. Note that I'm not talking about arbitrary precision arithmetic. This is exact arithmetic, for a sensible definition of exact. Here's their code to compute e exactly, pulled from the example on their web site:

//---------------------------------------------------------------------
// Compute an approximation to e=2.71.. up to an error of 2^p
 REAL e_approx (int p)
{
  if ( p >= 2 ) return 0;

  REAL y=1,z=2;
  int i=2;
  while ( !bound(y,p-1) ) {
    y=y/i;
    z=z+y;
    i+=1;
  }
  return z;
};

//---------------------------------------------------------------------
// Compute the exact value of  e=2.71.. 
REAL e()
{
  return limit(e_approx);
};
+1  A: 

You can solve the series problem in Sage (a free Python-based math software system) exactly as follows:

sage: k = var('k'); sum((-1)^k/(2*k+1), k, 1, infinity)
1/4*pi - 1

Behind the scenes, this is really using Maxima (a component of Sage).