Power Functions

Naive recursive power: npower

The function npower raises a float x to a non-negative integer power n:

let rec npower x n =
  if n = 0 then 1.0
  else x *. npower x (n - 1)
(* val npower : float -> int -> float = <fun> *)

The type reads: “pass in a float and an integer to return a float”. The rec keyword indicates the function is recursive — it calls itself.

Mathematical justification (for x != 0):

$x^0 = 1$ $x^{n+1} = x \times x^n$

For n >= 0, the computation terminates because the exponent decreases by 1 each time. For negative n, it would run forever:

$x^{-1} = x \times x^{-2} = x \times x \times x^{-3} = \dots$

Complexity: O(n) time (n multiplications) and O(n) space (not tail-recursive).

Efficient power: binary exponentiation

For large n, repeated multiplication is too slow. The square-and-multiply algorithm uses:

$x^1 = x$ $x^{2n} = (x^2)^n$ $x^{2n+1} = x \times (x^2)^n$

In OCaml:

let rec power x n =
  if n = 1 then x
  else if even n then
    power (x *. x) (n / 2)
  else
    x *. power (x *. x) (n / 2)
(* val power : float -> int -> float = <fun> *)

Example:

$2^{12} = 4^6 = 16^3 = 16 \times 256^1 = 16 \times 256 = 4096$

Only 4 multiplications instead of 12! Integer division / truncates, so (2n+1) / 2 = n.

Complexity: O(log n) time — at most 2 lg n multiplications, where lg n is log base 2. Space is also O(log n) because nesting occurs when the exponent is odd.

Comparison

Function	Algorithm	Time	Space
npower	Repeated multiplication	O(n)	O(n)
power	Binary exponentiation	O(log n)	O(log n)

For a 32-bit integer exponent, power makes at most 30 recursive calls (for 2^31 - 1). Making power tail-recursive by adding an accumulator is possible but the gain is minute for such small recursion depths.

The even test

The helper function uses modular arithmetic:

let even n = n mod 2 = 0
(* val even : int -> bool = <fun> *)

n mod 2 returns the remainder when dividing n by 2. If the remainder is 0, n is even.

Termination and exactness

The recurrence is bound to terminate because if n > 0, then n is smaller than both 2n and 2n+1. After enough recursive calls, the exponent reaches 1. The reasoning assumes exact arithmetic — floating-point is well-behaved here, but integer overflow occurs if values exceed the finite range of hardware integers.