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)

11766-fast-callable-stack-smash-4.8nofuzz.patch (8.9 KB) - added by boothby 8 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 8 years ago by robertwb

  • Authors set to Robert Bradshaw
  • Status changed from new to needs_review

Note that fast_callable(f, CDF) will produce a much faster evaluating expression.

comment:2 Changed 8 years ago by was

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 jason

  • Cc jason added

comment:4 Changed 8 years ago by boothby

  • 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 boothby

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

comment:6 Changed 8 years ago by jdemeyer

  • Reviewers changed from boothby to Tom Boothby

comment:7 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.0.beta11
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.