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: 04 Mar 2022).

First degree

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

let make_polynomial_1 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 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 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

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.

• 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 p =
  let a0 = p 0
  and a1 = p 1 - p 0
  in (a1, a0);;

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

Interlude

Alfrothul: Hmm.

Harald: Hmm?

Alfrothul: Right. There is no need to compute p 0 twice in the definition of crack_1.

Harald: 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);;

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 =
  fun 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 crack_2 be used 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 =
  fun 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 crack_3 be used to implement crack_2?
• can crack_3 be used to implement crack_1?
• can crack_3 be used 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.

A generalization

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 -> (x + 1) * (x + 1)
  
  fun x -> (x + 1) * (x + 1) * (x + 1)
  

Can such a polynomial function be cracked, and if so, how?

Resources

• The OCaml code for the present mini-project (latest version: 04 Mar 2022).

Version

Added entries in the general index [11 Mar 2022]

Added the precision about the as keyword to describe test_crack_1 [05 Mar 2022]

Added the interlude, streamlined the name of the formal parameter in the definition of crack_1, and polished the narrative as well as the .ml file [04 Mar 2022]

Created [27 Feb 2022]