The horner Reference Manual

Table of Contents

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

The horner Reference Manual

This is the horner Reference Manual, generated automatically by Declt version 2.3 "Robert April" on Tue Feb 20 08:47:08 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>

License

MIT

Description

Inline polynomial evaluation using Horner’s rule.

Dependencies
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

horner


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

horner

Source

evalpoly.lisp (file)

Macro: goertzel Z &body P
Package

horner

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

horner

Source

horner.lisp (file)

Macro: horner/even X &body COEFFS

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

Package

horner

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

horner

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

horner

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

horner

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

horner

Source

horner.lisp (file)

Macro: horner/precond X &body COEFFS
Package

horner

Source

horner.lisp (file)

Macro: horner/simple X &body COEFFS
Package

horner

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

horner

Source

horner.lisp (file)

Macro: quintic X U0 U1 U2 U3 U4 U5
Package

horner

Source

horner.lisp (file)

Macro: sextic X U0 U1 U2 U3 U4 U5 U6

Optimized sextic using Pan’s method.

Package

horner

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

horner

Source

horner.lisp (file)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   F   H   L  
Index Entry  Section

F
File, Lisp, horner.asd: The horner<dot>asd file
File, Lisp, horner/evalpoly.lisp: The horner/evalpoly<dot>lisp file
File, Lisp, horner/goertzel.lisp: The horner/goertzel<dot>lisp file
File, Lisp, horner/horner.lisp: The horner/horner<dot>lisp file
File, Lisp, horner/package.lisp: The horner/package<dot>lisp file

H
horner.asd: The horner<dot>asd file
horner/evalpoly.lisp: The horner/evalpoly<dot>lisp file
horner/goertzel.lisp: The horner/goertzel<dot>lisp file
horner/horner.lisp: The horner/horner<dot>lisp file
horner/package.lisp: The horner/package<dot>lisp file

L
Lisp File, horner.asd: The horner<dot>asd file
Lisp File, horner/evalpoly.lisp: The horner/evalpoly<dot>lisp file
Lisp File, horner/goertzel.lisp: The horner/goertzel<dot>lisp file
Lisp File, horner/horner.lisp: The horner/horner<dot>lisp file
Lisp File, horner/package.lisp: The horner/package<dot>lisp file

Jump to:   F   H   L  

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

A.2 Functions

Jump to:   E   F   G   H   M   Q   S  
Index Entry  Section

E
eval-horner: Exported functions
evalpoly: Exported macros

F
Function, eval-horner: Exported functions
Function, monic: Internal functions

G
goertzel: Exported macros

H
horner: Exported macros
horner/coeffs: Internal macros
horner/even: Exported macros
horner/monic: Internal macros
horner/odd: Exported macros
horner/precond: Internal macros
horner/simple: Internal macros

M
Macro, evalpoly: Exported macros
Macro, goertzel: Exported macros
Macro, horner: Exported macros
Macro, horner/coeffs: Internal macros
Macro, horner/even: Exported macros
Macro, horner/monic: Internal macros
Macro, horner/odd: Exported macros
Macro, horner/precond: Internal macros
Macro, horner/simple: Internal macros
Macro, quartic: Internal macros
Macro, quintic: Internal macros
Macro, sextic: Internal macros
monic: Internal functions

Q
quartic: Internal macros
quintic: Internal macros

S
sextic: Internal macros

Jump to:   E   F   G   H   M   Q   S  

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

A.3 Variables


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

A.4 Data types

Jump to:   H   P   S  
Index Entry  Section

H
horner: The horner system
horner: The horner package

P
Package, horner: The horner package

S
System, horner: The horner system

Jump to:   H   P   S