为什么阶乘函数给我一个负数

Question

我创建了一个阶乘函数，当然可以让我计算阶乘，正如我们所知，阶乘 永远不可能是 < 0。我的代码有时会给我负数......这是：

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

这里只是其中一些的结果：

i: 0
Value: 1

i: 1
Value: 1

...

i: 20
Value : 2432902008176640000

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

...这是问题，但不仅是 21 值，还有许多其他...

Answer 1

你有一个整数溢出。请注意，

64

位有符号整数必须在

以内

[-9223372036854775808 .. 9223372036854775807]

范围。如果你去 beyond 范围，你会得到 incorrect 价值：

2432902008176640000 * 21 == 51090942171709440000 > 9223372036854775807

如果你想计算 exact 阶乘值，看看 arbitrary precision integer big_int

Answer 2

这是使用

Big_int

模块计算大阶乘值的代码：

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

使用函数计算

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"

就其价值而言，我相信

Big_int

模块正在被更新的

Zarith

模块所取代。

Answer 3

OCaml

int

是机器整数；比例如选择的表示更有效，更接近硬件。一些流行的脚本语言，但有一个警告：机器整数是有限的（模）2⁶⁴，或 2³²，一个机器字的大小。
OCaml int further limited 因为它们是 tagged，这对于垃圾收集语言的效率非常有用，因为这是避免大量分配的非常简单的方法。然而，这意味着它们是模 2⁶³。

int

也是 signed，也就是说，可以用 2⁶³ 数表示的一半保留给负数。

这一切都意味着 OCaml

int

只能在 [-4611686018427387904, 4611686018427387904) 范围内，从 -2⁶² 到但不包括 2⁶²。幸运的是，您不必考虑所有这些，因为 OCaml 公开了

Int.(min_int, max_int)

，所以如果您预计您的应用程序需要更广泛的范围，您就会寻找更精细的东西。 21！恰好在这个范围之外。

“更精细的东西”将是 无限精度 或内存支持的整数。来自 ocaml/zarith 的 Z 模块 是该数据结构的标准 OCaml 实现。

以下是我们将如何使用 Zarith，假设我们有一个依赖于

opam

和

dune

的设置：

首先，

opam install -y zarith

会把包带到本地，这样你就可以在你的项目中使用它了。
然后，您将打开项目的

bin/dune

文件并添加一个

(libraries zarith)

，或将

zarith

添加到现有的

(libraries ...)

字段。
最后，您将能够像这样实现

fac

：

let rec zfac n =
 if Z.Compare.(n <= one) 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)

现在，如果你使用例如

Z.print

查看

fac 21

的值，你会找到正确答案：51090942171709440000