1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
-- |
-- Module : Numeric.Polynomial
-- Copyright : (c) 2012 Aleksey Khudyakov
-- License : BSD3
--
-- Maintainer : bos@serpentine.com
-- Stability : experimental
-- Portability : portable
--
-- Function for evaluating polynomials using Horher's method.
module Numeric.Polynomial (
-- * Polynomials
evaluatePolynomial
, evaluateEvenPolynomial
, evaluateOddPolynomial
-- ** Lists
-- $list
, evaluatePolynomialL
, evaluateEvenPolynomialL
, evaluateOddPolynomialL
) where
import qualified Data.Vector.Generic as G
import qualified Data.Vector as V
import Data.Vector.Generic (Vector)
-- | Evaluate polynomial using Horner's method. Coefficients starts
-- from lowest. In pseudocode:
--
-- > evaluateOddPolynomial x [1,2,3] = 1 + 2*x + 3*x^2
evaluatePolynomial :: (Vector v a, Num a)
=> a -- ^ /x/
-> v a -- ^ Coefficients
-> a
{-# INLINE evaluatePolynomial #-}
evaluatePolynomial x v
| G.null v = 0
| otherwise = G.foldr1 (\a r -> a + r*x) v
-- | Evaluate polynomial with only even powers using Horner's method.
-- Coefficients starts from lowest. In pseudocode:
--
-- > evaluateOddPolynomial x [1,2,3] = 1 + 2*x^2 + 3*x^4
evaluateEvenPolynomial :: (Vector v a, Num a)
=> a -- ^ /x/
-> v a -- ^ Coefficients
-> a
{-# INLINE evaluateEvenPolynomial #-}
evaluateEvenPolynomial x
= evaluatePolynomial (x*x)
-- | Evaluate polynomial with only odd powers using Horner's method.
-- Coefficients starts from lowest. In pseudocode:
--
-- > evaluateOddPolynomial x [1,2,3] = 1*x + 2*x^3 + 3*x^5
evaluateOddPolynomial :: (Vector v a, Num a)
=> a -- ^ /x/
-> v a -- ^ Coefficients
-> a
{-# INLINE evaluateOddPolynomial #-}
evaluateOddPolynomial x coefs
= x * evaluatePolynomial (x*x) coefs
-- $lists
--
-- When all coefficients are known statically it's more convenient to
-- pass coefficient in a list instead of vector. Functions below
-- provide just that functionality. If list is known statically it
-- will be inlined anyway.
evaluatePolynomialL :: (Num a) => a -> [a] -> a
evaluatePolynomialL x = evaluatePolynomial x . V.fromList
{-# INLINE evaluatePolynomialL #-}
evaluateEvenPolynomialL :: (Num a) => a -> [a] -> a
evaluateEvenPolynomialL x = evaluateEvenPolynomial x . V.fromList
{-# INLINE evaluateEvenPolynomialL #-}
evaluateOddPolynomialL :: (Num a) => a -> [a] -> a
evaluateOddPolynomialL x = evaluateOddPolynomial x . V.fromList
{-# INLINE evaluateOddPolynomialL #-}
|
