Mini-project: Cracking polynomial functions

The goal of this mini-project is to compute the coefficients of a given polynomial function.

Resources

• The OCaml code for the present mini-project (latest version: 24 Feb 2021).

First degree

Given two coefficients a1 and a0, the following function returns a polynomial function of degree 1:

let make_polynomial_1 a1 a0 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 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;;

In words: to test a candidate cracking function,

• we manufacture a first-degree polynomial function using two random integers;
• we apply the candidate cracking function to this polynomial function;
• if the resulting two integers are the same as the two random integers, the candidate cracking function passes this test;
• otherwise, the candidate cracking function does not pass this test and an error message is emitted.

Solution for the first-degree task

Let p1 be the first-degree polynomial function we want to crack. By definition, p1 denotes fun x -> a1 * x + a0, for some integers a1 and a0 which we want to compute:

• Eureka #0: applying the polynomial function to 0 yields a0.
• Eureka #1: applying the polynomial function to 1 yields a1 + a0, and since we know a0 thanks to the Eureka step #0, a1 follows.

In OCaml:

let crack_1 p1 =
  let a1 = p1 1 - p1 0
  and a0 = p1 0
  in (a1, a0);;

Witness the resource file, this implementation passes the unit tests.

Second degree

Given three coefficients a2, a1 and a0, the following function returns a polynomial function of degree 2:

let make_polynomial_2 a2 a1 a0 x =
  a2 * x * x + a1 * x + a0;;

Given such a polynomial function of degree 2, we want to compute its coefficients. So your task 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,

• we manufacture a second-degree polynomial function using three random integers;
• we apply the candidate cracking function to this polynomial function;
• if the resulting three integers are the same as the three random integers, the candidate cracking function passes this test;
• otherwise, the candidate cracking function does not pass this test and an error message is emitted.

Subsidiary question: can you use crack_2 to implement crack_1?

Zeroth degree

Implement 3 distinct OCaml functions crack_0 that, given a polynomial function of degree 0, return its coefficient.

Third degree

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 x =
  a3 * x * x * x + a2 * x * x + a1 * x + a0;;

Given such a polynomial function of degree 3, we want to compute its coefficients. So your 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,

• we manufacture a third-degree polynomial function using four random integers;
• we apply the candidate cracking function to this polynomial function;
• if the resulting four integers are the same as the four random integers, the candidate cracking function passes this test;
• otherwise, the candidate cracking function does not pass this test and an error message is emitted.

Subsidiary questions:

• can you use crack_3 to implement crack_2?
• can you use crack_3 to implement crack_1?
• can you use crack_3 to implement crack_0?

I just can’t stand no more of this third degree.

—Eddie Boyd and Willie Dixon

Fourth degree

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.

Resources

• The OCaml code for the present mini-project (latest version: 24 Feb 2021).

Version

Fixed an embarrassing mispelling of “polynomial”, of all words, thanks to Rana Harris Farooq’s eagle eye [13 Mar 2021]

Fixed a typo in the narrative about testing a candidate cracking function, thanks to Rajveer Kochar’s eagle eye [28 Feb 2021]

Fixed a typo in the accompanying .ml file, thanks to Ann Chen’s eagle eye [24 Feb 2021]

Eradicated the shorthand “polynomial” and replaced it by “polynomial function”, thanks to Ann Chen’s eagle eye [21 Feb 2021]

Fixed a typo in the definition of crack_1, thanks to Marcellinus Jerricho’s eagle eye [20 Feb 2021]

Created [14 Feb 2021]