The goal of this mini-project is to compute the coefficients of a given polynomial function.
Assuming a power function named power that exponentiates its first argument with its second, the following function maps two integer coefficients a1 and a0 to a polynomial function of degree 1:
let make_polynomial_1 a1 a0 =
fun x -> a1 * power x 1 + a0 * power x 0;;
Inlining power in this definition yields the following simplified version. Given two integer coefficients a1 and a0, this function returns a polynomial function of degree 1:
let make_polynomial_1_simplified a1 a0 =
fun x -> a1 * x + a0;;
Given such a polynomial function of degree 1, we want to compute its coefficients. So your task, should you choose to accept it – but hey, it’s not like this mission is impossible, witness the solution just below, so there really is no reason to digress here – is to implement a function named crack_1 of type:
(int -> int) -> int * int
that passes the following unit test:
let test_crack_1_once candidate =
let a1 = random_int ()
and a0 = random_int ()
in let p1 = make_polynomial_1 a1 a0
in let expected_result = (a1, a0)
and ((a1', a0') as actual_result) = candidate p1
in if actual_result = expected_result
then true
else let () = Printf.printf
"test_crack_1_once failed for %i * x^1 + %i with (%i, %i)\n"
a1 a0 a1' a0'
in false;;
where the keyword as is used to alias formal parameters.
In words: to test a candidate cracking function,
We want to crack a first-degree polynomial function. Since its degree is 1, this polynomial function can be stated as fun x -> a1 * x + a0, for some integer coefficients a1 and a0. We want to compute these coefficients, and the only thing we can do is to is to apply the polynomial function.
In OCaml:
let crack_1 p =
let a0 = p 0
and a1 = p 1 - p 0
in (a1, a0);;
Witness the resource file, this implementation passes the unit tests.
Alfrothul: Hmm.
Anton: Hmm?
Alfrothul: Right. There is no need to compute p 0 twice in the definition of crack_1.
Anton: Indeed. We only need to compute it once, at the outset.
Alfrothul: In fact, for the principle of it, we should name the result of all the applications of p at the outset, and then proceed:
let crack_1 p =
let p_0 = p 0
and p_1 = p 1
in let a0 = p_0
and a1 = p_1 - p_0
in (a1, a0);;
Given three coefficients a2, a1 and a0, the following function returns a polynomial function of degree 2:
let make_polynomial_2 a2 a1 a0 =
fun x -> a2 * power x 2 + a1 * power x 1 + a0 * power x 0;;
Given such a polynomial function of degree 2, we want to compute its coefficients. So your task – you might as well accept it – is to implement a function crack_2 of type:
(int -> int) -> int * int * int
that passes the following unit test:
let test_crack_2_once candidate =
let a2 = random_int ()
and a1 = random_int ()
and a0 = random_int ()
in let p2 = make_polynomial_2 a2 a1 a0
in let expected_result = (a2, a1, a0)
and ((a2', a1', a0') as actual_result) = candidate p2
in if actual_result = expected_result
then true
else let () = Printf.printf
"test_crack_2_once failed for %i * x^2 + %i * x^1 + %i with (%i, %i, %i)\n"
a2 a1 a0 a2' a1' a0'
in false;;
In words: to test a candidate cracking function,
Subsidiary question: can crack_2 be used to implement crack_1?
Implement 3 distinct OCaml functions crack_0 that, given a polynomial function of degree 0, return its coefficient.
Given four coefficients a3, a2, a1 and a0, the following function returns a polynomial function of degree 3:
let make_polynomial_3 a3 a2 a1 a0 =
fun x -> a3 * power x 3 + a2 * power x 2 + a1 * power x 1 + a0 * power x 0;;
Given such a polynomial function of degree 3, we want to compute its coefficients. So your accepted task is to implement a function crack_3 of type:
(int -> int) -> int * int * int * int
that passes the following unit test:
let test_crack_3_once candidate =
let a3 = random_int ()
and a2 = random_int ()
and a1 = random_int ()
and a0 = random_int ()
in let p3 = make_polynomial_3 a3 a2 a1 a0
in let expected_result = (a3, a2, a1, a0)
and ((a3', a2', a1', a0') as actual_result) = candidate p3
in if actual_result = expected_result
then true
else let () = Printf.printf
"test_crack_3_once failed for %i * x^3 + %i * x^2 + %i * x^1 + %i with (%i, %i, %i, %i)\n"
a3 a2 a1 a0 a3' a2' a1' a0'
in false;;
In words: to test a candidate cracking function,
Subsidiary questions:
Implement an OCaml function crack_4 of type:
(int -> int) -> int * int * int * int * int
that, given a polynomial function of degree 4, returns its 5 coefficients.
Suppose that the given polynomial function to crack was not defined in the standard way but is
in Horner form:
fun x -> ((2 * x) + 3) * x + 4
in any other form:
fun x -> power (x + 1) 2
fun x -> power (x + 1) 3
Can such a polynomial function be cracked, and if so, how?
Used the power function in the definitions of the polynomial makers [04 Mar 2023]
Created [10 Jan 2023]