I've written remainder(x,y) in OCaml. Is there more efficient than O(n)?

Question

Here's my code:

let rem x y =
  let rec aux acc i n =
    if i=n then acc else
    if acc+1=y then aux 0 (i+1) n else
    aux (acc+1) (i+1) n in
  aux 0 0 x;;

I'm just learning OCaml and I wonder:

1. Is this tail recursive?
2. Is there a more efficient algorithm, i.e., operating in better than linear time?

Answer 1

I don't know OCaml, but I know enough similar languages that I think I can read that well enough to answer. Still, take this with a grain of salt.

That is tail recursive. You either return a value, or return the result of a recursive call that depends only on its input parameters that are known at the time of the call.

There is a more efficient algorithm. Hint: repeated subtraction. (That may not be the most efficient algorithm.)

You don't actually use the parameter n, you could just use x directly in the same way you use y directly. The name rem isn't the most descriptive; remainder would be better, but that particular function is mostly known as mod or modulus.

I would find this formatting more readable:

if i = n 
then acc 
else if acc+1 = y 
     then aux      0  (i+1) n 
     else aux (acc+1) (i+1) n