Mailing list for all users of the OCaml language and system.
 help / color / mirror / Atom feed
* help an o'caml beginner
@ 2000-07-26 17:51 John BEPPU
  2000-07-27 18:47 ` Alain Frisch
                   ` (5 more replies)
  0 siblings, 6 replies; 12+ messages in thread
From: John BEPPU @ 2000-07-26 17:51 UTC (permalink / raw)
  To: caml-list

Hi.

Recently, there have been discussions about functional programming
on sites like slashdot, kuro5hin, and advogato.  This made me want
to investigate functional languages further.  I decided on O'Caml,
because there was a guy on slashdot who was very enthusiastic about
Standard ML.  There was also mention of O'Caml which was said to be 
a free dialect of ML and people generally had good things to say,
so I checked out the home page.  I happen to be a fan of the other
camel (Perl), but I hope you don't hold that against me.  ;-)

I've been trying to practice funcional techniques in Perl (mostly
by using recursion more often than I normally would and using
closures to make iterators).  However, I felt that I would not ever 
get a good understanding of the functional way if I didn't program 
in a (more) pure language.  That's another reason why I'm here.

Anyway, I hope you guys can help me.  

I tried out the recursive fibonacci number program that's in the
manual. 

    let rec fib n =
        if n < 2 then 1 else fib(n-1) + fib(n-2);;
    let main () =
        let arg = int_of_string Sys.argv.(1) in
        print_int(fib arg);
        print_newline();
        exit 0;;
    main ();;

I wrote a C implementation of the same recursive algorithm. 

    #include <stdio.h>

    int fib(int n)
    {
        if (n < 2) {
            return 1;
        } else {
            return fib(n - 1) + fib(n - 2);
        }
    }

    int main(char *argc, char **argv)
    {
        printf("%d\n", fib(atoi(argv[1])));
        return 0;
    }

What surprised the fsck out of me was how fast the O'Caml version
was compared to the C version.  I checked the asm output of ocamlopt,
and that was some lean code.  I was not expecting results like this,
so I was quite pleasantly surprised.  The performance of ocamlopt is
yet another reason I'm here.

Next, I wrote an iterative C version.

    #include <stdio.h>

    int fib(int n)
    {
        int val = 2;
        int n1 = 2;
        int n2 = 1;
        int i;
        if (n < 2)
            return n;

        for (i = 2; i < n; i++) {
            val = n2 + n1;
            n2 = n1;
            n1 = val;
        }
        return val;
    }

    int main(char *argc, char **argv)
    {
        printf("%d\n", fib(atoi(argv[1])));
        return 0;
    }

This was much faster than any of the recursive versions, because it 
doesn't have to recompute the same values over and over again.  

Next, I tried to fumble my way through making an O'Caml version of
this iterative algorithm, but I failed due to my lack of knowledge
about this language.  (I hesitate to print the tutorial, because
that's a lot of paper -- I wish the tutorial were available in HTML.
I just may have to print it, though.)


>>>
If anyone out there could implement an O'Caml fibonacci number
generator that doesn't make redundant calculations, I would really
appreciate it.  I just need something to study.
>>>


I wrote a recursive Perl version that doesn't make redundant
calculations, and I'd be interested to see how different in
structure an O'Caml version would be.

    #!/usr/bin/perl -w

    use strict;

    sub fib_pair {
        my $n = shift;
        my @seq;
        if ($n < 2) {
            @seq = (1, 1);
        } else {
            @seq = fib_pair($n - 1);
            @seq = ($seq[1], $seq[0] + $seq[1]);
        }
        return @seq;
    }

    sub fib {
        my $n = shift;
        return (fib_pair($n))[1];
    }

    print fib($ARGV[0]), "\n";


Thanks for reading this far.  I understand that English is a foreign
language to many of you, and I'm terribly sorry I had to write so
much.



^ permalink raw reply	[flat|nested] 12+ messages in thread
end of thread, other threads:[~2000-08-03 13:13 UTC | newest]

Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2000-07-26 17:51 help an o'caml beginner John BEPPU
2000-07-27 18:47 ` Alain Frisch
2000-07-27 18:56 ` Markus Mottl
2000-07-29 17:03   ` John BEPPU
2000-07-29 17:23     ` Markus Mottl
2000-07-31  7:11   ` Vitaly Lugovsky
2000-07-31  8:43     ` Markus Mottl
2000-08-02 16:58     ` Printable Caml manual Walid Taha
2000-07-27 18:57 ` help an o'caml beginner Remi VANICAT
2000-07-27 19:08 ` Jean-Christophe Filliatre
2000-07-27 21:31 ` Laurent Chéno
2000-07-27 23:47 ` Michel Quercia

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox