Which factorial is the fastest?

[gmhwxi]

Please take a guess.

Which of the following three is the fastest?

(* ****** ****** *)

//

fun

{a:t0p}

gfact1(n: int): a = let

//

overload * with gmul_int_val

//

in

//

(fix

f( i: int

, n: int, r: a): a =>

if i < n

then f(i+1, n, (i+1)*r) else r

// end of [if]

)(0, n, gnumber_int<a>(1))

//

end // end of [let] // end of [gfact1]

//

(* ****** ****** *)

fun

{a:t0p}

gfact2(n: int): a = let

//

overload * with gmul_int_val

//

fun

loop

(xs: stream_vt(int), r0: a): a =

(

case+ !xs of

| ~stream_vt_nil

() => r0

| ~stream_vt_cons

(x0, xs) => loop(xs, (x0+1)*r0)

)

//

val _0_n_ =

streamize_intrange_lr<>(0, n)

//

in

loop(_0_n_, gnumber_int<a>(1))

end // end of [let] // end of [gfact2]

(* ****** ****** *)

fun

{a:t0p}

product

(xs: stream_vt(a)): a = let

//

overload * with gmul_val_val

//

fun

loop

(xs: stream_vt(a), r0: a): a =

(

case+ !xs of

| ~stream_vt_nil() => r0

| ~stream_vt_cons(x0, xs) => loop(xs, r0*x0)

)

//

in

loop(xs, gnumber_int<a>(1))

end // end of [product]

fun

{a:t0p}

gfact3(n: int): a =

product<a>

(stream_vt_map_cloptr

(streamize_intrange_lr<>(0, n), lam(i) => gnumber_int<a>(i+1))

) (* end of [gfact3] *)

[Raoul Duke]

whichever fits in the cache :-)

[gmhwxi]

It turns out that:

gfact1 is the fastest if machine-level integers
(int32, int64, etc) are used. This is not surprising.

What is a bit surprising is that gfact3 is the fastest
when GMP integers are used. Note that gfact3 uses
a linear stream to implement a loop. There is a lot of
malloc/free when such a loop is executed. However, this
overhead become negligible once the loop body is not
completely computationally trivial.