fsharp


This blog has moved on http://blog.khigia.net/blog.html and this post is at http://blog.khigia.net/wp-import/fsharp/2008/03/30/ocaml-vs-f-for-big-integer-surprising-performance-test.html

Was inspired by Rober Pickering post about a post about Euler problem 14 …

Without changing the algorithm, I ran a simple test to compare F#, ocaml byte code and ocaml native code … and the result is quite surprising, for me at least!

The program do a lot of computation on integer (even 64 bits); I remember (no ref) that ocaml is more efficient for floating point operation that for integer. But anyway, just wanted an idea of how to port this code to Ocaml.

Following is the code in F# as seen on cited post:

#light
let rec seq_length x n =
match x with
| x when x = 0L -> (n + 1)
| x when x = 1L -> seq_length 0L (n + 1)
| x when x%2L=0L ->seq_length (x/2L) (n + 1)
| _ -> seq_length (3L*x + 1L) (n + 1)

let rec loop i imax n =
let n’ = seq_length i 0
let imax, n = if n’ > n then i, n’ else imax, n
if i < 1000000L then loop (i + 1L) imax n else imax print_any (loop 1L 0L 0)[/sourcecode] And here is an Ocaml version: [sourcecode language="csharp"] let ( ** ) = Int64.mul let ( // ) = Int64.div let ( %% ) = Int64.rem let rec seq_length x n = match x with | 0L -> (n + 1)
| 1L -> seq_length 0L (n + 1)
| x when x %% 2L = 0L -> seq_length (x // 2L) (n + 1)
| _ -> seq_length (Int64.succ (3L ** x)) (n + 1)

let rec loop i imax n =
let n’ = seq_length i 0 in
let imax, n = if n’ > n then (i, n’) else (imax, n) in
if i < 1000000L then loop (Int64.succ i) imax n else imax let _ = print_string (Int64.to_string (loop 1L 0L 0))[/sourcecode] Surprisingly (for me!), the compiled F# code is much faster:

  • time mono eul14.exe: 12.979s
  • time ./eul14.byte: 58.145s
  • time ./eul14.native: 30.234s

I’m not sure why Ocaml seems to be slower for this test. Can it be a GC issue?

Advertisements

This blogpost present a good F# solution to Euler problem 2. The code make use of infinite sequence. I’ve written other solutions to this same problem. The first one is a code specialized to solve this problem: it computes the fibonacci sequence while checking the problem conditions and computing the problem answer.

#light

let rec fib_filter_fold (n0,n1) filter folder acc m =
    if n0 <= m
    then fib_filter_fold (n1, n0 + n1) filter folder (if filter n0 then (folder acc n0) else acc) m
    else acc

let pb2 m = fib_filter_fold (1,1) (fun x -> x % 2 = 0) (fun acc x -> acc + x) 0 m

printf "euler problem 2 (1000000): %a\n" output_any (pb2 1000000)

I then wrote a second version, trying to make use of Seq functions. Idea is to start with the fibonacci sequence and apply some modification on it to solve the problem. I’m not so happy with the result!

let fibs =
    Seq.unfold
        (fun (n0, n1) -> Some(n0, (n1, n0 + n1)))
        (1, 1)

let reach_index s m =
    s
    |> Seq.mapi (fun i x -> (i, x))
    |> Seq.find_index (fun x -> x > m)

let pb2seq n =
    Seq.truncate (reach_index fibs n) fibs
    |> Seq.filter (fun x -> x % 2 = 0)
    |> Seq.fold (fun acc x -> acc + x) 0

printf "euler problem with seq (1000000): %a\n" output_any (pb2seq 1000000)

Why don’t I like this? because I have to manipulate the sequence twice, first to find the index of the last element to take into account, and second to compute the problem answer.I would have like a method ‘take_while’ in Seq to write something in the line of:

let pb2_not_compilable n =
    fibs
    |> Seq.take_while (fun x -> x < n)
    |> Seq.filter (fun x -> x % 2 = 0)
    |> Seq.fold (fun acc x -> acc + x) 0

… am I missing something?Btw, how to implement this “take_while” function? I’ve try, but Seq has a ‘hd’ function but no ‘tail’ … what am I missing here? I’m sure this is possible to implement …

The previous blogpost implements a hylomorphism in Erlang.

Following is again the same in F#: but this is part of my exercices to learn F#, and I just begin to learn … so the code is … ergh, whatever.

And I have no idea how to implement default values. Any advice?

#light
open Microsoft.FSharp.Collections.List;

let rec hylo step till col inj v s =
    if till s
    then
        v
    else
        let ns = step s in
        let nv = inj v (col s) in
        hylo step till col inj nv ns;

let fact =
    let step = fun x -> x - 1 in
    let till = fun x -> x <= 1 in
    let col = fun x -> x in
    let inj = fun a x -> a * x in
    hylo step till col inj 1;

let evens n =
    let step = fun x -> x + 2 in
    let till = fun x -> x >= n in
    let col = fun x -> x in
    let inj = fun a x -> x :: a in
    rev (hylo step till col inj [] 0);

let to_bin n =
    let step = fun x -> x / 2 in
    let till = fun x -> x <= 0 in
    let col = fun x -> x % 2 in
    let inj = fun a x -> x :: a in
    hylo step till col inj [] n;

let expand l =
    let rec duplicate c n a =
        if n > 0
        then duplicate c (n - 1) (c::a)
        else a
        in
    let step = fun li -> tl li in
    let till = fun li -> match li with |[] -> true |_ -> false in
    let col = fun li -> match hd(li) with |(c,n) -> duplicate c n [] in
    let inj = fun a x -> (x :: a) in
    rev (hylo step till col inj [] l);

do printf "fact(5)=%a\n" output_any (fact 5);
do printf "evens(10)=%a\n" output_any (evens 10);
do printf "to_bin(10)=%a\n" output_any (to_bin 10);
do printf "expand([(1,2); (4,7)])=%a\n" output_any (expand [(1, 2); (4,7)]);