[Camllist] A (much less) frustrated beginner
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Sven Luther <sven.luther@w...> 
Subject:  Re: [Camllist] A (much less) frustrated beginner 
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 lowlevel  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 camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners