Why does this cause an Overflow error? (SML)

Question

This code produces an Overflow error and I am not entirely sure why. This is in SML which I am somewhat unfamiliar with at the moment so I am not entirely sure how to fix it.

fun detPrime(num:int, divn:int) =
    if divn = num
    then true
    else if num mod divn = 0
         then false
         else detPrime(num, divn+1);

fun prime(num: int) = 
    detPrime(num, 2);

fun goldbachHelp(num1: int, num2: int) = 
    if num2 > num1
    then []
    else if prime(num2) = true andalso prime(num1) = true
         then num2::num1::[]
         else goldbachHelp(num1-1, num2+1);

fun goldbach(num: int) = 
    if num mod 2 = 1
    then []
    else goldbachHelp(num, 0);

goldbach(100);

Answer 1

Why does this cause an Overflow error?

More importantly, how do you find out?

Overflow means an integer exceeds the bounds of Int.minInt or Int.maxInt. All you do is increment and decrement by one in different places. So somehow a condition that should eventually terminate these increments and decrements is not met. I've modified your code slightly and inserted some print statements in it:

fun detPrime (num, divn) =
    num = divn orelse
    num mod divn <> 0 andalso
    detPrime (num, divn+1)

fun isPrime num =
    ( print ("isPrime(" ^ Int.toString num ^ ")\n")
    ; detPrime (num, 2)
    )

fun goldbachHelp (num1, num2) =
    ( print ("goldbachHelp(" ^ Int.toString num1 ^ ", " ^ Int.toString num2 ^")\n")
    ; if num1 > num2
      then []
      else if isPrime num1 andalso isPrime num2
           then [num2, num1]
           else goldbachHelp(num1+1, num2-1)
    )

fun goldbach num =
    goldbachHelp (0, num)

Calling this code prints:

- goldbach 100;
goldbachHelp(0, 100)
isPrime(0)
goldbachHelp(1, 99)
isPrime(1)

uncaught exception Overflow [overflow]
  raised at: <file stdIn>

Evaluating isPrime 1 by hand gives:

isPrime 1 ~> detPrime (1, 2)
          ~> 1 = 2 orelse 1 mod 2 <> 0 andalso detPrime (1, 2+1)
          ~> 1 mod 2 <> 0 andalso detPrime (1, 2+1)
          ~> 1 <> 0 andalso detPrime (1, 2+1)
          ~> detPrime (1, 3)
          ~> 1 = 3 orelse 1 mod 3 <> 0 andalso detPrime (1, 3+1)
          ~> 1 mod 3 <> 0 andalso detPrime (1, 3+1)
          ~> 1 <> 0 andalso detPrime (1, 3+1)
          ~> detPrime (1, 4)
          ~> 1 = 4 orelse 1 mod 4 <> 0 andalso detPrime (1, 4+1)
          ~> 1 mod 4 <> 0 andalso detPrime (1, 4+1)
          ~> 1 <> 0 andalso detPrime (1, 4+1)
          ~> detPrime (1, 5)
          ~> ... you can see where this is going ...

It seems then that even though you probably tested isPrime with reasonable input (num ≥ 2, since that is by definition the smallest prime), goldbachHelp manages to call it with unreasonable input:

goldbach 100 ~> goldbachHelp (0, 100)
             ~> if 0 > 100
                then []
                else if isPrime 0 andalso isPrime 100
                     then [100, 0]
                     else goldbachHelp(0+1, 100-1)
             ~> if isPrime 0 andalso isPrime 100
                then [100, 0]
                else goldbachHelp(0+1, 100-1)
             ~> if detPrime (0, 2) andalso isPrime 100
                then [100, 0]
                else goldbachHelp(0+1, 100-1)
             ~> if 0 = 2 orelse
                   0 mod 2 <> 0 andalso
                   detPrime (0, 3) andalso isPrime 100
                then [100, 0]
                else goldbachHelp(0+1, 100-1)
             ~> if false orelse
                   false andalso
                   detPrime (0, 3) andalso isPrime 100
                then [100, 0]
                else goldbachHelp(0+1, 100-1)
             ~> if false andalso isPrime 100
                then [100, 0]
                else goldbachHelp(0+1, 100-1)
             ~> goldbachHelp(1, 99)
             ~> if 1 > 99
                then []
                else if isPrime 1 andalso isPrime 99
                     then [99, 1]
                     else goldbachHelp(1+1, 99-1)
             ~> if isPrime 1 andalso isPrime 99
                then [99, 1]
                else goldbachHelp(1+1, 99-1)
             ~> ... you can see where this is going ...

Incidentally, isPrime 0 works, but isPrime 1 in the subsequent iteration doesn't.

---

Things you can do when the problem is hard to locate:

• Insert print statements to find the point where computation diverges.

• Test your sub-components thoroughly; isPrime accepts an int; you don't expect to call it on any int, but what if you did? Instead of testing every possible int, divide the domain into equivalence classes and check the boundaries: What if it's as small as it can get? What if it's as big as it can get? What if it's zero? What if it's just above zero? What if it's just below zero? Known primes, non-primes and pseudo-primes of various sizes. (Incidentally, isPrime (~1) also causes Overflow.)

• Make isPrime robust:

  fun isPrime num =
      num > 1 andalso detPrime (num, 2)