大数的最大公约数算法

Question

我正在尝试创建一个处理非常大的数的gcd函数。因此，到目前为止，我尝试过的所有方法都导致错误。例如：

fun gcd(a : Int.toLarge, b : Int.toLarge): Int.toLarge =
  if   b = 0
  then a
  else gcd(b, a mod b)` 

给我以下错误提示：

Error:unbound type constructor : toLarge in path Int.toLarge

有人可以给我一些建议吗？我的程序的其余部分似乎运行良好。先谢谢你！

- Stelios Dr

Answer 1

你误将 Int.toLarge 当作一种类型，实际上它是个函数。你所需要的类型是 IntInf.int。无论你输入什么类型的数字，gcd 函数看起来都是一样的；但你可能需要从另一个模块中引用算术运算符。

下面是针对类型 Int.int 的 gcd 函数：

fun gcd (a, 0) = a
  | gcd (a, b) = gcd (b, a - b*(a div b))

由于SML/NJ的算术运算符是重载的，因此这里为IntInf.int提供���个：

fun gcd (a, 0) = a : IntInf.int
  | gcd (a, b) = gcd (b, a - b*(a div b))

- sshine