"ocaml_beginners"::[] The G.C.D. program of OCaml

Hello,

On 8/17/06, LORENZO <arniwarpyahoo.com.tw> wrote:
>     Hi All,
>
>  I am new to functional programming
>        and try OCaml coding, but I don't get
>        understanding with my practice on G.C.D. as
below:
>
>  (* Determine the greatest common divisor of
>     two positive numbers a and b. No need to assume
a>b  *)
>
>  let rec gcd a b =
>  (*  let r = a mod b in   *)
>      if (a mod b) = 0 then
>         Printf.printf "The G.C.D is %d\n"
b
>      else
>         Printf.printf "processing r =
%d\n" (a mod b);
>         gcd b (a mod b);;
>
>  let a = int_of_string Sys.argv.(1) in
>  let b = int_of_string Sys.argv.(2) in
>    if !Sys.interactive then
>       ()
>    else
>       gcd a b;;
>
>  It always print "Fatal error: exception
Division_by_zero"
>       at the end of the program. Can anyone explain why
?
>

An easier way to find the problem is to rewrite it using
pattern
matching.  Here is the original algorithm, rewritten:

let rec gcd a b = match (a mod b) with
0 -> Printf.printf "The G.C.D is %d\n" b
| _ -> Printf.printf "processing r = %d\n"
(a mod b); gcd b (a mod b);;

The key parts here are the initial check 'a mod b' and the
recursive
call, which is also 'a mod b'.

So, let's go through a simple stepthrough (gcd 10 5).

Step 1: a = 10, b = 5, r = 0.  The call is 'gcd 5 0'
Step 2: ERROR

The initial check fails when attempting 5/0.

The way to fix it is to realize that recursive algorithms
must take an
extra step to terminate the algorithm.  At the end of step
1, you have
basically finished.  However, you must call the function one
more time
in order to have it execute the terminating clause.

So, here's an updated version:

let rec gcd a b = match b with
0 -> Printf.printf "The G.C.D is %d\n" a
| _ -> Printf.printf "processing r = %d\n"
(a mod b); gcd b (a mod b);;

Stepping through this time (gcd 10 5):

Step 1: a = 10, b = 5, r = 0.  Call 'gcd 5 0'
Step 2: a = 5, b = 0.  We are done.

The current 'a', ie, the previous 'b', is the answer. 
So, we output that.

Finally, the if-else version of the correct algorithm can be
written as:

let rec gcd a b =
  if (b = 0) then
    Printf.printf "The G.C.D is %d\n" a
  else
    Printf.printf "processing r = %d\n" (a mod
b); gcd b (a mod b);;

Regards,

Sachin.


Archives up to August 22, 2005 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
The archives of the very official ocaml list (the seniors'
one) can be found at http://caml.inria.fr
Attachments are banned and you're asked to be polite, avoid
flames etc. 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http:/
/groups.yahoo.com/group/ocaml_beginners/

<*> To unsubscribe from this group, send an email to:
    ocaml_beginners-unsubscribe@yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.c
om/info/terms/
 

On Fri, 18 Aug 2006 07:58:26 +0200, Sachin Shah
<zakalukagmail.com> wrote:

> An easier way to find the problem is to rewrite it
using pattern
> matching.  Here is the original algorithm, rewritten:
>
> let rec gcd a b = match (a mod b) with
> 0 -> Printf.printf "The G.C.D is %d\n"
b
> | _ -> Printf.printf "processing r =
%d\n" (a mod b); gcd b (a mod b);;

Please check your Ideas before posting them and confusing
people. This  
version is far from equivalent to the Original version.
Using it gives:

# let rec gcd a b = match (a mod b) with
    0 -> Printf.printf "The G.C.D is %d\n" b
    | _ -> Printf.printf "processing r =
%d\n" (a mod b); gcd b (a mod b);;
val gcd : int -> int -> unit = <fun>
# gcd 10 5;;
The G.C.D is 5
- : unit = ()

So just by rewriting you have already fixed the Problem.

> So, let's go through a simple stepthrough (gcd 10 5).
>
> Step 1: a = 10, b = 5, r = 0.  The call is 'gcd 5 0'
> Step 2: ERROR
>
> The initial check fails when attempting 5/0.

Actually it doesn't as you can see when you just try to use
it.

> The way to fix it is to realize that recursive
algorithms must take an
> extra step to terminate the algorithm.  At the end of
step 1, you have
> basically finished.  However, you must call the
function one more time
> in order to have it execute the terminating clause.

Where did you get this idea from?

> Finally, the if-else version of the correct algorithm
can be written as:
>
> let rec gcd a b =
>   if (b = 0) then
>     Printf.printf "The G.C.D is %d\n" a
>   else
>     Printf.printf "processing r = %d\n" (a
mod b); gcd b (a mod b);;

This gives:

# let rec gcd a b =
   if (b = 0) then
     Printf.printf "The G.C.D is %d\n" a
   else
     Printf.printf "processing r = %d\n" (a mod
b); gcd b (a mod b);;
val gcd : int -> int -> 'a = <fun>
# gcd 10 5;;
processing r = 0
The G.C.D is 5
Exception: Division_by_zero.

So you have the same Problem again. The Problem is not with
the condition,  
but rather that the recursive call is not part of the
conditional.


Greetings,
    Till


-- 
It can't rain all the time.
   --The Crow


Archives up to August 22, 2005 are also downloadable at http://www.connettivo.net/cntprojects/ocaml_beginners/
The archives of the very official ocaml list (the seniors'
one) can be found at http://caml.inria.fr
Attachments are banned and you're asked to be polite, avoid
flames etc. 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http:/
/groups.yahoo.com/group/ocaml_beginners/

<*> To unsubscribe from this group, send an email to:
    ocaml_beginners-unsubscribe@yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.c
om/info/terms/