Can anyone please help me to understand that why Int type overflow result is not consistent with higher numbers. Sometime it is positive, sometime negative and finally converge to zero.
import scala.annotation.tailrec
object FactorialExample {
def main(args: Array[String]): Unit = {
(1 to 100).foreach(i => println(s"Factorial of ${i} is " + factorial(i)))
}
def factorial(i: Int): Int = {
@tailrec
def fact(i: Int, acc: Int): Int = {
if (i <= 0) acc
else fact(i - 1, acc * i)
}
fact(i, 1)
}
}
why Int type overflow result is not consistent with higher numbers. Sometime it is positive, sometime negative and finally converge to zero.
This is just how overflowing int types behave. You can read more at e.g. Modular arithmetic or Two's Complement. Do you have a specific question?
I do understand that its overflow situation but my question was once overflow situation comes into picture compiler should throw a number by which user should be aware that its garbage and need to use other data type
This is answered at Why, In Java arithmetic, overflow or underflow will never throw an Exception?
As others have pointed out, Scala, and Java, do not perform overflow checking on integer values by default. (I agree that quietly overflowing a value can result in unexpected—and unwanted—behavior, and many very subtle bugs.) However, all is not lost. java.lang.Math has static methods (addExact, incrementExact, multiplyExact, subtractExact, etc.) that will throw an ArithmeticException if a calculation overflows the underlying type. For example:
scala> def factorial(n: Int): Int = {
| if(n <= 1) 1
| else Math.multiplyExact(n, factorial(n - 1))
| }
factorial: (n: Int)Int
scala> factorial(12)
res0: Int = 479001600
scala> factorial(13)
java.lang.ArithmeticException: integer overflow
at java.lang.Math.multiplyExact(Math.java:867)
at .factorial(<console>:13)
... 28 elided
This version isn't tail recursive, and throwing exceptions violates functional programming principles (a better approach is to return a type that encapsulates possible errors, such as a Try[Int] or Either[Throwable, Int]), but it will detect and report overflows of the Int type. Refer to java.lang.Math for further details.
For example, here's a functional version that will not exhaust the stack:
scala> import scala.annotation.tailrec
import scala.annotation.tailrec
scala> import scala.util.Try
import scala.util.Try
scala> def factorial(n: Int): Try[Int] = {
| @tailrec
| def fact(i: Int, acc: Int): Int = {
| if(i <= 1) acc
| else fact(i - 1, Math.multiplyExact(i, acc))
| }
| Try(fact(n, 1))
| }
scala> factorial(12)
res0: scala.util.Try[Int] = Success(479001600)
scala> factorial(13)
res1: scala.util.Try[Int] = Failure(java.lang.ArithmeticException: integer overflow)
Regarding the overflowed value: you can regard such results as being effectively random. It is the result of retaining only the right-most 32 bits (the capacity of an Int type) of the overflowed result. If the most significant bit is set, then this value will be treated as a negative value. (As others have pointed out, see Two's Complement for a more detailed explanation of how Int bit patterns are interpreted.) While it would depend upon the calculation you're performing, the results would not converge on zero in the general case.
For example, factorial(13) is the lowest argument value that causes an Int overflow. Without using Math.multiplyExact, your original function would return the value 1932053504—which is not obviously wrong, unfortunately. If we use Long instead of Int, we can calculate this result exactly as 6227020800. But let's look at these numbers in their binary representations:
scala> 1932053504.toBinaryString
res0: String = 1110011001010001100110000000000
scala> 6227020800L.toBinaryString
res1: String = 101110011001010001100110000000000
The right-most 32 bits have the same values! (Note that leading zeros are omitted.) However, the Long representation has an addition bit, which cannot be stored in the Int representation, and that makes all the difference. Unfortunately, the recursive algorithm (n! = n * (n - 1)!) means that these errors are compounded once we get an overflow, meaning that, for argument values higher than 13, we start multiplying overflowed values, resulting in total garbage, and further destroying any patterns in the overflowed value. In particular, once a factorial is calculated as zero, all subsequent values will clearly be zero too.
