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)