Opened 8 years ago
Closed 8 years ago
#11766 closed defect (fixed)
fast_callable always segfaults when input is a polynomial of large degree
Reported by: | was | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | critical | Milestone: | sage-5.0 |
Component: | basic arithmetic | Keywords: | |
Cc: | jason | Merged in: | sage-5.0.beta11 |
Authors: | Robert Bradshaw | Reviewers: | Tom Boothby |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
The fast_callable
function is great -- perfect for the application I had in mind, which was running Newton-Raphson on a polynomial of large degree. Unfortunately, it seems fast_callable
is implemented recursively, and maybe "blows the stack" as soon as the degree of the input gets large. Here's an example, which fails on both 64-bit Linux *and* OS X:
sage: R.<x> = CC[]; f = R.random_element(degree=30000) sage: time g = fast_callable(f, CC) /home/wstein/sage/sage-4.7.2.alpha2/local/bin/sage-sage: line 301: 15849 Segmentation fault sage-ipython "$@" -i
Attachments (1)
Change History (8)
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
From Robert Bradshaw: "Ugh. I didn't write that version of the code, but yes, it, it'll blow the stack. (Incidentally, I remember running into very similar issues to #11767 refereeing some similar code over the reals...)"
comment:3 Changed 8 years ago by
- Cc jason added
comment:4 Changed 8 years ago by
- Reviewers set to boothby
- Status changed from needs_review to positive_review
This works as advertised, but is slow on large input. I'd like to use fast_callable with / instead of polynomial_compiled, but that doesn't look promising so far since it takes so long to build the fast_callable.
sage: R.<x> = CC[]; f = R.random_element(degree=600000) sage: time f(1) 63.7162567572333 - 243.107542673361*I Time: CPU 1.62 s, Wall: 1.62 s sage: time f(1) 63.7162567572333 - 243.107542673361*I Time: CPU 1.59 s, Wall: 1.60 s sage: time g = fast_callable(f,CC) Time: CPU 32.33 s, Wall: 32.41 s sage: time g(1) 63.7162567572333 - 243.107542673361*I Time: CPU 0.74 s, Wall: 0.74 s
Here's a slightly more reasonable example.
sage: R.<x> = CC[]; f = R.random_element(degree=20000) sage: time f(1) 67.4816349551299 + 91.7847423047406*I Time: CPU 0.09 s, Wall: 0.09 s sage: time f(1) 67.4816349551299 + 91.7847423047406*I Time: CPU 0.05 s, Wall: 0.06 s sage: time g = fast_callable(f,CC) Time: CPU 0.38 s, Wall: 0.38 s sage: time g(1) 67.4816349551299 + 91.7847423047406*I Time: CPU 0.04 s, Wall: 0.04 s sage:
This is not significantly slower than the old version, so I'm accepting the patch
comment:5 Changed 8 years ago by
BTW, there's some fuzz:
~/Desktop/sage-4.8/devel/sage/sage$ hg qpush applying 11766-fast-callable-stack-smash.patch patching file sage/ext/fast_callable.pyx Hunk #2 succeeded at 1555 with fuzz 2 (offset 3 lines). now at: 11766-fast-callable-stack-smash.patch
Changed 8 years ago by
comment:6 Changed 8 years ago by
- Reviewers changed from boothby to Tom Boothby
comment:7 Changed 8 years ago by
- Merged in set to sage-5.0.beta11
- Resolution set to fixed
- Status changed from positive_review to closed
Note that fast_callable(f, CDF) will produce a much faster evaluating expression.