From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id CAA06849; Wed, 24 Dec 2003 02:05:01 +0100 (MET)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id CAA06802 for <caml-list@pauillac.inria.fr>; Wed, 24 Dec 2003 02:05:00 +0100 (MET)
Received: from smtp.siren.ocn.ne.jp (siren.ocn.ne.jp [211.129.13.170])
	by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hBO14vb04328
	for <caml-list@inria.fr>; Wed, 24 Dec 2003 02:04:58 +0100 (MET)
Received: from PWARP (p5174-ipad07kyoto.kyoto.ocn.ne.jp [221.189.196.174])
	by smtp.siren.ocn.ne.jp (Postfix) with SMTP
	id 718C8F4A; Wed, 24 Dec 2003 10:04:54 +0900 (JST)
Message-ID: <005001c3c9b9$ee438140$0274a8c0@PWARP>
From: "Nicolas Cannasse" <warplayer@free.fr>
To: "Tyler Eaves" <tyler@ml1.net>, <caml-list@inria.fr>
References: <1072206032.62516.27.camel@tylere>
Subject: Re: [Caml-list] A (much less) frustrated beginner
Date: Wed, 24 Dec 2003 10:04:49 +0900
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 6.00.2800.1158
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165
X-Loop: caml-list@inria.fr
X-Spam: no; 0.00; cannasse:01 warplayer:01 caml-list:01 950:99 primes:01 isprime:01 primes:01 printf:01 printf:01 isprime:01 low-level:01 undocumented:01 hacks:01 cannasse:01 unsafe:01 
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

> 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