I've written remainder(x,y) in OCaml. Is there more efficient than O(n)? 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:


Is this tail recursive? 
Is there a more efficient algorithm, i.e., operating in better than linear time?
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