Segmentation fault on computations in AA, exactify()

[mkoeppe]

Basic arithmetic with AA can lead to enormous expression trees, which
easily leads to recursion depth errors and excessive memory use.

x = 3*AA(sqrt(2))/200
moves = [ 1/60,  3*AA(sqrt(2))/200, -AA(sqrt(3))/1000 ]
for i in xrange(1000000): x = x + moves[randint(0, len(moves)-1)];
print x
12064.933787495?
x.exactify()
/Users/mkoeppe/bin/sage: line 134: 41236 Segmentation fault: 11  "$SAGE_ROOT/src/bin/sage" "$@"

(I mentioned this to some developers during the Sage Days in Davis in 2013, but didn't follow up on it.)

might be related to #16222. See also the task ticket #18333.

CC: @vbraun @gagern @videlec

Component: number fields

Issue created by migration from https://trac.sagemath.org/ticket/18818

[mkoeppe]

comment:1

Probably AA elements should call exactify at some point when the expression tree becomes too big.

[gagern]

comment:2

Since you're working in AA, not in SR, #16222 doesn't seem related to this. Instead I'd personally guess #17886 should be a suitable solution here. Since #18356 with #18242 is supposedly a more advanced version of that, it should fit the bill, too.

[gagern]

comment:3

Looking at #18333 I found #19955 which aims to get rid of ANUnaryExpr and ANBinaryExpr, thus eliminating the expression trees you mention.

[videlec]

comment:4

It might be subtle to detect these kinds of things. If you are adding a lot of numbers that belong to a common number field you would better use this number field. Possibly using the ready made function

sage: from sage.rings.qqbar import number_field_elements_from_algebraics
sage: number_field_elements_from_algebraics([AA(2).sqrt(), AA(3).sqrt()])
(Number Field in a with defining polynomial y^4 - 4*y^2 + 1,
 [-a^3 + 3*a, -a^2 + 2],
 Ring morphism:
   From: Number Field in a with defining polynomial y^4 - 4*y^2 + 1
   To:   Algebraic Real Field
   Defn: a |--> 0.5176380902050415?)

The ticket #19955 should definitely handle it. However in such case, with #20074 and a little extra help it already "works"

sage: sqrt2 = AA(2).sqrt()
sage: sqrt3 = AA(3).sqrt()
sage: (sqrt2 * sqrt3).exactify()
sage: moves = [ 1/60,  3*sqrt2/200, -sqrt3/1000 ]
... # then same code

But this current "solution" makes the summation much much slower since some checks are made to see whether the addition could remain in a given number field.

[mkoeppe]

comment:5

Replying to @videlec:

If you are adding a lot of numbers that belong to a common number field you would better use this number field. Possibly using the ready made function number_field_elements_from_algebraics

Yes, this is what I'm already using in my application.

The ticket #19955 should definitely handle it. However in such case, with #20074 and a little extra help it already "works"

Great to hear that work is underway to improve QQbar.