CODEWITHSUNDEEP
overflowsmlexponentiation
Mimi
Mimi

Reputation: 29

Overflow in SML: Exponentiation procedure

I'm trying to write a simple procedure that calculates x to the power of 17 in the language Standard ML. I'm supposed to do it with a "helping procedure":

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

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

This causes an overflow. Can somebody tell me why it does so?

Upvotes: 0

Views: 201

Answers (2)

sshine
sshine

Reputation: 16105

Your function does not calculate the power of 17. Evaluating it:

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

Perhaps you meant to write:

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

It sounds like an ideal case for recursion, though:

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

fun power17 x = power (x, 17)

Upvotes: 0

snahor
snahor

Reputation: 1201

You are getting an Integer Overflow. If you want your code to work, you need to use LargeInt.int.

  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;

One more thing, that code is not calculating x ** 17, instead it's doing x ** 257.

You should only call help twice:

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

Upvotes: 1

Related Questions