Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] A (much less) frustrated beginner
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Nicolas Cannasse <warplayer@f...>
Subject: Re: [Caml-list] A (much less) frustrated beginner
> 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.

Nicolas Cannasse

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