Loading ...
Sorry, an error occurred while loading the content.

Count Factorial Using Float Type

Expand Messages
  • LORENZO
    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
    Message 1 of 5 , Apr 3 8:55 AM
    • 0 Attachment
      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 ;;
    • Lars Nilsson
      ... 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
      Message 2 of 5 , Apr 3 9:06 AM
      • 0 Attachment
        On 4/3/07, LORENZO <arniwarp@...> wrote:
        > 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...

        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

        >
        > 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 ;;
      • William D. Neumann
        ... 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
        Message 3 of 5 , Apr 3 11:03 AM
        • 0 Attachment
          > 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

          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"

          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
        • William D. Neumann
          ... 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
          Message 4 of 5 , Apr 3 11:44 AM
          • 0 Attachment
            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
            > 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>

            # 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
          • LORENZO
            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
            Message 5 of 5 , Apr 8 1:06 AM
            • 0 Attachment
              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:
              >
              > > 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).
              > 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
              >
            Your message has been successfully submitted and would be delivered to recipients shortly.