Fast Power

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

   • a 64-bit floating point number $a$
   • a non-negative integer $n$ ($n \ge 0$) and returns $a^n$ using recursion as straightforwardly as possible
   • Hint: just observe the straightforward recurrence: $a^0 = 1$, and $a^n = a \cdot a^{n-1}$ for $n > 0$
   • Note 1: do not use loops or mutable variables. A loop-based version, power_iter (or powerIter), is provided in the boilerplate code for comparison
   • Note 2: power_simple may cause a stack overflow for large $n$ due to deep recursion, but that is OK for this problem (you will fix it in a later topic, tail_recursion)

2. Write a faster version, power_fast (or powerFast, depending on the naming convention of your language), that computes $a^n$ using only $O(\log n)$ multiplications

   • Hint: observe that $a^{100} = a^{50} \times a^{50}$, or more generally, $a^{2n} = a^n \times a^n$
   • An alternative observation is $a^{100} = (a^2)^{50}$, which leads to a slightly different implementation. Try both if you can
   • power_fast is one of the simplest examples where a recursion demonstrates a clear practical advantage over a loop. The observation above is straightforward to express with recursion, but awkward with loops
   • As a bonus, power_fast will not cause a stack overflow even for very large $n$, since the recursion depth is also $O(\log n)$
   • Note 3: since $a^n$ rapidly grows to infinity when $|a| > 1$ and rapidly shrinks to zero when $|a| < 1$, computing $a^n$ for very large $n$ is rarely meaningful in practice. The purpose of this problem to illustrate the core idea with a simple example
   • Note 4: if $a$ is just a scalar, the two versions may not differ much in speed, since each multiplication is cheap
   • For these reasons, the idea behind power_fast really shines when, for example:
     • $a$ is a large matrix, where each multiplication is expensive
     • $a$ is a bignum (arbitrary-precision integer)
     • we use modular arithmetic, which avoids arithmetic overflow

• Boilerplate source files {go,jl,ml,rs}/fast_power.{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_power.go
package main
import (
	"math"
	"fmt"
)

func power_iter(a float64, n int64) float64 {
	p := 1.0
	for i := int64(0); i < n; i++ {
		p *= a
	}
	return p
}
/** begin my answer */

func power_simple(a float64, n int64) float64 {
	if n == 0 {
		return 1.0
	} else {
		return a * power_simple(a, n - 1)
	}
}

func power_fast(a float64, n int64) float64 {
	if n == 0 {
		return 1.0
	} else if n % 2 == 0 {
		return power_fast(a * a, n / 2)
	} else {
		return a * power_fast(a, n - 1)
	}
}

/** end my answer */

func main() {
	if !(math.Abs(power_simple(1.0 + 1.0/10.0,      10)        - 2.59374246) < 1.0e-7) { panic("wrong") }
	if !(math.Abs(power_fast(1.0 + 1.0/10.0,        10)        - 2.59374246) < 1.0e-7) { panic("wrong") }
	if !(math.Abs(power_simple(1.0 + 1.0/100.0,     100)       - 2.70481383) < 1.0e-7) { panic("wrong") }
	if !(math.Abs(power_fast(1.0 + 1.0/100.0,       100)       - 2.70481383) < 1.0e-7) { panic("wrong") }
	if !(math.Abs(power_fast(1.0 + 1.0/1000000.0,   1000000)   - 2.71828047) < 1.0e-7) { panic("wrong") }
	if !(math.Abs(power_iter(1.0 + 1.0/1000000.0,   1000000)   - 2.71828047) < 1.0e-7) { panic("wrong") }
	if !(math.Abs(power_fast(1.0 + 1.0/10000000.0,  10000000)  - 2.71828169) < 1.0e-7) { panic("wrong") }
	if !(math.Abs(power_iter(1.0 + 1.0/10000000.0,  10000000)  - 2.71828169) < 1.0e-7) { panic("wrong") }
	if !(math.Abs(power_fast(1.0 + 1.0/100000000.0, 100000000) - 2.71828179) < 1.0e-7) { panic("wrong") }
	if !(math.Abs(power_iter(1.0 + 1.0/100000000.0, 100000000) - 2.71828180) < 1.0e-7) { panic("wrong") }
	fmt.Println("OK")
}

2-2. Compile

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

2-4. Ask Questions or Get Feedback

%%hey problem_file=fast_power.md answer_file=go/fast_power.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_power.jl
function power_iter(a, n)
    p = 1.0
    for i in 1:n
        p *= a
    end
    p
end
### begin my answer

function power_simple(a, n)
    if n == 0
        1.0
    else
        a * power_simple(a, n - 1)
    end
end

function power_fast(a, n)
    if n == 0
        1.0
    elseif n % 2 == 0
        power_fast(a * a, div(n, 2))
    else
        a * power_fast(a, n - 1)
    end
end
### end my answer

function main()
    @assert abs(power_simple(1.0 + 1/10.0,      10)        - 2.59374246) < 1.0e-7
    @assert abs(power_fast(1.0 + 1/10.0,        10)        - 2.59374246) < 1.0e-7
    @assert abs(power_simple(1.0 + 1/100.0,     100)       - 2.70481383) < 1.0e-7
    @assert abs(power_fast(1.0 + 1/100.0,       100)       - 2.70481383) < 1.0e-7
    @assert abs(power_fast(1.0 + 1/1000000.0,   1000000)   - 2.71828047) < 1.0e-7
    @assert abs(power_iter(1.0 + 1/1000000.0,   1000000)   - 2.71828047) < 1.0e-7
    @assert abs(power_fast(1.0 + 1/10000000.0,  10000000)  - 2.71828169) < 1.0e-7
    @assert abs(power_iter(1.0 + 1/10000000.0,  10000000)  - 2.71828169) < 1.0e-7
    @assert abs(power_fast(1.0 + 1/100000000.0, 100000000) - 2.71828179) < 1.0e-7
    @assert abs(power_iter(1.0 + 1/100000000.0, 100000000) - 2.71828180) < 1.0e-7
    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_power.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_power.jl

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

3-5. Ask Questions or Get Feedback

%%hey problem_file=fast_power.md answer_file=jl/fast_power.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_power.ml
let rec power_iter a n =
  let p = ref 1.0 in
  (for i = 1 to n do
     p := !p *. a
   done;
   !p)
(** begin my answer *)

let rec power_simple a n =
  if n = 0 then
    1.0
  else
    a *. power_simple a (n - 1)

let rec power_fast a n =
  if n = 0 then
    1.0
  else if n mod 2 = 0 then
    power_fast (a *. a) (n / 2)
  else
    a *. power_fast a (n - 1);;
(** end my answer *)

let main () =
  assert (Float.abs (power_simple (1.0 +. 1.0 /. 10.0)      10        -. 2.59374246) < 1.0e-7);
  assert (Float.abs (power_fast (1.0 +. 1.0 /. 10.0)        10        -. 2.59374246) < 1.0e-7);
  assert (Float.abs (power_simple (1.0 +. 1.0 /. 100.0)     100       -. 2.70481383) < 1.0e-7);
  assert (Float.abs (power_fast (1.0 +. 1.0 /. 100.0)       100       -. 2.70481383) < 1.0e-7);
  assert (Float.abs (power_fast (1.0 +. 1.0 /. 1000000.0)   1000000   -. 2.71828047) < 1.0e-7);
  assert (Float.abs (power_iter (1.0 +. 1.0 /. 1000000.0)   1000000   -. 2.71828047) < 1.0e-7);
  assert (Float.abs (power_fast (1.0 +. 1.0 /. 10000000.0)  10000000  -. 2.71828169) < 1.0e-7);
  assert (Float.abs (power_iter (1.0 +. 1.0 /. 10000000.0)  10000000  -. 2.71828169) < 1.0e-7);
  assert (Float.abs (power_fast (1.0 +. 1.0 /. 100000000.0) 100000000 -. 2.71828179) < 1.0e-7);
  assert (Float.abs (power_iter (1.0 +. 1.0 /. 100000000.0) 100000000 -. 2.71828180) < 1.0e-7);
  Printf.printf "OK\n"
;;

main()

4-2. Compile

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

• 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_power

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_power.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_power.ml

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

4-5. Ask Questions or Get Feedback

%%hey problem_file=fast_power.md answer_file=ml/fast_power.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_power.rs
fn power_iter(a: f64, n: i64) -> f64 {
    let mut p = 1.0;
    for _i in 1..n+1 {
        p *= a
    }
    p
}
/** begin my answer */

fn power_slow(a: f64, n: i64) -> f64 {
    if n == 0 {
        1.0
    } else {
	a * power_slow(a, n - 1)
    }
}

fn power_fast(x: f64, n: i64) -> f64 {
    if n == 0 {
        1.0
    } else if n % 2 == 0 {
        power_fast(x * x, n / 2)
    } else {
        x * power_fast(x, n - 1)
    }
}
/** end my answer */

fn main() {
    assert!((power_slow(1.0 + 1.0/10.0,        10).abs()       - 2.59374246) < 1.0e-7);
    assert!((power_fast(1.0 + 1.0/10.0,        10).abs()       - 2.59374246) < 1.0e-7);
    assert!((power_slow(1.0 + 1.0/100.0,       100).abs()      - 2.70481383) < 1.0e-7);
    assert!((power_fast(1.0 + 1.0/100.0,       100).abs()      - 2.70481383) < 1.0e-7);
    assert!((power_fast(1.0 + 1.0/1000000.0,   1000000).abs()  - 2.71828047) < 1.0e-7);
    assert!((power_iter(1.0 + 1.0/1000000.0,   1000000).abs()  - 2.71828047) < 1.0e-7);
    assert!((power_fast(1.0 + 1.0/10000000.0,  10000000).abs() - 2.71828169) < 1.0e-7);
    assert!((power_iter(1.0 + 1.0/10000000.0,  10000000).abs() - 2.71828169) < 1.0e-7);
    assert!((power_fast(1.0 + 1.0/100000000.0, 100000000).abs() - 2.71828179) < 1.0e-7);
    assert!((power_iter(1.0 + 1.0/100000000.0, 100000000).abs() - 2.71828180) < 1.0e-7);
    println!("OK");
}

5-2. Compile

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

• 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_power

5-4. Ask Questions or Get Feedback

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

Problem:
{problem}

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

Give me a feedback to my answer.