The horner Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

The horner Reference Manual

This is the horner Reference Manual, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 11:56:49 2018 GMT+0.

Next: , Previous: , Up: Top   [Contents][Index]

1 Introduction

The Julia language has introduced into numerical computing the useful idea of using macros to inline the evaluation, using Horner’s rule, of polynomials with constant coefficients.

Because repeatedly evaluating a polynomial is usually at the core of any implementation of a special function, the use of macros, which facilitates type inference and unrolls the loop, potentially offers large gains over doing the same evaluation with a function.

This library provides the same affordance Julia does: a single macro, `evalpoly`, which uses Horner’s rule for a real variable, and a related rule due to Goertzel (see AOCP v2) for a complex variable.

We also go beyond what Julia offers by offering preconditioning of polynomials. While Horner’s rule is optimal in respect of the total number of operations if the coefficients are not known in advance, when coefficients are known in advance – and here “in advance” means “at compile time” – then, for polynomials of the fourth degree or greater, we can sometimes do better than Horner’s rule by pre-computing intermediate values. (Again, see Knuth AOCP v2.)

Examples

In The Art of Scientific Computing, the case for Horner’s rule is put in terms of life and death:

We assume that you know enough never to evaluate a polynomial this way:

``````p=c[0]+c[1]*x+c[2]*x*x+c[3]*x*x*x+c[4]*x*x*x*x;
``````

or (even worse!),

``````p=c[0]+c[1]*x+c[2]*pow(x,2.0)+c[3]*pow(x,3.0)+c[4]*pow(x,4.0);
``````

Come the (computer) revolution, all persons found guilty of such criminal behavior will be summarily executed, and their programs won’t be! It is a matter of taste, however, whether to write

``````p=c[0]+x*(c[1]+x*(c[2]+x*(c[3]+x*c[4])));
``````

or

``````p=(((c[4]*x+c[3])*x+c[2])*x+c[1])*x+c[0];
``````

The `evalpoly` macro automates this transformation. Instead of writing:

``````;; Bad
(+ c0
(* c1 x)
(* c2 x x)
(* c3 x x x)
(* c4 x x x x))
``````

Or manually transforming the above into

``````;; Painful
(+ (* (+ (* (+ (* (+ (* c4 x) c3) x) c2) x) c1)
x)
c0)
``````

You can use the `evalpoly` macro, which does the transformation automatically.

``````;; Good, easy, but we can do better.
(horner:evalpoly x c0 c1 c2 c3 c4)
``````

This is a big improvement, but we can do better. Most of the time the coefficients of a polynomial are constants, known at compile time. In this case, we can do better than the above by simply inlining the constants, so the whole computation can be done without any memory accesses.

Say you want to define the error function. You look into Abramowitz and Stegun and find a formula for a rational approximation which involves a polynomial with five coefficients. We can inline the computation of this polynomial using the `evalpoly` macro:

``````(horner:evalpoly x
0.254829592
-0.284496736
1.421413741
-1.453152027
1.061405429)
``````

If all this did was inline the computation, that would be a significant gain. But it does better: because the coefficients are known in advance, the macro is able to precondition the computation, thereby saving a multiplication.

Next: , Previous: , Up: Top   [Contents][Index]

2 Systems

The main system appears first, followed by any subsystem dependency.

Previous: , Up: Systems   [Contents][Index]

2.1 horner

Author

Paul M. Rodriguez <pmr@ruricolist.com>

MIT

Description

Inline polynomial evaluation using Horner’s rule.

Dependencies
• alexandria
• serapeum
• infix-math
Source

horner.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

Previous: , Up: Files   [Contents][Index]

3.1 Lisp

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.1 horner.asd

Location

horner.asd

Systems

horner (system)

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.2 horner/package.lisp

Parent

horner (system)

Location

package.lisp

Packages

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.3 horner/horner.lisp

Dependency

package.lisp (file)

Parent

horner (system)

Location

horner.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

3.1.4 horner/goertzel.lisp

Dependency

package.lisp (file)

Parent

horner (system)

Location

goertzel.lisp

Exported Definitions

goertzel (macro)

Previous: , Up: Lisp files   [Contents][Index]

3.1.5 horner/evalpoly.lisp

Dependency

package.lisp (file)

Parent

horner (system)

Location

evalpoly.lisp

Exported Definitions

evalpoly (macro)

Next: , Previous: , Up: Top   [Contents][Index]

4 Packages

Packages are listed by definition order.

Previous: , Up: Packages   [Contents][Index]

4.1 horner

Source

package.lisp (file)

Use List
• infix-math/infix-math
• serapeum
• alexandria.0.dev
• common-lisp
Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Exported definitions

Next: , Previous: , Up: Exported definitions   [Contents][Index]

5.1.1 Macros

Macro: evalpoly Z &body P
Package
Source

evalpoly.lisp (file)

Macro: goertzel Z &body P
Package
Source

goertzel.lisp (file)

Macro: horner X &body COEFFS

Compute a polynomial using Horner’s rule.
Note that the coefficients COEFFS are provided in ascending order of powers: p0 + p1*x + p2*x^2...

Package
Source

horner.lisp (file)

Macro: horner/even X &body COEFFS

Evaluate polynomial with even powers only: p0 + p1*x^2 + p2*x^4...

Package
Source

horner.lisp (file)

Macro: horner/odd X &body COEFFS

Evaluate polynomial with odd powers only: p0*x + p1*x^3 + p2*x^5...

Package
Source

horner.lisp (file)

Previous: , Up: Exported definitions   [Contents][Index]

5.1.2 Functions

Function: eval-horner X COEFFS

Eval COEFFS at run time, for testing.

Package
Source

horner.lisp (file)

Previous: , Up: Definitions   [Contents][Index]

5.2 Internal definitions

Next: , Previous: , Up: Internal definitions   [Contents][Index]

5.2.1 Macros

Macro: horner/coeffs X &body COEFFS
Package
Source

horner.lisp (file)

Macro: horner/monic X &body COEFFS

Like ‘horner’ when the last coefficient is 1 (and omitted). Cf. p1evl in Cephes.

Package
Source

horner.lisp (file)

Macro: horner/precond X &body COEFFS
Package
Source

horner.lisp (file)

Macro: horner/simple X &body COEFFS
Package
Source

horner.lisp (file)

Macro: quartic X U0 U1 U2 U3 U4

Better-than-Horner computation of the quartic. See Higham 2002, Knuth v.2.

Package
Source

horner.lisp (file)

Macro: quintic X U0 U1 U2 U3 U4 U5
Package
Source

horner.lisp (file)

Macro: sextic X U0 U1 U2 U3 U4 U5 U6

Optimized sextic using Pan’s method.

Package
Source

horner.lisp (file)

Previous: , Up: Internal definitions   [Contents][Index]

5.2.2 Functions

Function: monic &rest COEFFICIENTS

Convert coefficients u_0, u_1... u_n to monic form and return them as multiple values.

Package
Source

horner.lisp (file)

Previous: , Up: Top   [Contents][Index]

Appendix A Indexes

Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts

Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Index Entry Section `horner`: The horner system `horner`: The horner package `Package, horner`: The horner package `System, horner`: The horner system