fast_callable always segfaults when input is a polynomial of large degree

[williamstein]

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

CC: @jasongrout

Component: basic arithmetic

Author: Robert Bradshaw

Reviewer: Tom Boothby

Merged: sage-5.0.beta11

Issue created by migration from https://trac.sagemath.org/ticket/11766

[robertwb]

Author: Robert Bradshaw

[robertwb]

comment:1

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

[williamstein]

comment:2

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...)"

[boothby]

comment:4

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

[boothby]

Reviewer: boothby

[boothby]

comment:5

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

[jdemeyer]

comment:6

Attachment: 11766-fast-callable-stack-smash-4.8nofuzz.patch.gz

[jdemeyer]

Changed reviewer from boothby to Tom Boothby

[jdemeyer]

Merged: sage-5.0.beta11