#18106: Maximum depth recursion in QQbar
---------------------------------+------------------------
Reporter: vdelecroix | Owner:
Type: defect | Status: new
Priority: major | Milestone: sage-6.6
Component: number fields | Resolution:
Keywords: sd66 | Merged in:
Authors: | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------------+------------------------
Comment (by gagern):
In `exactify` there is a bit of code which adjusts the recursion limit,
increasing it by 10 for every recursive call so it will never be reached.
It was introduced in
[http://git.sagemath.org/sage.git/commit/?id=42b0fb3d75cf0967592d2ffdc731a8a610659b59
42b0fb3] to address #2638. I guess we could use the same for
`_interval_fast` as well.
On the other hand, we could also try addressing the source of this deep
recursion. The way I see it, that's because addition is left associative,
so that cyclotomic polynomial will be a very deep but thin binary tree. If
we had a representation which describes a sum (and perhaps also a product)
of an arbitrary number of algebraic numbers using a single descriptor, the
data structure would become much more shallow.
As a third solution, we might set up our own evaluation machinery for
these trees, with our own stack instead of Python recursion. I haven't yet
worked out all the details, but if this sounds interesting I might write
some code to see how this approach feels.
The way I see it, since the backtrace is about `_interval_fast` and
`_more_precision`, all of this is happening before exact computation is
triggered, right? Do we have any way to find out that exact computation
might in this case be faster than repeated numeric refinement? I fear we
have no way to detect this, but if someone has an idea, please share it.
--
Ticket URL: <http://trac.sagemath.org/ticket/18106#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
