CODEWITHSUNDEEP
mathf#
Olaf
Olaf

Reputation: 3986

F#: multiplication of polynomials

I found this exercise in "Functional Programming Using F#" (4.22.3):

Declare infix F# operators for addition and multiplication of polynomials in the chosen representation.

f(x) = a0 + a1 * x + a2 * x^2 + ... + an * x^n

The polynomial is reprsented as a list of integer. For example the polynomial f(x) = x^3 + 2 is represented by the list [2; 0; 0; 1]. Now I need a function that takes two lists of integers and returns a list of integers:

// polymul: int list -> int list -> int list
let polymul p q = 
    ???

The authors gave this hint along with the exercise:

The following recursion formula is useful when defining the multiplication:

0 * Q(x) = 0

(a0+a1*x+...+an*x^n) * Q(x) = a0 * Q(x) + x * [(a1+a2*x+...+an*x^(n-1)) * Q(x)]

I could not come up with a solution for this exercise. Can anyone help me?

Upvotes: 2

Views: 1123

Answers (1)

Olaf
Olaf

Reputation: 3986

I have a solution. I took the hint and converted it one-to-one into F#. And it worked magically:

// multiplicate a polynomial with a constant
// polymulconst: float -> float list -> float list
let rec polymulconst c = function
    | []      -> []
    | a::rest -> c*a::polymulconst c rest

// multiplying a polynomial by x
// polymulx: float list -> float list
let polymulx = function
    | []      -> []
    | lst     -> 0.0::lst 

// add two polynomials
// polyadd: float int -> float int -> float int
let rec polyadd ps qs =
    match (ps, qs) with
    | ([], ys)       -> ys
    | (xs, [])       -> xs
    | (x::xs, y::ys) -> (x+y)::polyadd xs ys

// polymul: float int -> float int -> float int
let rec polymul qs = function
    | []    -> []
    | p::ps -> polyadd (polymulconst p qs) 
                       (polymulx (polymul qs ps))

let ( .++. ) p q = polyadd p q
let ( .**. ) p q = polymul p q

I tested the function in the F# REPL:

> let polyA = [1.0; -2.0; 1.0];;

val polyA : float list = [1.0; -2.0; 1.0]

> let polyB = [-4.0; 3.0; 2.0];;

val polyB : float list = [-4.0; 3.0; 2.0]

> polymul polyA polyB;;

val it : float list = [-4.0; 11.0; -8.0; -1.0; 2.0]

> polyA .**. polyB;;

val it : float list = [-4.0; 11.0; -8.0; -1.0; 2.0]

>

Upvotes: 3

Related Questions