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

else "Factorial = " ^ (string_of_float ( factorial x)) ;;

let fact =

let n = float_of_string Sys.argv.(1) in

print_string ( factPositive n);;

fact ;; - On 4/3/07, LORENZO <arniwarp@...> wrote:
> It's amazing how fast OCaml deals with factorial

You do realize that performing 170 multiplications using normal

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

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

>

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

> else "Factorial = " ^ (string_of_float ( factorial x)) ;;

>

> let fact =

> let n = float_of_string Sys.argv.(1) in

> print_string ( factPositive n);;

>

> fact ;; > It's amazing how fast OCaml deals with factorial

OK... this is a good example of where floating point computation might let

> 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

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"

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

method:

# f2s f170;;

- : string =

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

# let sbi_f170 = string_of_big_int bi_f170;;

val sbi_f170 : string =

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

# let diff = sub_big_int bi_f170 bi_ff170;;

val diff : Big_int.big_int = <abstr>

# 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."

-- Neko Case

Life is unfair. Kill yourself or get over it.

-- Black Box Recorder- 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

One other thing to note here. If you are satisfied with an approximate

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

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>

# let diff' = sub_big_int bi_f170 bi_s170;;

val diff' : Big_int.big_int = <abstr>

# 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."

-- Neko Case

Life is unfair. Kill yourself or get over it.

-- Black Box Recorder - Hi,

Thankx to Lars' careful remind of float type

precision issue and also appreciate to

William's kind and great supply corrected

version using Big_int of nums.cma, I was not

aware of the problem while trying OCaml...

Sincerely

--- In ocaml_beginners@yahoogroups.com, "William D. Neumann"

<wneumann@...> wrote:>

issue (if

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

> > we care about accuracy -- after all, we're within 7e-14% of the

correct

> > answer).

> also be happy with Stirling's approximation

>

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

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

> Just a note.

>

> William D. Neumann

>