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 HAA16448; Wed, 24 Dec 2003 07:23:42 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id HAA16537 for ; Wed, 24 Dec 2003 07:23:41 +0100 (MET) Received: from mwinf0604.wanadoo.fr (smtp6.wanadoo.fr [193.252.22.25]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id hBO6Nev25205 for ; Wed, 24 Dec 2003 07:23:40 +0100 (MET) Received: from iliana (AStrasbourg-206-1-38-147.w81-250.abo.wanadoo.fr [81.250.184.147]) by mwinf0604.wanadoo.fr (SMTP Server) with ESMTP id 79CA8280008E; Wed, 24 Dec 2003 07:23:40 +0100 (CET) Received: from luther by iliana with local (Exim 3.36 #1 (Debian)) id 1AZ2Qm-0000ll-00; Wed, 24 Dec 2003 07:23:40 +0100 Date: Wed, 24 Dec 2003 07:23:40 +0100 To: Nicolas Cannasse Cc: Tyler Eaves , caml-list@inria.fr Subject: Re: [Caml-list] A (much less) frustrated beginner Message-ID: <20031224062340.GA2923@iliana> References: <1072206032.62516.27.camel@tylere> <005001c3c9b9$ee438140$0274a8c0@PWARP> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline In-Reply-To: <005001c3c9b9$ee438140$0274a8c0@PWARP> User-Agent: Mutt/1.5.4i From: Sven Luther X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 sven:01 luther:01 sven:01 luther:01 0900,:01 cannasse:01 950:99 primes:01 isprime:01 primes:01 printf:01 printf:01 isprime:01 low-level:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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