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

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

[Tyler Eaves]

[-- Attachment #1: Type: text/plain, Size: 470 bytes --]

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!

[-- Attachment #2: primes2.ml --]
[-- Type: text/plain, Size: 622 bytes --]

(*  primes2.ml 
    Prime number generator, take 2
    Tyler Eaves <tyler@ml1.net>
    *)
   
exception Not_prime;;
exception Its_Prime;;

let rec isprime n primes = (
    try
        List.iter (fun x -> if n mod x = 0 then raise Not_prime else if sqrt
        (float_of_int n) < (float_of_int x) then raise Its_Prime else ()) primes;
        Printf.printf "%d is PRIME!\n" n; 
        isprime (n+2) (List.concat [primes; [n]])
    with 
        Not_prime -> isprime (n+2) primes
        | Its_Prime -> (Printf.printf "%d is PRIME!\n" n; 
          isprime (n+2) (List.concat [primes; [n]]))
    );;

isprime 3 [2];;
    

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

[Aleksey Nogin]

On 23.12.2003 11:00, Tyler Eaves wrote:

> (*  primes2.ml 
>     Prime number generator, take 2
>     Tyler Eaves <tyler@ml1.net>
>     *)
>    
> exception Not_prime;;
> exception Its_Prime;;
> 
> let rec isprime n primes = (
>     try
>         List.iter (fun x -> if n mod x = 0 then raise Not_prime else if sqrt
>         (float_of_int n) < (float_of_int x) then raise Its_Prime else ()) primes;
>         Printf.printf "%d is PRIME!\n" n; 
>         isprime (n+2) (List.concat [primes; [n]])
>     with 
>         Not_prime -> isprime (n+2) primes
>         | Its_Prime -> (Printf.printf "%d is PRIME!\n" n; 
>           isprime (n+2) (List.concat [primes; [n]]))
>     );;
> 
> isprime 3 [2];;

Minor thing - instead of "List.concat [primes; [n]]", you can write just 
"primes @ [n]" ("@" is an infix list append operator).

Also, List.iter is still somewhat imperative. Here is a slight modification:

let rec list_exists f n = function
    [] -> false
  | hd :: _ when hd > n -> false
  | hd :: tl -> f hd && (list_eists f n tl) ;;

let rec print_primes n primes =
    let limit = int_of_float (sqrt (float_of_int n))) in
    if list_exists (fun x -> n mod x = 0) limit primes then
       print_primes (n + 2) primes
    else begin
       Printf.printf "%d is PRIME!\n" n;
       print_primes (n+2) (primes @ [n])
    end;;

print_primes 3 [2];;

-- 
Aleksey Nogin

Home Page: http://nogin.org/
E-Mail: nogin@cs.caltech.edu (office), aleksey@nogin.org (personal)
Office: Jorgensen 70, tel: (626) 395-2907

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

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

[Nicolas Cannasse]

> 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

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

[Sven Luther]

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

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

[james woodyatt]

[-- Attachment #1: Type: text/plain, Size: 807 bytes --]

On 23 Dec 2003, at 11:00, Tyler Eaves 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.

For extra credit, have a look at the following bit of weirdness 
(though, I really think this thread belongs on the ocaml-beginners 
list).  I think you will be surprised at how fast it runs, and I 
suspect it would be a good piece of example code for figuring out how 
to use lazy evaluation in Ocaml.


[-- Attachment #2: primes.ml --]
[-- Type: application/octet-stream, Size: 1290 bytes --]

(** primes.ml -- sieve of eratosthenes *)

(* a lazy list *)
type 'a seq_cell = Z | P of 'a * 'a seq and 'a seq = 'a seq_cell Lazy.t

(* val sieve: int -> int seq -> int seq *)
let sieve n =
  let rec loop s =
    match Lazy.force s with
    | P (hd, tl) when hd mod n = 0 -> loop tl
    | P (hd, tl) -> P (hd, lazy (loop tl))
    | _ -> Z
  in
  fun s ->
    lazy (loop s)

(* val primes: int seq -> int seq *)
let primes max =
  let max = sqrt (float_of_int max) in
  let rec loop s =
    match Lazy.force s with
    | P (hd, tl) ->
      let tl = if float_of_int hd > max then tl else sieve hd tl in
      P (hd, lazy (loop tl))
    | Z ->
      Z
  in
  fun s ->
    lazy (loop s)

(* val counter: int seq *)
let counter =
  let rec loop n = P (n, lazy (loop (succ n))) in
  lazy (loop 2)

(* val limit: int -> 'a seq -> 'a seq *)
let rec limit max s =
  lazy begin
    match Lazy.force s with
    | P (hd, tl) when hd <= max -> P (hd, limit max tl)
    | _ -> Z
  end

(* val main: unit *)
let main =
  let rec loop s =
    match Lazy.force s with
    | P (hd, tl) -> Printf.printf " %d" hd; flush stdout; loop tl
    | Z -> ()
  in
  let n = int_of_string Sys.argv.(1) in
  Printf.printf "Primes to %d: 1" n;
  loop (primes n (limit n counter));
  print_newline ();
  flush stdout
;;

[-- Attachment #3: Type: text/plain, Size: 105 bytes --]




-- 
j h woodyatt <jhw@wetware.com>
that's my village calling... no doubt, they want their idiot back.

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

[Jean-Christophe Filliatre]

james woodyatt writes:
 > 
 > For extra credit, have a look at the following bit of weirdness 
 > (though, I really think this thread belongs on the ocaml-beginners 
 > list).  I think you will be surprised at how fast it runs, and I 
 > suspect it would be a good piece of example code for figuring out how 
 > to use lazy evaluation in Ocaml.

Here  is another using  streams (thus  you need  to compile  with "-pp
camlp4o"). It's  a nice example to  learn about streams,  though it is
not that efficient.
-- 
Jean-Christophe

======================================================================
let rec filter p = parser
  [< 'n; s >] -> if p n then [< 'n; filter p s >] else [< filter p s >]

let naturals = let rec gen n = [< 'n; gen (succ n) >] in gen 2

let primes =
  let rec sieve = parser
    [< 'n; s >] -> [< 'n; sieve (filter (fun m -> m mod n <> 0) s) >]
  in
  sieve naturals

let _ = 
  while true do
    Printf.printf "%d\n" (Stream.next primes); flush stdout;
  done
======================================================================

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