CODEWITHSUNDEEP
mathocaml
user19878266
user19878266

Reputation:

Why does a factorial function gives me a negative number

I made a factorial function permitting me to calculate factorials of course and as we know, a factorial can never be < 0. And my code gives me some times negative numbers... Here it is:

exception FactorialError of string;;
let rec factorial (n: int) : int = (
  if n < 0 then raise (FactorialError "The number has to be upper or equal then 0");
  if n == 0 then 1 else n * factorial(n-1);
);;

let value = ref (1);;
for i = 0 to 100 do
(
  value := factorial i;
  if !value = 0 then raise (FactorialError ("Factorial is no more possible after i = " ^ 
string_of_int i)) else print_string ("i: " ^ string_of_int i);
  print_string "\nValue: ";
  print_int !value;
  print_string "\n";
)
done;;

And here are the results for some of them only:

i: 0
Value: 1

i: 1
Value: 1

...

i: 20
Value : 2432902008176640000

i: 21
Value : -4249290049419214848 // <- Here is the problem

... Here is the problem but not only for the 21 value but also for many other...

Upvotes: 0

Views: 240

Answers (3)

Moth
Moth

Reputation: 263

What happened is that OCaml's int is a machine int; more efficient, and closer to the hardware than representations chosen by e.g. some popular scripting languages, but with one caveat: Machine ints are limited (modulo) 264 or 232, the size of a machine word.

OCaml ints are further limited because they're tagged, this is great for efficiency in a garbage-collected language, as it's a very simple way to avoid a huge number of allocations. This however means they're modulo 263.
int is also signed, that is, half what could be represented with 263 numbers is reserved to negative numbers.

This all means that when you're using int, your values can only be in range [-4611686018427387904, 4611686018427387904), from -262 up to but not including 262.
Lucky for you, you don't have to think about all this, because OCaml exposes Int.(min_int, max_int), readily calculated for you based on your platform. If you anticipate your application will need a wider range than what OCaml provides with int, you look for something more elaborate. 21! happens to be outside of this range.

That "something more elaborate" would be infinite precision or memory-backed integers. The Z module from ocaml/zarith is the standard OCaml implementation of this data structure.

Here's how we'll use Zarith, assuming we have a project setup that relies on opam and dune:

  1. opam install -y zarith will bring you the package locally so that you can use it in your projects.
  2. add a (libraries zarith), or add zarith to an existent (libraries ...) field to the dune file next to the module that uses zarith.
  3. you'll be able to implement fac like this:
let rec zfac n =
  if Z.Compare.(n = zero) then Z.one 
  else Z.(n * zfac (pred n))

let fac n =
  if n < 0 then invalid_arg "fac n where n < 0" 
  else zfac Z.(of_int n)

Notice that the error case is checked only once, outside of the recursive function, and that I'm using = (or its opposite, <>) and avoiding ==, as it and != are physical equality operators rather than structural equality operators: they check if two things are in the same spot in memory, so they'll often give you unexpected results. Try for yourself: let x = [1;2] and y = [1;2] in x == y, this will be false, because x and y occupy different spots in memory!
There was also no need to use extra parenthesis or specify the types. You'll find such style niceties in documents online, I suggest OCaml guidelines and best practices.

Now, if you use e.g. Z.to_string in a toplevel to check the value of fac 21, you'll find the correct answer: 51090942171709440000

Alternatively if you're just trying things out in a REPL, and you've done at least step 1 from above, you can enter #require "zarith";; and play with the library interactively.

Upvotes: 1

Jeffrey Scofield
Jeffrey Scofield

Reputation: 66813

Here is code that uses the Big_int module to calculate a large factorial value:

$ cat bigfact.ml
open Big_int

let rec big_fact n =
    if n < 2 then unit_big_int
    else
        mult_big_int (big_int_of_int n) (big_fact (n - 1))

Use the function to calculate big_fact 100:

$ ocaml nums.cma
OCaml version 4.14.0
Enter #help;; for help.

# #use "bigfact.ml";;
val big_fact : int -> Big_int.big_int = <fun>
# string_of_big_int (big_fact 100);;
- : string =
    "93326215443944152681699238856266700490
     71596826438162146859296389521759999322
     99156089414639761565182862536979208272
     23758251185210916864000000000000000000
     000000"

For what it's worth, I believe the Big_int module is being replaced by the newer Zarith module.

Upvotes: 1

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186793

You have an integer overflow. Please, note that 64bit signed integer must be within

[-9223372036854775808 .. 9223372036854775807]

range. If you go beyond the ranges, you'll get incorrect value:

2432902008176640000 * 21 == 51090942171709440000 > 9223372036854775807

If you want to compute exact factorial value, have a look at arbitrary precision integer big_int

Upvotes: 1

Related Questions