Opened 7 years ago

Last modified 3 years ago

#18106 new defect

QQbar: make sum and product n-ary and remove recursive calls — at Version 6

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.6
Component: number fields Keywords: sd66, qqbar
Cc: gagern Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by vdelecroix)

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:

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

In this ticket:

  • introduce a new (one variable) polynomial descriptor
  • we make sum and product be n-ary operators instead of binary
  • we remove all recursive call to become depth first search

The current behavior prevents avoiding lazy fields (RLF and CLF) for number field embeddings (see e.g. #18103).

Change History (6)

comment:1 Changed 7 years ago by vdelecroix

  • Keywords sd66 added

comment:2 follow-up: Changed 7 years ago 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 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.

comment:3 in reply to: ↑ 2 Changed 7 years ago by vdelecroix

Replying to gagern:

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.

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.

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.

Looks reasonable to do it without recursion. We might obtain a good speed up.

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?

Right!

Do you find reasonable to open two tickets:

  • one for polynomial descriptor in one variable
  • one for evaluation without recursion

Vincent

comment:4 Changed 7 years ago by gagern

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 might 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, then we can move the remaining idea to a new ticket.

comment:5 Changed 7 years ago by vdelecroix

  • Description modified (diff)
  • Summary changed from Maximum depth recursion in QQbar to QQbar: make sum and product n-ary and remove recursive calls

comment:6 Changed 7 years ago by vdelecroix

  • Description modified (diff)
Note: See TracTickets for help on using tickets.