Long Expression Crashes SymPy

I'm using 64-bit Python 3.3.1, pylab and 32GB system RAM. This function: def sqrt2Expansion(limit): x = Symbol('x') term = 1+1/x for _ in range(limit): term

Solution 1:

I will try to elaborate on the comment that I have posted above.

Sympy expressions are trees. Each operation is a node which has as branches its operands. For instance x+y looks like Add(x, y) and x*(y+z) like Mul(x, Add(y, z)).

Usually these expressions get automatically flattened like in Add(x, Add(y, z)) becoming Add(x, y, z), but for more complicated cases one can get very deep trees.

And deep trees can pose problems especially when either the interpreter or the library itself limits the depth of permitted recursion (as a protection against infinite recursion and exploding memory usage). Most probably this is the cause of your RuntimeError: each subs makes the tree deeper and as the tree gets deeper the recursive subs must call itself more times till it gets to the deepest node.

You can simplify the tree to something of the form polynomial/polynomial which has constant depth by using the factor method. Just change term = term.subs({x: (2+1/x)}) to term = term.subs({x: (2+1/x)}).factor().

Solution 2:

Is there a reason that you need to do it symbolically? Just start with 2 and work from there. You will never hit recursion errors because the fraction will be flattened at each stage

In [10]: def sqrt2(limit):
   ....:     expr = Rational(1, 2)
   ....:     for i in range(limit):
   ....:         expr = 1/(2 + expr)
   ....:     return 1 + expr
   ....:

In [11]: sqrt2(100)
Out[11]:
552191743651117350907374866615429308899
───────────────────────────────────────
390458526450928779826062879981346977190

In [12]: sqrt2(100).evalf()
Out[12]: 1.41421356237310

In [13]: sqrt(2).evalf()
Out[13]: 1.41421356237310

In [15]: print sqrt2(1000)
173862817361510048113392732063287518809190824104684245763570072944177841306522186007881248757647526155598965224342185265607829530599877063992267115274300302346065892232737657351612082318884085720085755135975481584205200521472790368849847501114423133808690827279667023048950325351004049478273731369644053281603356987998498457434883570613383878936628838144874794543267245536801570068899/122939577152521961584762100253767379068957010866562498780385985503882964809611193975682098617378531179669585936977443997763999765977165585582873799618452910919591841027248057559735534272951945685362378851460989224784933532517808336113862600995844634542449976278852113745996406252046638163909206307472156724372191132577490597501908825040117098606797865940229949194369495682751575387690