Evaluating polynomials with Horner’s Method

A polynomial of the nth degree comprises n coefficients and can be evaluated at a specific value x as follows:

def poly as x =
  f64.sum (map2 (*) as (map (x **) (map f64.i64 (indices as))))

Horner’s method is a well-known technique for evaluating polynomials using fewer multiplications (in particular, avoiding the use of the power operation). While normally expressed sequentially, it can also be implemented in Futhark using an exclusive scan:

def horner as x =
  f64.sum (map2 (*) as (exscan (*) 1 (map (const x) as)))

In most cases, the additional overhead of manifesting the result of the scan exceeds the savings from not evaluating **, so poly is sometimes faster than horner.

However, Oleg Kiselyov presents in the article Parallel Fun with Monoids a monoid for computing Horner’s method, which can be implemented in Futhark as follows.

def horner_oleg as x : f64 =
  let op (p1, b1) (p2, b2) = (p1 * b2 + p2, b1 * b2)
  let (y, _) = reduce op (0, 1) (map (\a -> (a, x)) (reverse as))
  in y

The function horner_oleg can be expected to run much faster than both poly and horner.