login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit

Computing value of following polynomial was proposed as a benchmark:

fricas
p := x^24+32*x^21+9*x^18+34*x^12+34*x^10+45*x^3

\label{eq1}{{x}^{24}}+{{32}\ {{x}^{21}}}+{9 \ {{x}^{18}}}+{{34}\ {{x}^{1
2}}}+{{34}\ {{x}^{10}}}+{{45}\ {{x}^{3}}}(1)
Type: Polynomial(Integer)

Naive solution have unimpressive speed:

fricas
)set messages time on
[eval(p, x, 0.5) for i in 1..1000];
Type: List(Polynomial(Float))
fricas
Time: 0.05 (IN) + 0.12 (EV) + 0.01 (OT) = 0.18 sec

Simple reformulations do not give better results. However, assuming that we need double precision floating point results we can turn p into a compiled function. First we convert polynomial to use doubles as coefficients:

fricas
pf := p::POLY(DoubleFloat)

\label{eq2}{{x}^{24}}+{{32.0}\ {{x}^{21}}}+{{9.0}\ {{x}^{18}}}+{{34.0}\ {{x}^{12}}}+{{34.0}\ {{x}^{10}}}+{{45.0}\ {{x}^{3}}}(2)
Type: Polynomial(DoubleFloat?)
fricas
Time: 0 sec

Then we define corresponding function:

fricas
function(pf, 'dff, 'x)

\label{eq3}dff(3)
Type: Symbol
fricas
Time: 0.01 (OT) = 0.01 sec

Now try it:

fricas
v := 0.5::SF

\label{eq4}0.5(4)
Type: DoubleFloat?
fricas
Time: 0 sec
[dff(v) for i in 1..10000];
fricas
Compiling function dff with type DoubleFloat -> DoubleFloat
Type: List(DoubleFloat?)
fricas
Time: 0.13 (EV) + 0.01 (OT) = 0.14 sec

Now it is much better, but still slow. Main cost is interpreter loop. Try driver function:

fricas
do_it(v, n) == (res : SF := 0; for i in 1..n repeat res := res + dff(v); res)
Type: Void
fricas
Time: 0 sec
do_it(v, 1000000)
fricas
Compiling function do_it with type (DoubleFloat, PositiveInteger)
       -> DoubleFloat

\label{eq5}5666553.556919098(5)
Type: DoubleFloat?
fricas
Time: 0.54 (EV) = 0.54 sec

This is much better, around half microsecond per evaluation, but still slower than machine arithmetic. Profiling (not shown here) indicated that 99% of time is spent in exponentiation routine. So we would need better formula like Horner rule.




  Subject:   Be Bold !!
  ( 15 subscribers )  
Please rate this page: