"ocaml_beginners"::[] Count Factorial Using Float Type

It's amazing how fast OCaml deals with factorial
computations up to 170 using Float type. Since
the result is like 7.25741561531e+306, I would
like to see it in human readable format like 7257415...

Does there any String function transform the format?
And if I just want to keep the leading non-zero number
as a string, how can I do? My code is as below

----------------------------------
let factPositive x =
let rec factorial x =
if x = 1.0 then 1.0
else x *. ( factorial ( x -. 1.0)) in
if (x <0.0) then "error: negative argument&quot;
else "Factorial = " ^ (string_of_float ( factorial x)) ;;

let fact =
let n = float_of_string Sys.argv.(1) in
print_string ( factPositive n);;

fact ;;

Messages in this topic (1) Reply (via web post) | Start a new topic

.

On 4/3/07, LORENZO < arniwarp%40yahoo.com.tw">arniwarpyahoo.com.tw> wrote:
&gt; It's amazing how fast OCaml deals with factorial
> computations up to 170 using Float type. Since
&gt; the result is like 7.25741561531e+306, I would
&gt; like to see it in human readable format like 7257415...

You do realize that performing 170 multiplications using normal
floating point numbers shouldn't take a whole lot of time, regardless
of what language is used, right? There's a big difference between
floats and "unlimited" integers/bigints, etc. The former has for all
intents and purposes a constant time for multiplication, while the
latter, depending on algorithm, has a quite different complexity as
the numbers get larger.

Lars Nilsson

>
&gt; Does there any String function transform the format?
> And if I just want to keep the leading non-zero number
&gt; as a string, how can I do? My code is as below
&gt;
> ----------------------------------
>; let factPositive x =
> let rec factorial x =
> if x = 1.0 then 1.0
> else x *. ( factorial ( x -. 1.0)) in
> if (x <0.0) then "error: negative argument&quot;
> else "Factorial = " ^ (string_of_float ( factorial x)) ;;
>
> let fact =
> let n = float_of_string Sys.argv.(1) in
> print_string ( factPositive n);;
>;
> fact ;;

Messages in this topic (0) Reply (via web post) | Start a new topic

.

> It's amazing how fast OCaml deals with factorial
> computations up to 170 using Float type. Since
&gt; the result is like 7.25741561531e+306, I would
&gt; like to see it in human readable format like 7257415...
>
&gt; Does there any String function transform the format?
> And if I just want to keep the leading non-zero number
&gt; as a string, how can I do? My code is as below

OK... this is a good example of where floating point computation might let
you down -- it's not exact.

Consider your example above, computing 170! using floats. The first hint
that you don't have the correct value is that we are apparently storing an
approximately 980 bit number in just 64 bits of space. Unless you're
number is one of a special (relatively) few, we're obviously going to be
losing some information here. Let's show an example of this:

# let f2s f = Printf.sprintf "%.0f" f;;
val f2s : float -> string = <fun>;

# f2s 123.456;;
- : string = "123&quot;

So now, let's use f2s on f170 = 170! computed using your floating point
method:

# f2s f170;;
- : string =

&quot;72574156153079940453996357155895914678961841172422578
034055442117556932462152715774446149978680776400131841
762719858268015977432472479790779953366194299806857932
857680533608861121498254370813563656990432878846140027
884906945304696617530078018969625637211046192423573487
35986883814984039817295623520648167424"

Right away, we know something is wrong here, as there should be a run of
0s at the end of the number (41 of them, to be exact), and we don't have a
single one.

So how close are we to the correct answer? Well, let's compute it first:

# #load "nums.cma";;
# open Big_int;;
# let rec bi_fact n =
if le_big_int n unit_big_int then unit_big_int
else mult_big_int n (bi_fact (pred_big_int n))
;;
val bi_fact : Big_int.big_int -> Big_int.big_int = <fun>;

# let bi_f170 = bi_fact (big_int_of_int 170);;
val bi_f170 : Big_int.big_int = <abstr&gt;

# let sbi_f170 = string_of_big_int bi_f170;;
val sbi_f170 : string =

&quot;7257415615307998967396728211129263114716991681296451
37654357779890056184340170615785235074924261745951149
09912378385207766660225654427530253289007732075109024
00430280058295603966612599658257104398558294257568966
31343961226257109494680671120556888045719334021266145
2800000000000000000000000000000000000000000"

(see all the 0s!)

Now let's look at the difference:
# let bi_ff170 = big_int_of_string (f2s f170);;
val bi_ff170 : Big_int.big_int = <abstr&gt;
# let diff = sub_big_int bi_f170 bi_ff170;;
val diff : Big_int.big_int = <abstr&gt;
# string_of_big_int diff;;
- : string =
"49219970924955396716468208075640541935731380335871448
685971864345804077357513745398194983068149658526939750
682793181947739473335641537775302166071445120049347178
544627742211757480328592509696843523106511215680406252
850537034036719178934722355934190954512640131161850159
60182704376479351832576"

So we're off by about 5e292. Depending on how you look at it, that's
either a huge issue (if we care about precision), or a miniscule issue (if
we care about accuracy -- after all, we're within 7e-14% of the correct
answer).

Anyway to answer your original question:
No, there's no "string" function, but you can use the format specifiers of
the Printf module to do the conversion.

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers. We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy.&quot;

-- Neko Case

Life is unfair. Kill yourself or get over it.
-- Black Box Recorder

Messages in this topic (0) Reply (via web post) | Start a new topic

.

On Tue, 3 Apr 2007, William D. Neumann wrote:

> So we're off by about 5e292. Depending on how you look at it, that's
&gt; either a huge issue (if we care about precision), or a miniscule issue (if
> we care about accuracy -- after all, we're within 7e-14% of the correct
> answer).

One other thing to note here. If you are satisfied with an approximate
answer, such as the one computed by the float factorial, you may also be
happy with Stirling's approximation

n! approx sqrt ((2*n + (1/3)) * pi) * n^n * e^(-n)

Or, in OCaml:
# let stirling f =
let pi = acos (-. 1.)
and e_pow = f *. (log f) -. f in
sqrt ((2. *. f +. (1. /. 3.)) *. pi) *. (exp e_pow)
;;
val stirling : float -> float = <fun>;

# stirling 5.;;
- : float = 119.970030169685486

# stirling 170.;;
- : float = 7.25741387665077865e+306

# let bi_s170 = big_int_of_string (f2s (stirling 170.));;
val bi_s170 : Big_int.big_int = <abstr&gt;

# let diff' = sub_big_int bi_f170 bi_s170;;
val diff' : Big_int.big_int = <abstr&gt;

# string_of_big_int diff';;
- : string =
"173865722031901065217218838396758965740121558460469341
0070279842007462086622428973708292096185047615684822616
5952137642518127279708914335809192786795059054247595567
1905498770224883503671136127464679562582749639639116441
9877369701262767632351989895882343822492935813690943947
726344674962688141334413312"

And so here we're accurate to within 2.5e-5 %.

Just a note.

William D. Neumann

---

"There's just so many extra children, we could just feed the
children to these tigers. We don't need them, we're not doing
anything with them.

Tigers are noble and sleek; children are loud and messy.&quot;

-- Neko Case

Life is unfair. Kill yourself or get over it.
-- Black Box Recorder

Messages in this topic (0) Reply (via web post) | Start a new topic

.