6
\$\begingroup\$

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?
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Kakadu
    Nov 19, 2013 at 8:27

1 Answer 1

3
\$\begingroup\$

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 
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.