Re: [Caml-list] A (much less) frustrated beginner

[Sven Luther <sven.luther@wanadoo.fr>]

On Wed, Dec 24, 2003 at 10:04:49AM +0900, Nicolas Cannasse wrote:
> > I think I'm beginning to get it. Attached find my second try at a prime
> > number generator.
> >
> > This one is distinguished from my first by two important differences:
> >
> > 1: It is written (I think) in a completly functional style
> > 2: It actually *works*. It's pretty fast too. Running as an optimized
> > binary on my system (Athlon @ 950mhz under FreeBSD 5.1) it can calculate
> > the first 15104 primes (Highest is 165161) with one minute of CPU time.
> >
> > Thanks again for all your help!
> 
> Check the difference with this one , getting rid of the exceptions :
> 
> let rec isprime n primes =
>     let rec test = function
>         | [] -> true
>         | x :: l ->
>             if n mod x = 0 then
>                 false
>             else if sqrt (float_of_int n) < (float_of_int x) then
>                 true
>             else
>                 loop l
>     in
>     if test primes then begin
>         Printf.printf "%d is PRIME!\n" n;
>         isprime (n+2) (primes @ [n])
>     end else
>         isprime (n+2) primes
> 
> there is another improvement :
> @ is linear, so is not efficient here.
> we could write  ( n :: primes ) the append the element at the head of the
> list (in constant time) but then the list will be reverse constructed.
> One trick is to manually modify the list using low-level - undocumented and
> unsafe Obj operations so we can construct the list directly in the good
> order, but that require some hacks.

Don't teach Obj tricks to a beginner, that is not the way to go. Usually
you just need to reverse the list at the end of the construction, which
is enough, and since both the :: and the reversal are linear.

Friendly,

Sven Luther

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners