Sage: Ticket #18106: QQbar: make sum and product n-ary and remove recursive calls
https://trac.sagemath.org/ticket/18106
<p>
In QQbar, there are currently many operations that involve recursive calls. For example, this rather simple example gives an error because the Python stack gets filled:
</p>
<pre class="wiki">sage: a = QQbar.zeta(1009)
sage: p = cyclotomic_polynomial(1009)
sage: b = p(a)
sage: b
0.?e-12 + 0.?e-12*I
sage: b == 0
Traceback (most recent call last):
...
RuntimeError: maximum recursion depth exceeded
</pre><p>
In this ticket:
</p>
<ul><li>introduce a new (one variable) polynomial descriptor
</li><li>we make sum and product be n-ary operators instead of binary
</li><li>we remove all recursive call to become depth first search
</li></ul><p>
The current behavior prevents avoiding lazy fields (RLF and CLF) for number field embeddings (see e.g. <a class="closed ticket" href="https://trac.sagemath.org/ticket/18103" title="enhancement: cleanup number fields coerce embeddings (closed: duplicate)">#18103</a>).
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/18106
Trac 1.1.6vdelecroixThu, 02 Apr 2015 09:17:42 GMTkeywords set
https://trac.sagemath.org/ticket/18106#comment:1
https://trac.sagemath.org/ticket/18106#comment:1
<ul>
<li><strong>keywords</strong>
<em>sd66</em> added
</li>
</ul>
TicketgagernThu, 02 Apr 2015 09:39:23 GMT
https://trac.sagemath.org/ticket/18106#comment:2
https://trac.sagemath.org/ticket/18106#comment:2
<p>
In <code>exactify</code> 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 <a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=42b0fb3d75cf0967592d2ffdc731a8a610659b59"><span class="icon"></span>42b0fb3</a> to address <a class="closed ticket" href="https://trac.sagemath.org/ticket/2638" title="defect: [with patch, positive review] complex QQbar expressions exceed maximum ... (closed: fixed)">#2638</a>. I guess we could use the same for <code>_interval_fast</code> as well.
</p>
<p>
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.
</p>
<p>
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.
</p>
<p>
The way I see it, since the backtrace is about <code>_interval_fast</code> and <code>_more_precision</code>, 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.
</p>
TicketvdelecroixThu, 02 Apr 2015 10:11:50 GMT
https://trac.sagemath.org/ticket/18106#comment:3
https://trac.sagemath.org/ticket/18106#comment:3
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/18106#comment:2" title="Comment 2">gagern</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
Looks like a good idea to have a polynomial descriptor for one (or several?) algebraic numbers. It might even be used to get faster and more precise interval evaluations.
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
Looks reasonable to do it without recursion. We might obtain a good speed up.
</p>
<blockquote class="citation">
<p>
The way I see it, since the backtrace is about <code>_interval_fast</code> and <code>_more_precision</code>, all of this is happening before exact computation is triggered, right?
</p>
</blockquote>
<p>
Right!
</p>
<p>
Do you find reasonable to open two tickets:
</p>
<ul><li>one for polynomial descriptor in one variable
</li><li>one for evaluation without recursion
</li></ul><p>
Vincent
</p>
TicketgagernThu, 02 Apr 2015 11:24:58 GMT
https://trac.sagemath.org/ticket/18106#comment:4
https://trac.sagemath.org/ticket/18106#comment:4
<p>
No, I'd keep it in one ticket, although it certainly makes sense to have multiple branches. But I see these things as complementary: if either one works well, the other <em>might</em> become obsolete. And to decide that, we need to compare them, which is easier when we have a single ticket. Once one thing is ready to be merged, <em>then</em> we can move the remaining idea to a new ticket.
</p>
TicketvdelecroixSat, 16 May 2015 10:12:34 GMTdescription, summary changed
https://trac.sagemath.org/ticket/18106#comment:5
https://trac.sagemath.org/ticket/18106#comment:5
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/18106?action=diff&version=5">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Maximum depth recursion in QQbar</em> to <em>QQbar: make sum and product n-ary and remove recursive calls</em>
</li>
</ul>
TicketvdelecroixSat, 16 May 2015 10:14:58 GMTdescription changed
https://trac.sagemath.org/ticket/18106#comment:6
https://trac.sagemath.org/ticket/18106#comment:6
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/18106?action=diff&version=6">diff</a>)
</li>
</ul>
TicketchapotonFri, 22 Sep 2017 14:38:01 GMTkeywords changed
https://trac.sagemath.org/ticket/18106#comment:7
https://trac.sagemath.org/ticket/18106#comment:7
<ul>
<li><strong>keywords</strong>
<em>qqbar</em> added
</li>
</ul>
TicketjipilabFri, 07 Feb 2020 17:35:56 GMT
https://trac.sagemath.org/ticket/18106#comment:8
https://trac.sagemath.org/ticket/18106#comment:8
<p>
FWIW, in Sage9.1beta3:
</p>
<pre class="wiki">sage: a = QQbar.zeta(1009)
sage: p = cyclotomic_polynomial(1009)
sage: b = p(a)
sage: b
0
sage: b == 0
True
</pre><p>
I arrived on this ticket because of <a class="new ticket" href="https://trac.sagemath.org/ticket/28599" title="defect: RecursionError and AssertionError with regular_polygon (new)">#28599</a>.
</p>
TicketnbruinFri, 07 Feb 2020 21:56:25 GMT
https://trac.sagemath.org/ticket/18106#comment:9
https://trac.sagemath.org/ticket/18106#comment:9
<p>
Oh my, increasing the recursion limit is a *horrible* hack. There's a reason why python doesn't like to do deep recursions: stack management in C means that C generally doesn't like to do it, and CPython implements recursion by doing recursion in C. So along with the Python frame stack, the C call stack is also getting deeper.
</p>
<p>
Before you start changing the recursion limit in Python, you really want to make sure you can't accomplish the same thing in another way. In particular, you should make sure that the "recursion" really gets used: basically that stack depth will only grow logarithmically with problem size (but a little beyond the default 1000 that is normally set) The patch from <a class="closed ticket" href="https://trac.sagemath.org/ticket/2638" title="defect: [with patch, positive review] complex QQbar expressions exceed maximum ... (closed: fixed)">#2638</a> seems to be still in force. If it is at all possible to rewrite that code so that recursion limit increases are not necessary, we'd have a significant improvement in our code base.
</p>
Ticket