SML中的溢出：取幂程序

Question

我正在尝试编写一个简单的程序，用于计算语言Standard ML中x的17次幂。我应该用“帮助程序”来做：

fun help (y:int) = y * y * y * y; 

fun power17 (x:int) = help (help (help (help (x)))) * x; 

这会导致溢出。有人可以告诉我为什么这样做吗？

Answer 1

您正在获取整数溢出。如果你想要你的代码工作，你需要使用。

fun help (y: LargeInt.int) = y * y * y * y; 

    fun power17 (x: int) = 
    let 
     val x' = Int.toLarge x 
    in 
     help (help (help (help (x')))) * x' 
    end; 

一两件事，那代码不计算x ** 17，而不是它做x ** 257。

你应该只调用help两次：

fun power17 (x:int) = (help (help x)) * x; 

Answer 2

你的函数不计算17.电源评测吧：

power17 2 ~> help (help (help (help x))) * 2 
      ~> help (help (help (2 * 2 * 2 * 2))) * 2 (* that's 2^5 *) 
      ~> help (help (help (8))) * 2 
      ~> help (help (8 * 8 * 8 * 8)) * 2  (* that's 2^13 *) 
      ~> help (help (4096)) * 2 
      ~> help (4096 * 4096 * 4096 * 4096) * 2 (* that's 2^49 *) 
      ~> raise Overflow (* most SML compilers have 32-bit ints *) 

也许你的意思是写：

fun power17 x = help x * help x * help x * help x * x 

这听起来像递归的理想情况，但：

fun power (x, 0) = 1 
    | power (x, n) = x * power (x, n-1) 

fun power17 x = power (x, 17)