# 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:

1. Is this tail recursive?
2. Is there a more efficient algorithm, i.e., operating in better than linear time?
• I do not clearly understand what are you trying to achieve. If you want to implement mod function using sequence of additions your solution can be cheaper for when x div y is low and more expensive than x mod y when x div y is large because built-in mod probably can be very fast if suitabe processor instruction exists. Commented Nov 19, 2013 at 8:27

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