#19822: Fast polynomial evaluation fmpz_poly/ZZX with mpfr/mpfi input
-------------------------------------+-------------------------------------
Reporter: vdelecroix | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-7.0
Component: algebra | Resolution:
Keywords: | Merged in:
Authors: Vincent Delecroix | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/vdelecroix/19822 | 131cd594f7a5b4977040b9f681dc8b02197e4247
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Changes (by vdelecroix):
* status: needs_work => needs_review
Old description:
> We implement functions that allow fast evaluations of integer polynomials
> with real input:
> - `fmpz_poly_eval_mpfr(mpfr_t res, const fmpz_poly_t poly, const mpfr_t
> a, mpfr_rnd_t rnd)`
> - `fmpz_poly_eval_mpfi(mpfi_t res, const fmpz_poly_t poly, const mpfi_t
> a)`
> - `ZZX_eval_mpfr(mpfr_t res, ZZX_c poly, const mpfr_t a, const mpfr_rnd_t
> rnd)`
> - `ZZX_eval_mpfi(mpfi_t res, ZZX_c poly, const mpfi_t a)`
>
> These functions are integrated in the polynomial code and number field
> element comparisons (when real embedding is defined, see #17830). For the
> latter we win a great `x10` speed up. The new code is also is `x50`
> faster than comparisons in `QQbar`. For the benchmarks, we used the
> following comparison function
> {{{
> def test(a,n):
> cf = continued_fraction(a)
> cv1 = a.parent()(cf.convergent(2*n+1))
> cv2 = a.parent()(cf.convergent(2*n+2))
> for _ in range(200):
> assert cv1 > a > cv2
> }}}
> Before
> {{{
> sage: x = polygen(ZZ)
> sage: K.<a> = NumberField(x^3 - 2, embedding=1.26)
> sage: sage: %timeit test(a,10)
> 10 loops, best of 3: 51.1 ms per loop
> sage: sage: %timeit test(a,20)
> 10 loops, best of 3: 67 ms per loop
> sage: sage: %timeit test(a,100)
> 10 loops, best of 3: 108 ms per loop
> sage: sage: %timeit test(a,200)
> 1 loops, best of 3: 154 ms per loop
> }}}
> after
> {{{
> sage: x = polygen(ZZ)
> sage: K.<a> = NumberField(x^3 - 2, embedding=1.26)
> sage: sage: sage: %timeit test(a,10)
> 100 loops, best of 3: 5.84 ms per loop
> sage: sage: sage: %timeit test(a,20)
> 100 loops, best of 3: 10.2 ms per loop
> sage: sage: sage: %timeit test(a,100)
> 10 loops, best of 3: 33.5 ms per loop
> sage: sage: sage: %timeit test(a,200)
> 10 loops, best of 3: 64.8 ms per loop
> }}}
> To be compared with
> {{{
> sage: a = AA(2)**(1/3)
> sage: a.exactify()
> sage: sage: %timeit test(a,10)
> 10 loops, best of 3: 97.7 ms per loop
> sage: sage: %timeit test(a,20)
> 10 loops, best of 3: 133 ms per loop
> sage: sage: %timeit test(a,100)
> 1 loops, best of 3: 224 ms per loop
> sage: sage: %timeit test(a,200)
> 1 loops, best of 3: 305 ms per loop
> }}}
>
> See also the following discussion for upstream integrations:
>
> - [https://groups.google.com/forum/#!topic/flint-devel/WAw4jvBHPyQ thread
> on flint-devel]
New description:
We implement functions that allow fast evaluations of integer polynomials
with real input:
- `fmpz_poly_eval_mpfr(mpfr_t res, const fmpz_poly_t poly, const mpfr_t a,
mpfr_rnd_t rnd)`
- `fmpz_poly_eval_mpfi(mpfi_t res, const fmpz_poly_t poly, const mpfi_t
a)`
- `ZZX_eval_mpfr(mpfr_t res, ZZX_c poly, const mpfr_t a, const mpfr_rnd_t
rnd)`
- `ZZX_eval_mpfi(mpfi_t res, ZZX_c poly, const mpfi_t a)`
These functions are integrated in the polynomial code with method
`_eval_mpfr` and `_eval_mpfi`.
See also the following discussion for upstream integrations:
- [https://groups.google.com/forum/#!topic/flint-devel/WAw4jvBHPyQ thread
on flint-devel]
--
Comment:
For 2. I just forward the rounding mode to the mpfr functions. Having
exact rounding for polynomials might actually be tricky... and also
useful. The main reason for having this option is to handle simply
polynomial evaluations with different !RealField input.
For 3. I did not consider it on purpose. Having special case for degree
0,1 will slow down the code of higher degree cases which are indeed the
interesting ones.
--
Ticket URL: <http://trac.sagemath.org/ticket/19822#comment:6>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
