16 people like it.

Inline factorial samples with fix point

While reading Tomas Petricek's master thesis, came across FIX operator implementation. Decided to experiment with various implementations of factorial.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
let rec fix f x = f (fix f) x

let inline factf1 n =
    let loop = fix (fun f x -> 
        if x<=LanguagePrimitives.GenericOne 
            then LanguagePrimitives.GenericOne
            else x * (f (x - LanguagePrimitives.GenericOne)))
    loop n

let rec fix2 f a b = f (fix2 f) a b

let inline factf2 n =
    let loop = fix2 (fun f acc n -> 
        if n<=LanguagePrimitives.GenericOne 
            then acc 
            else f (n*acc) (n-LanguagePrimitives.GenericOne))
    loop LanguagePrimitives.GenericOne n

let inline facti n =
    let rec loop acc n = 
       if n<=LanguagePrimitives.GenericOne 
        then acc 
        else loop (n*acc) (n-LanguagePrimitives.GenericOne)
    loop LanguagePrimitives.GenericOne n


(* It seems there's little difference performance-wise. Still, tail-recursive implementation is faster than CPS.
> [1I..2000I] |> List.iter (factf1 >> ignore);;
Real: 00:00:04.603, CPU: 00:00:04.586, GC gen0: 480, gen1: 1, gen2: 0
val it : unit = ()
> [1I..2000I] |> List.iter (factf2 >> ignore);;
Real: 00:00:04.868, CPU: 00:00:04.851, GC gen0: 556, gen1: 1, gen2: 0
val it : unit = ()
> [1I..2000I] |> List.iter (facti >> ignore);;
Real: 00:00:04.043, CPU: 00:00:04.024, GC gen0: 548, gen1: 0, gen2: 0
val it : unit = ()
> 
*)
val fix : f:(('a -> 'b) -> 'a -> 'b) -> x:'a -> 'b

Full name: Script.fix
val f : (('a -> 'b) -> 'a -> 'b)
val x : 'a
val factf1 : n:'a -> 'b (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)

Full name: Script.factf1
val n : 'a (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)
val loop : ('a -> 'b) (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)
val f : ('a -> 'b) (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)
val x : 'a (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)
module LanguagePrimitives

from Microsoft.FSharp.Core
val GenericOne<'T (requires member get_One)> : 'T (requires member get_One)

Full name: Microsoft.FSharp.Core.LanguagePrimitives.GenericOne
val fix2 : f:(('a -> 'b -> 'c) -> 'a -> 'b -> 'c) -> a:'a -> b:'b -> 'c

Full name: Script.fix2
val f : (('a -> 'b -> 'c) -> 'a -> 'b -> 'c)
val a : 'a
val b : 'b
val factf2 : n:'a -> 'b (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)

Full name: Script.factf2
val loop : ('b -> 'a -> 'b) (requires member get_One and member ( * ) and member get_One and member ( - ) and comparison and member get_One)
val f : ('b -> 'a -> 'b) (requires member get_One and member ( * ) and member get_One and member ( - ) and comparison and member get_One)
val acc : 'b (requires member get_One and member ( * ) and member get_One and member ( - ) and comparison and member get_One)
val facti : n:'a -> 'b (requires member ( * ) and member get_One and member ( - ) and comparison and member get_One and member get_One)

Full name: Script.facti
Raw view New version

More information

Link:http://fssnip.net/1U
Posted:6 years ago
Author:Dmitri Pavlenkov
Tags: factorial , recursive , inline , fix , languageprimitives