pascal triangle gives overflow for 13

Question

I wrote a code to output Pascal triangle in a multi-line textbook. The program works fine for inputs between 1 to 12 but gives an overflow error once a value of 13 is inputed.

Is there any modifications I can make to enable the program to accurately give outputs for 13 and higher?

Here is the code I used:

Public Class pascal_triangle

    Private Function factorial(ByVal k As Integer) As Integer
        If k = 0 Or k = 1 Then
            Return 1
        Else
            Return k * factorial(k - 1)
        End If
    End Function


    Private Sub BtnGen_Click(sender As Object, e As EventArgs) Handles BtnGen.Click
        Dim nCr As Integer
        Dim i, j, k As Integer
        Dim output As String

        output = ""

        j = Val(TxtColumn.Text)

        For k = 0 To j
            For i = 0 To k
                Dim fact, fact1, fact2 As Integer

                fact = factorial(k)
                fact1 = factorial(k - i)
                fact2 = factorial(i)
                nCr = fact / (fact1 * fact2)
                TxtOutput.Text += Str(nCr) & output
            Next
            TxtOutput.Text += vbCrLf
        Next
    End Sub

End Class

Answer 1

The overflow is because 13! is too big to fit in an integer.

The largest representable integer (32-bit signed) is

• 2147483647 (0x7FFFFFFF == 01111111 11111111 11111111 11111111b)

so :

 12!    =  479001600  
 MaxInt = 2147483647
 13!    = 6227020800    

If you want to use larger numbers than this you need to use a larger number type. The next larger types are Long (64-bit signed, max 9223372036854775807) or, for your purposes, ULong (unsigned 64-bit, since you don't need negative numbers, which is twice that at 18446744073709551615).

This will let you calculate up to20!, which is 2432902008176640000. For numbers larger than this you will need to look into using either BigInteger or other dedicated libraries that allow for holding and calculating arbitrarily large numbers.

Alternatively, you can look into other methods of computing an arbitrary row without using factorials.