Почему это вызывает ошибку переполнения? (СМЛ) - PullRequest
Новая
       9

Почему это вызывает ошибку переполнения? (СМЛ)

0 голосов
/ 02 мая 2018

Этот код вызывает ошибку переполнения, и я не совсем уверен, почему. Это на языке SML, с которым я сейчас немного не знаком, поэтому я не совсем уверен, как это исправить. 

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

1 Ответ

0 голосов
/ 02 мая 2018

Почему это вызывает ошибку переполнения?

Что важнее, как ты узнал?

Переполнение означает, что целое число превышает границы Int.minInt или Int.maxInt. Все, что вы делаете, это увеличиваете и уменьшаете по одному в разных местах. Так что каким-то образом условие, которое должно в конечном итоге прекратить эти приращения и убывания, не выполняется. Я немного изменил ваш код и вставил в него несколько операторов print: 

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)

При вызове этого кода печатается: 

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

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

Оценка isPrime 1 от руки дает: 

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 ...

Похоже, что даже если вы, вероятно, протестировали isPrime с разумным вводом (num ≥ 2, поскольку по определению это наименьшее простое число), goldbachHelp удается вызвать его с необоснованным вводом: 

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 ...

Кстати, isPrime 0 работает, но isPrime 1 в последующей итерации - нет.

Вещи, которые вы можете сделать, когда трудно определить проблему:

  • Вставьте операторы печати, чтобы найти точку, где вычисления расходятся.

  • Тщательно проверьте свои подкомпоненты; isPrime принимает int ; Вы не ожидаете, что он позвонит на any int , но что, если вы это сделали? Вместо того, чтобы проверять все возможные int , , разделите домен на классы эквивалентности и проверьте границы : Что делать, если он настолько мал, насколько он может получить? Что, если он будет настолько большим, насколько сможет? Что делать, если это ноль? Что если оно чуть выше нуля? Что если оно чуть ниже нуля? Известны простые, непростые и псевдопростые числа различных размеров. (Кстати, isPrime (~1) также вызывает переполнение.)

  • Марка isPrime Надежность : 

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