2

Learn You a Haskell shows the factorial function:

Prelude> factorial n = product [1..n]

Prelude> factorial 50
30414093201713378043612608166064768844377641568960512000000000000

Looks like either an Int is larger than 32-bits or Haskell has a BigNumber-like type.

Running that "similar" function in Scala. 

scala> def factorial(n: Int) = List.range(1, n+1).foldLeft(1)(_*_)
factorial: (n: Int)Int

I can calculate a factorial that stays within Int.MaxValue (2 billion something)

scala> factorial(10)
res5: Int = 362880

Overflow occurs due to the result exceeding Int.MaxValue

scala> factorial(33)
res6: Int = -2147483648

But, why isn't it overflowing here?

scala> factorial(50)
res7: Int = 0

So, how's it work in Haskell? And, why does it result in 0 for Scala?

Kevin Meredith
  • 41,036
  • 63
  • 209
  • 384

3 Answers3

9

According to the documentation:

The standard instances of Integral are Integer (unbounded or mathematical integers, also known as "bignums") and Int (bounded, machine integers, with a range equivalent to at least 29-bit signed binary)

Wikibooks explains this:

"Integer" is an arbitrary precision type: it will hold any number no matter how big, up to the limit of your machine's memory…. This means you never have arithmetic overflows. On the other hand it also means your arithmetic is relatively slow. Lisp users may recognise the "bignum" type here.

In ghci: 

Prelude> factorial 50 :: Int
-3258495067890909184
Prelude> factorial 50 :: Integer
30414093201713378043612608166064768844377641568960512000000000000

So, with Int it actually overflows. Integer can hold any number without overflow limited by system's memory.

Sibi
  • 47,472
  • 16
  • 95
  • 163
7

There are (at least) two types for whole numbers in Haskell: Integer which can hold arbitrarily large numbers, but arithmetic is slower, and Int, with a machine dependent maximal value and faster arithmetic (see also this question: Haskell Int and Integer)

Haskell's default integer type is Integer, that's why there's no overflow in your haskell example. Scala's Int (32 bit signed) however can overflow and then wraps around into negative numbers.

This is the reason for odd results as in factorial(50)=0 (and factorial(51) = factorial(52) = ... = 0: Due to overflows, a temporary result in the multiplication is 0, thus all following factorials are 0 as well.

Example using decimal numbers: Let's assume that we are using a fixed width decimal representation with 3 places and only positive numbers (in reality, we would have 32 or 64 binary digits and Haskell and Scala both use signed numbers, but the basic concept stays the same):

  • factorial 1 = 001
  • factorial 2 = 002
  • ...
  • factorial 5 = 120
  • factorial 6 = 720
  • factorial 7 = 5040, BUT we can only store 3 digits, so this gets truncated to 040
  • factorial 8 = (factorial 7) * 8 = 040 * 8 = 320
  • factorial 9 = 320 * 9 = 2880 = 880
  • factorial 10 = 880 * 10 = 8800 = 800
  • factorial 11 = 800 * 11 = 8800 = 800
  • factorial 12 = 800 * 12 = 9600 = 600
  • ...
  • factorial 15 = 200 * 15 = 3000 = 000
  • factorial 16 = (factorial 15) * 16 = 000 * 16 = 000
  • ...

An example on my 64 bit box, using Haskell:

Prelude> factorial 65 :: Int  # largest nonzero factorial on my box
-9223372036854775808
Prelude> factorial 66 :: Int  # all following factorials are zero
0
Prelude> -9223372036854775808 * 66 :: Int  # because (factorial 65) * 66 = 0
0

Prelude> -9223372036854775808 * 66         # with arbitrary precision:
-608742554432415203328
Prelude> -608742554432415203328 / 2^64      # this happens to be a multiple of 2^64
-33.0

The same thing would happen with factorials in a fixed length base 10 representation: each factor that is a multiple of 10 introduces another 0 at the "right end of the number", so eventually, all digits of our imaginary fixed length base 10 integer are shifted out to the left.

With the internal binary representation used in Haskells or Scalas Int, the same happens for each even factor, so that at some point, all bits are 0.

Community
  • 1
  • 1
Jasper
  • 3,939
  • 1
  • 18
  • 35
  • 3
    Note that each even number in the product adds at least one 0 bit to the end of the binary result. Eventually, all the 1 bits are shifted left beyond the boundary of the word, so that only 0s remain. That is, it's not a coincidence that this happens (as could be implied by "this happens to be"): it would happen in any finite-width number fairly quickly. – amalloy Apr 05 '14 at 17:42
  • as I understand overflow, `val result = fact(LARGE_NUMBER)` will lead to: `result % Int.MaxValue`. In other words, a particular type can hold a max value. If you exceed that, then you roll over to the lower bound of the type. Why doesn't that happen in the `0` case? – Kevin Meredith Apr 07 '14 at 17:54
  • the `0` case is not special at all, you can think of it as `result % Int.MaxValue = 0`. See also updated answer. – Jasper Apr 07 '14 at 18:36
7

In addition to aforementioned reasons on Haskell Int and Integer machine dependent and arbitrary precision, the equivalent in Scala for Integer would be

def factorial(n: Int) = (BigInt(1) to BigInt(n)).product

where BigInt provides arbitrary precision and relies on java.math.BigInteger.

elm
  • 20,117
  • 14
  • 67
  • 113