Fast Affine Recurrence

• Consider the sequence defined by: $$ x_0 = c, \qquad x_n = a x_{n-1} + b $$

1. Write a function affine_recurrence_simple (or affineRecurrenceSimple, depending on the naming convention of your language) that takes:

   • 64-bit floating point numbers $a$, $b$, and $c$,
   • a non-negative integer $n$ ($n \ge 0$),
   • and returns $x_n$
   • Note 1: do not use loops or mutable variables. A loop-based version, affine_recurrence_iter (or affineRecurrenceIter), is provided in the boilerplate code for comparison
   • Note 2: affine_recurrence_simple may cause a stack overflow for large $n$ due to deep recursion, but that is acceptable for this problem (you will fix it in a later topic, tail_recursion)

2. Write a faster version, affine_recurrence_fast (or affineRecurrenceFast, depending on the naming convention of your language), that computes $x_n$ in only $O(\log n)$ time

   • Hint: this is a generalization of the previous fast power problem
   • Observe: $$x_n = a x_{n-1} + b = a(a x_{n-2} + b) + b = a^2 x_{n-2} + ab + b$$
   • Therefore, if we define $y_n$ as: $$ y_0 = c, \qquad y_n = a^2 y_{n-1} + ab + b $$ then $x_{100} = y_{50}$, or more generally, $x_{2n} = y_n$
   • Apply this idea recursively

• Boilerplate source files {go,jl,ml,rs}/fast_recurrence.{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

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

import heytutor

%%writefile_ go/fast_recurrence.go
package main
import "math"
import "fmt"

func affineRecurrenceIter(a, b, c float64, n int64) float64 {
	x := c
	for i := int64(0); i < n; i++ {
		x = a * x + b
	}
	return x
}
/** begin my answer */

func affineRecurrenceSimple(a, b, c float64, n int64) float64 {
	if n == 0 {
		return c
	} else {
		x := affineRecurrenceSimple(a, b, c, n - 1)
		return a * x + b
	}
}

func affineRecurrenceFast(a, b, c float64, n int64) float64 {
	if n == 0 {
		return c
	} else if n % 2 == 0 {
		return affineRecurrenceFast(a * a, a * b + b, c, n / 2)
	} else {
		x := affineRecurrenceFast(a, b, c, n - 1)
		return a * x + b
	}
}
/** end my answer */

func main() {
	if !(math.Abs(affineRecurrenceSimple(0.9,  1.0, 2.0, 100)     - 9.9997875) < 1.0e-6) { panic("wrong") }
	if !(math.Abs(affineRecurrenceSimple(0.99, 1.0, 2.0, 1000)    - 99.9957692) < 1.0e-6) { panic("wrong") }
	if !(math.Abs(affineRecurrenceFast(0.99,   1.0, 2.0, 1000)    - 99.9957692) < 1.0e-6) { panic("wrong") }
	if !(math.Abs(affineRecurrenceFast(0.99,   1.0, 2.0, 10000)   - 100.0) < 1.0e-6) { panic("wrong") }
	if !(math.Abs(affineRecurrenceFast(0.999,  1.0, 2.0, 10000)   - 999.9549170) < 1.0e-6) { panic("wrong") }
	if !(math.Abs(affineRecurrenceFast(0.999,  1.0, 2.0, 100000)  - 1000.0) < 1.0e-6) { panic("wrong") }
	if !(math.Abs(affineRecurrenceFast(0.9999, 1.0, 2.0, 100000)  - 9999.5463184) < 1.0e-6) { panic("wrong") }
	if !(math.Abs(affineRecurrenceIter(0.9999, 1.0, 2.0, 100000)  - 9999.5463184) < 1.0e-6) { panic("wrong") }
	if !(math.Abs(affineRecurrenceFast(0.9999, 1.0, 2.0, 1000000) - 10000.0) < 1.0e-6) { panic("wrong") }
	if !(math.Abs(affineRecurrenceIter(0.9999, 1.0, 2.0, 1000000) - 10000.0) < 1.0e-6) { panic("wrong") }
	fmt.Println("OK")
}

2-2. Compile

%%bash_
export PATH=${PATH}:~/.local/go/bin:~/go/bin
go build -o go/fast_recurrence go/fast_recurrence.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

%%bash_
go/fast_recurrence

2-4. Ask Questions or Get Feedback

%%hey problem_file=fast_recurrence.md answer_file=go/fast_recurrence.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

import heytutor

%%writefile_ jl/fast_recurrence.jl
function affine_recurrence_iter(a, b, c, n)
    x = c
    for i in 1:n
        x = a * x + b
    end
    x
end
### begin my answer

function affine_recurrence_simple(a, b, c, n)
    if n == 0
        c
    else
        x = affine_recurrence_simple(a, b, c, n - 1)
        a * x + b
    end
end

function affine_recurrence_fast(a, b, c, n)
    if n == 0
        c
    elseif n % 2 == 0
        affine_recurrence_fast(a * a, a * b + b, c, n ÷ 2)
    else
        x = affine_recurrence_fast(a, b, c, n - 1)
        a * x + b
    end
end
### end my answer

function main()
    @assert abs(affine_recurrence_simple(0.9,  1.0, 2.0, 100)     - 9.9997875) < 1.0e-6
    @assert abs(affine_recurrence_simple(0.99, 1.0, 2.0, 1000)    - 99.9957692) < 1.0e-6
    @assert abs(affine_recurrence_fast(0.99,   1.0, 2.0, 1000)    - 99.9957692) < 1.0e-6
    @assert abs(affine_recurrence_fast(0.99,   1.0, 2.0, 10000)   - 100.0) < 1.0e-6
    @assert abs(affine_recurrence_fast(0.999,  1.0, 2.0, 10000)   - 999.9549170) < 1.0e-6
    @assert abs(affine_recurrence_fast(0.999,  1.0, 2.0, 100000)  - 1000.0) < 1.0e-6
    @assert abs(affine_recurrence_fast(0.9999, 1.0, 2.0, 100000)  - 9999.5463184) < 1.0e-6
    @assert abs(affine_recurrence_iter(0.9999, 1.0, 2.0, 100000)  - 9999.5463184) < 1.0e-6
    @assert abs(affine_recurrence_fast(0.9999, 1.0, 2.0, 1000000) - 10000.0) < 1.0e-6
    @assert abs(affine_recurrence_iter(0.9999, 1.0, 2.0, 1000000) - 10000.0) < 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

%%bash_
export PATH=${PATH}:~/.juliaup/bin
julia jl/fast_recurrence.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/fast_recurrence.jl

• For trial and error, you may also consider creating a Julia notebook

3-5. Ask Questions or Get Feedback

%%hey problem_file=fast_recurrence.md answer_file=jl/fast_recurrence.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

import heytutor

%%writefile_ ml/fast_recurrence.ml
let rec affine_recurrence_iter a b c n =
  let x = ref c in
  for i = 1 to n do
    x := a *. !x +. b
  done;
  !x
;;
(** begin my answer *)

let rec affine_recurrence_simple a b c n =
  if n = 0 then
    c
  else
    let x = affine_recurrence_simple a b c (n - 1) in
    a *. x +. b
;;

let rec affine_recurrence_fast a b c n =
  if n = 0 then
    c
  else if n mod 2 = 0 then
    affine_recurrence_fast (a *. a) (a *. b +. b) c (n / 2)
  else
    let x = affine_recurrence_fast a b c (n - 1) in
    a *. x +. b
(** end my answer *)

let main () =
  assert (Float.abs (affine_recurrence_simple 0.9    1.0 2.0 100     -. 9.9997875) < 1.0e-6);
  assert (Float.abs (affine_recurrence_simple 0.99   1.0 2.0 1000    -. 99.9957692) < 1.0e-6);
  assert (Float.abs (affine_recurrence_fast   0.99   1.0 2.0 1000    -. 99.9957692) < 1.0e-6);
  assert (Float.abs (affine_recurrence_fast   0.99   1.0 2.0 10000   -. 100.0) < 1.0e-6);
  assert (Float.abs (affine_recurrence_fast   0.999  1.0 2.0 10000   -. 999.9549170) < 1.0e-6);
  assert (Float.abs (affine_recurrence_fast   0.999  1.0 2.0 100000  -. 1000.0) < 1.0e-6);
  assert (Float.abs (affine_recurrence_fast   0.9999 1.0 2.0 100000  -. 9999.5463184) < 1.0e-6);
  assert (Float.abs (affine_recurrence_iter   0.9999 1.0 2.0 100000  -. 9999.5463184) < 1.0e-6);
  assert (Float.abs (affine_recurrence_fast   0.9999 1.0 2.0 1000000 -. 10000.0) < 1.0e-6);
  assert (Float.abs (affine_recurrence_iter   0.9999 1.0 2.0 1000000 -. 10000.0) < 1.0e-6);
  Printf.printf "OK\n"
;;

main()

4-2. Compile

%%bash_
eval $(opam env)
ocamlc ml/fast_recurrence.ml -o ml/fast_recurrence

• 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

%%bash_
ml/fast_recurrence

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/fast_recurrence.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/fast_recurrence.ml

• For trial and error, you may also consider creating an OCaml notebook

4-5. Ask Questions or Get Feedback

%%hey problem_file=fast_recurrence.md answer_file=ml/fast_recurrence.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

import heytutor

%%writefile_ rs/fast_recurrence.rs
fn affine_recurrence_iter(a: f64, b: f64, c: f64, n: i64) -> f64 {
    let mut x = c;
    for _i in 0..n {
	x = a * x + b
    }
    x
}
/** begin my answer */

fn affine_recurrence_simple(a: f64, b: f64, c: f64, n: i64) -> f64 {
    if n == 0 {
        c
    } else {
	let x = affine_recurrence_simple(a, b, c, n - 1);
	a * x + b
    }
}

fn affine_recurrence_fast(a: f64, b: f64, c: f64, n: i64) -> f64 {
    if n == 0 {
        c
    } else if n % 2 == 0 {
        affine_recurrence_fast(a * a, a * b + b, c, n / 2)
    } else {
	let x = affine_recurrence_fast(a, b, c, n - 1);
	a * x + b
    }
}
/** end my answer */

fn main() {
    assert!((affine_recurrence_simple(0.9,  1.0, 2.0, 100)     - 9.9997875).abs() < 1.0e-6);
    assert!((affine_recurrence_simple(0.99, 1.0, 2.0, 1000)    - 99.9957692).abs() < 1.0e-6);
    assert!((affine_recurrence_fast(0.99,   1.0, 2.0, 1000)    - 99.9957692).abs() < 1.0e-6);
    assert!((affine_recurrence_fast(0.99,   1.0, 2.0, 10000)   - 100.0).abs() < 1.0e-6);
    assert!((affine_recurrence_fast(0.999,  1.0, 2.0, 10000)   - 999.9549170).abs() < 1.0e-6);
    assert!((affine_recurrence_fast(0.999,  1.0, 2.0, 100000)  - 1000.0).abs() < 1.0e-6);
    assert!((affine_recurrence_fast(0.9999, 1.0, 2.0, 100000)  - 9999.5463184).abs() < 1.0e-6);
    assert!((affine_recurrence_iter(0.9999, 1.0, 2.0, 100000)  - 9999.5463184).abs() < 1.0e-6);
    assert!((affine_recurrence_fast(0.9999, 1.0, 2.0, 1000000) - 10000.0).abs() < 1.0e-6);
    assert!((affine_recurrence_iter(0.9999, 1.0, 2.0, 1000000) - 10000.0).abs() < 1.0e-6);
    println!("OK");
}

5-2. Compile

%%bash_
. ~/.cargo/env
rustc rs/fast_recurrence.rs -o rs/fast_recurrence

• 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

%%bash_
rs/fast_recurrence

5-4. Ask Questions or Get Feedback

%%hey problem_file=fast_recurrence.md answer_file=rs/fast_recurrence.rs

Problem:
{problem}

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

Give me a feedback to my answer.