CODEWITHSUNDEEP
vb.netbigintegerpascals-triangle
High Zedd
High Zedd

Reputation: 55

pascal triangle gives overflow for 13

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

Upvotes: 0

Views: 160

Answers (2)

Blackwood
Blackwood

Reputation: 4534

Your main problem is that you are using Integer which is too small to hold the factorial of 13. Change your Factorial function to return Long. It would also be a good idea to turn Option Strict On and make nCr a Double.

Private Function factorial(ByVal k As Integer) As Long
    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 Double
    Dim i, j, k As Integer
    Integer.TryParse(TxtColumn.Text, j)
    For k = 0 To j
        For i = 0 To k
            Dim fact, fact1, fact2 As Long
            fact = factorial(k)
            fact1 = factorial(k - i)
            fact2 = factorial(i)
            nCr = fact / (fact1 * fact2)
            TxtOutput.Text += nCr.ToString & " "
        Next
        TxtOutput.Text += vbCrLf
    Next
End Sub

Upvotes: 1

J...
J...

Reputation: 31403

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.

Upvotes: 1

Related Questions