Root Finding by Binary Search¶

  • Consider the function

$$ f(x) = x^3 - x - 2. $$

  • Write a function find_root (or findRoot depending on the language's case convention) that takes:

    • 64-bit floating point numbers $a$ and $b$ with $f(a)$ and $f(b)$ having opposite signs,
    • 64-bit floating point number $\epsilon$,

    and returns an approximation of a root of $f(x)=0$ using binary search.

  • At each step:

    • compute the midpoint $m = (a+b)/2$,
    • if $f(m)$ has the same sign as $f(a)$, replace $a$ with $m$,
    • otherwise replace $b$ with $m$.

  • when it becomes $|b-a|<\epsilon$, return the midpoint.

  • Use:

    • 64-bit floating point numbers for all real values

  • Boilerplate source files {go,jl,ml,rs}/find_root.{go,jl,ml,rs} containing the test code is generated and shown below.

  • Edit the source files either by opening them in a text editor (e.g., vscode), or editing the cells below and executing them.

1. AI tutor¶

1-1. Prepare¶

  • Your personal AI tutor is provided for questions and feedback
  • Execute the following cell before you use it
In [ ]:
import heytutor

1-2. Examples¶

1-2-1. A general question¶

%%hey
How to write a function in Go?

1-2-2. A hint on this specific problem¶

%%hey
Give me a hint on this problem for Rust

1-2-3. NEW: A few builtin variables¶

  • {file:FILENAME} is the content of FILE
  • {bash[-1]} is the output of the last %%bash_ cell, {bash[-2]} that of the second last %%bash_ cell, etc.
  • {problem} is the content of the file you specified by %%hey problem_file=foo.md
  • {answer} is the content of the file you specified by %%hey answer_file=go/foo.go

1-2-4. Help when you struggle¶

%%hey answer_file=go/foo.go
I get this error when I compile it. What's wrong?"

My program:
{answer}

Error message:
{bash[-1]}

1-2-5. Ask feedback¶

  • You are encouraged to ask a feedback once you think you are done with the problem, to know if there is a better answer. You can do so by something like:
%%hey problem_file=foo.md answer_file=go/foo.md
Give me a feedback to my answer.

Problem:
{problem}

My Answer:
{answer}

2. Go¶

2-1. Baseline code¶

In [ ]:
import heytutor
In [ ]:
%%writefile_ go/find_root.go
package main
import "math"
import "fmt"

/** begin my answer */

func findRoot(a, b, eps float64) float64 {
	f := func(x float64) float64 { return x*x*x - x - 2.0 }
	l := a
	r := b
	for math.Abs(r - l) > eps {
		c := 0.5 * (l + r)
		if f(l)*f(c) < 0.0 {
			r = c
		} else {
			l = c
		}
	}
	return 0.5 * (l + r)
}
/** end my answer */

func main() {
	if !(math.Abs(findRoot(0, 2, 1.0e-20) - 1.5213797) < 1.0e-6) { panic("wrong") }
	fmt.Println("OK")
}

2-2. Compile¶

In [ ]:
%%bash_
export PATH=${PATH}:~/.local/go/bin:~/go/bin
go build -o go/find_root go/find_root.go
  • Note: when you run go or other Go commands in a terminal (SSH or Jupyter terminal), you need to execute the first line (export PATH=${PATH}:~/go/bin)
  • You may consider adding that line in your ~/.bash_profile

2-3. Run¶

In [ ]:
%%bash_
go/find_root

2-4. Ask Questions or Get Feedback¶

In [ ]:
%%hey problem_file=find_root.md answer_file=go/find_root.go

Problem:
{problem}
My Answer (between /** begin my answer */ and /** end my answer */):
{answer}

Give me a feedback to my answer.

3. Julia¶

3-1. Baseline code¶

In [ ]:
import heytutor
In [ ]:
%%writefile_ jl/find_root.jl
### begin my answer

function find_root(a, b, eps)
    f(x) = x^3 - x - 2
    l = a
    r = b
    while abs(r - l) > eps
        c = 0.5 * (l + r)
        if f(l) * f(c) < 0
            r = c
        else
            l = c
        end
    end
    0.5 * (l + r)
end
### end my answer

function main()
    @assert abs(find_root(0, 2, 1.0e-20) - 1.5213797) < 1.0e-6
    println("OK")
end

main()

3-2. Compile¶

  • Julia code is compiled "just in time" (compiled upon executed), so does not need a specific action for compilation before you run

3-3. Run¶

In [ ]:
%%bash_
export PATH=${PATH}:~/.juliaup/bin
julia jl/find_root.jl
  • Note: when you run julia or other Julia commands in a terminal (SSH or Jupyter terminal), you need to execute the first line (export PATH=${PATH}:~/.juliaup/bin)
  • You may consider adding that line in your ~/.bash_profile

3-4. Interactive execution¶

  • julia command also serves is an interactive command for Julia programs

  • You can run a source code and continue interaction

$ julia -i jl/find_root.jl
  • For trial and error, you may also consider creating a Julia notebook

3-5. Ask Questions or Get Feedback¶

In [ ]:
%%hey problem_file=find_root.md answer_file=jl/find_root.jl

Problem:
{problem}

My Answer (between ### begin my answer and ### end my answer):
{answer}

Give me a feedback to my answer.

4. OCaml¶

4-1. Baseline code¶

In [ ]:
import heytutor
In [ ]:
%%writefile_ ml/find_root.ml
(** begin my answer *)

let find_root a b eps =
  let f x = x *. x *. x -. x -. 2.0 in
  let l = ref a in
  let r = ref b in
  while abs_float (!r -. !l) > eps do
    let c = 0.5 *. (!l +. !r) in
    if f !l *. f c < 0.0 then
      r := c
    else
      l := c
  done;
  0.5 *. (!l +. !r);;
(** end my answer *)

let main () =
  assert (abs_float (find_root 0.0 2.0 1.0e-20 -. 1.5213797) < 1.0e-6);
  Printf.printf "OK\n"
;;

main()

4-2. Compile¶

In [ ]:
%%bash_
eval $(opam env)
ocamlc ml/find_root.ml -o ml/find_root
  • Note: when you run ocamlc or other OCaml commands (see below) in a terminal (SSH or Jupyter terminal), you need to execute the first line (eval $(opam env))
  • You may consider adding that line in your ~/.bash_profile

4-3. Run¶

In [ ]:
%%bash_
ml/find_root

4-4. Interactive execution¶

  • ocaml command is an interactive command for OCaml programs

  • In terminal (Jupyter or SSH), you can directly run a source code

$ eval $(opam env)   # once in your session or put it in ~/.bash_profile
$ ocaml ml/find_root.ml
  • You can run a source code and continue interaction
$ eval $(opam env)   # once in your session or put it in ~/.bash_profile
$ ocaml -init ml/find_root.ml
  • For trial and error, you may also consider creating an OCaml notebook

4-5. Ask Questions or Get Feedback¶

In [ ]:
%%hey problem_file=find_root.md answer_file=ml/find_root.ml

Problem:
{problem}

My Answer (between (** begin my answer *) and (** end my answer *)):
{answer}

Give me a feedback to my answer.

5. Rust¶

5-1. Baseline code¶

In [ ]:
import heytutor
In [ ]:
%%writefile_ rs/find_root.rs
/** begin my answer */

fn find_root(a: f64, b: f64, eps: f64) -> f64 {
    let f = |x: f64| x*x*x - x - 2.0;
    let mut l = a;
    let mut r = b;
    while (r - l).abs() > eps {
        let c = 0.5 * (l + r);
	if f(l) * f(c) < 0.0 {
            r = c;
        } else {
            l = c;
        }
    }
    0.5 * (l + r)
}
/** end my answer */

fn main() {
    assert!((find_root(0.0, 2.0, 1.0e-20) - 1.5213797).abs() < 1.0e-6);
    println!("OK");
}

5-2. Compile¶

In [ ]:
%%bash_
. ~/.cargo/env
rustc rs/find_root.rs -o rs/find_root
  • Note: when you run rustc or other Rust commands in a terminal (SSH or Jupyter terminal), you need to execute the first line (. ~/.cargo/env)
  • You may consider adding that line in your ~/.bash_profile

5-3. Run¶

In [ ]:
%%bash_
rs/find_root

5-4. Ask Questions or Get Feedback¶

In [ ]:
%%hey problem_file=find_root.md answer_file=rs/find_root.rs

Problem:
{problem}

My Answer (between /** begin my answer */ and /** end my answer */):
{answer}

Give me a feedback to my answer.