[RESOLVED] Going beyond the assignment

http://www.vbforums.com/showthread.p...89#post4243389

This thread got me working on a self-project.... Why can't I do this function with any number greater than 65535

vb.net Code:

Public Class Form1
 
    Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        TextBox1.Text = CStr(SumOfIntegers(CInt(TextBox1.Text)))
    End Sub
    Public Function SumOfIntegers(ByVal int As Integer) As Integer
        Dim nint As New Integer
        Dim sum As New Integer
        For i = 1 To int
            sum += i
        Next
        Return sum
    End Function
End Class

Arithmetic operation resulted in an overflow.

vb .net Code:

Public Function SumOfIntegers(ByVal int As Integer) As Integer
        Dim nint As New Integer
        Dim sum As New Integer
        If int > 65535 Then
            For i = 1 To 65535
                sum += i
            Next
            For i = 65536 To int
                sum += i
            Next
        Else
            For i = 1 To int
                sum += i
            Next
        End If
        Return sum
    End Function

This does not work either.

Because

Integer.MaxValue = 2147483647
SumOfIntegers(65535) = 2147450880

The difference between them is 32767 which is less than 65536 , so trying to add the next number in the sequence will exceed Integer.MaxValue and cause an Arithmetic Overflow.

If you want to go past 65535, use the Longs, Luke

Intrigues me that 65535 is 2^16 -1 while Integer.Maxvalue is 2^31 - 1.

EDIT : I should write that in binary:

2^16 - 1 = 1111111111111111
2^31 - 1 = 1111111111111111111111111111111

vb.net Code:

Public Function SumOfIntegers(ByVal int As Integer) As Long
        Dim nint As Long = int
        Dim sum As New Integer
        If int > 65535 Then
            For i = 1 To 65535
                sum += i
            Next
            For i As Long = 65536 To nint
                Dim nsum As Long = sum
                nsum += nint
            Next
        Else
            For i = 1 To int
                sum += i
            Next
        End If
        Return sum
    End Function

Okay, No error, but anything over 65535 still shows 2147450880

I dont know, but at the top of your code you have used integers. That might be it.

vb.net Code:

Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        TextBox1.Text = CStr(SumOfIntegers(CInt(TextBox1.Text)))
    End Sub
    Public Function SumOfIntegers(ByVal int As Integer) As Long
        Dim nint As Long = int
        Dim sum As New Integer
        If int > 65535 Then
            For i = 1 To 65535
                sum += i
            Next
            For i As Long = 65536 To nint
                Dim nsum As Long = sum
                nsum += nint
            Next
        Else
            For i = 1 To int
                sum += i
            Next
        End If
        Return sum
    End Function

here is the code of where I call it too. Its strange that it still won't go above the max integer, I changed the Function to produce a Long, the values for the numbers over 65535 have been changed to Long, it ends up as a String... I must figure this out.

You always return sum which peaks out at SumOfIntegers(65535)

This line

Code:

---

Dim nsum As Long = sum

---

should be outside the For loop as it keeps resetting the value of nsum. And shouldn't

Code:

---

nsum += nint

---

be

Code:

---

nsum += i

---

It's an interesting way to do it, but I meant to use your original code and change all Integers to Longs

vb.net Code:

Public Function SumOfLongs(ByVal lng As Long) As Long
    Dim sum As New Long
    For i = 1 To lng
        sum += i
    Next
    Return sum
End Function

vb.net Code:

Public Function SumOfIntegers(ByVal int As Integer) As Long
        Dim nint As Long = int
        Dim sum As New Integer
        Dim nsum As New Long
        If int > 65535 Then
            For i = 1 To 65535
                sum += i
            Next
            nsum = sum
            For i As Long = 65536 To nint
                nsum += i
            Next
            Return nsum
        Else
            For i = 1 To int
                sum += i
            Next
            Return sum
        End If
    End Function

This way makes it look more complex ;)
Works.


Turns out we have a problem though, I seem to not be able to go past this number: 9,223,372,036,854,775,807
How do I get past it?

vb.net Code:

Public Function SumOfIntegers(ByVal int As Integer) As Long
        nlong = TextBox1.Text
        Dim nint As Long = int
        Dim sum As New Integer
        Dim nsum As New Long
        If nlong > 9223372036854775807 Then
'Now what goes here.......
        Else
            If int > 65535 Then
                For i = 1 To 65535
                    sum += i
                Next
                nsum = sum
                For i As Long = 65536 To nint
                    nsum += i
                Next
                Return nsum
            Else
                For i = 1 To int
                    sum += i
                Next
                Return sum
            End If
        End If
    End Function

This is a tricky one, seeing as I am still only 8 months in to my VB .NET professionalism, I do not know how to continue with this.

Look into using BigInt. Don't expect impressive performance, though. The problem is that an Integer is four bytes, while a Long is eight bytes. There is an absolute cap on the largest integer that can be represented by those numbers of bits, and you are running up against it. The same problem will exist for every data type that has a fixed number of bytes. BigInt is a class, and it encapsulates a means to go as large as the memory available to your system, but that means comes at a cost. I suspect that what is happening is that BigInt is handling a collection of Integers, each of which is four bytes long, and expanding the collection as needed. Calculations that spill over the boundaries between integers in the collection require somewhat more complex operations. This will result in reduced performance for a BigInt relative to a Long or an Integer.

By the way, there is no reason to use New with Integer or Long.

lol :)

look into BigInts (too scarey for me) (EDIT: beaten by Shaggy - again)

btw, the bigest number you can pass in to the Longs method is 2^32 - 1 and the Long.MaxValue is 2^63 - 1

2^32 - 1 = 11111111111111111111111111111111
2^63 - 1 = 111111111111111111111111111111111111111111111111111111111111111

I'm liking the 1's

Okay, I am having trouble finding the BigInt class, I found a download on CodeProject for the C# one but I don't know how well I will be able to work with that. I did read that .NET 4.0 came with BigInteger, and I have .NET 4.0 but I can't seem to be able to use it, I can't even do Imports System.Numerics

Does anybody know of a location where I can obtain this BigInt class?

you need to add a reference to the assembly also. Project --> Add Reference --> .NET TAB and find System.Numerics.

vb.net Code:

Public Function SumOfIntegers(ByVal int As BigInteger) As BigInteger
        Dim bsum As BigInteger = 0
        For i As BigInteger = 1 To int
            bsum += i
        Next
        Return bsum
    End Function

So it has come to this. But, how do you convert a BigInteger into a String?

vb.net Code:

TextBox1.Text = SumOfIntegers(TextBox1.Text)

This does not work, neither does Cint around the textbox, or using Cstr around the Function

The MSDN on this doesn't really make sense to me..... http://msdn.microsoft.com/en-us/library/dd268301.aspx

vb.net Code:

TextBox1.Text = BigInteger.TryParse(TextBox1.Text, SumOfIntegers(TextBox1.Text))

This puts "True" into the textbox.

vb.net Code:

TextBox1.Text = BigInteger.Parse(SumOfIntegers(TextBox1.Text))

This says I cannot convert from BigInteger to String

try this:

vb.net Code:

Imports System.Numerics
 
Public Class Form1
 
    Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load
        MsgBox(SumOfIntegers(New BigInteger(65536)).ToString)
    End Sub
 
    Public Function SumOfIntegers(ByVal int As BigInteger) As BigInteger
        Dim bsum As BigInteger = 0
        For i As BigInteger = 1 To int
            bsum += i
        Next
        Return bsum
    End Function
 
End Class

to convert:

vb.net Code:

TextBox1.Text = SumOfIntegers(BigInteger.Parse(TextBox1.Text)).tostring

vb.net Code:

Imports System.Drawing
Imports System.Numerics
Public Class Form1
    Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        TextBox1.Text = SumOfIntegers(BigInteger.Parse(TextBox1.Text)).ToString
    End Sub
    Public Function SumOfIntegers(ByVal int As BigInteger) As BigInteger
        Dim bsum As BigInteger = 0
        For i As BigInteger = 1 To int
            bsum += i
        Next
        Return bsum
    End Function
End Class

Thank you, this works.... But, the performance when I use the value of 1200500200 to start the Function, is very poor. Much slower than I would have expected. Through using breakpoints I have discovered that this line is the slowing cause

vb.net Code:

bsum += i

Would a BGW make this maybe a little faster? I have an i7 clocking at 2.8ghz right now.

The TryParse method returns a Boolean:

False if the attempted parsing fails
True if the Parsing succeeds

If the Parsing succeeds, the parsed value is returned in the second parameter of the method.


So to "TryParse" a string into a big integer, first declare a BigInteger variable to hold the result of the parsing, and check the result for True or False and act accordingly.

vb.net Code:

Dim bi As BigInteger = BigInteger.Zero
 
If BigInteger.TryParse(TextBox1.Text, bi) Then
    TextBox1.Text = SumOfIntegers(bi).ToString
Else
    MessageBox.Show("Failed to parse string into BigInteger")
End If

Edited/Updated Post #16

Going to mess around with this to see if I can get it to do "125005005" in under 10 seconds.

I might even end up posting this in the "Code it Better" section.

Quote:

---

Originally Posted by thebuffalo

vb.net Code:

MsgBox(SumOfIntegers(New BigInteger(TextBox1.Text)).ToString)
 
TextBox1.Text = New BigInteger(SumOfIntegers(TextBox1.Text).ToString)
'Neither of these work.

Using this to attempt it and try to still have the function work with the textbox, it failed and gave me this error:
Overload resolution failed because no accessible 'New' can be called without a narrowing conversion:

vb.net Code:

Imports System.Drawing
Imports System.Numerics
Public Class Form1
    Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        TextBox1.Text = New BigInteger(SumOfIntegers(TextBox1.Text).ToString)
    End Sub
    Public Function SumOfIntegers(ByVal int As BigInteger) As BigInteger
        Dim bsum As BigInteger = 0
        For i As BigInteger = 1 To int
            bsum += i
        Next
        Return bsum
    End Function
End Class

Latest code attempt to surpass the limits of Long & Integers.

---

you're confusing yourself

a textbox.text is a string. New BigInteger doesn't accept a string parameter, so it tries to cast the string to an acceptable datatype
Inferrd's method from post #16 will work + my code from post #15 will work as long as textbox1 contains an integral number

vb.net Code:

Imports System.Drawing
Imports System.Numerics
Public Class Form1
    Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        TextBox1.Text = SumOfIntegers(BigInteger.Parse(TextBox1.Text)).ToString
    End Sub
    Public Function SumOfIntegers(ByVal int As BigInteger) As BigInteger
        Dim bsum As BigInteger = 0
        For i As BigInteger = 1 To int
            bsum += i
        Next
        Return bsum
    End Function
End Class

Final Code, and it works. Going to work on performance with this now.

Thanks Guys

Quote:

---

Originally Posted by thebuffalo

the performance when I use the value of 1200500200 to start the Function, is very poor. Much slower than I would have expected. Through using breakpoints I have discovered that this line is the slowing cause

vb.net Code:

bsum += i

Would a BGW make this maybe a little faster? I have an i7 clocking at 2.8ghz right now.

---

1.2 billion is a large loop + 1.2 billion mathematical operations are causing the delay

You might be able to improve performance by parallelizing the loop, since the order of these operations doesn't matter, but it is very unlikely to have much impact, and could be a disaster. For one thing, the addition operation in BigInteger would have to be designed to be thread safe, which would very likely mean locking prior to performing the addition, then unlocking. It may be that it was written to lock smaller parts, or use some kind of non-locking atomic operation, but I doubt it. More likely, either BigInteger is not written to be thread safe, or it was written to lock prior to the addition, and release the lock at the end of the addition. If it is the former case, then parallelizing the loop will probably result in wildly incorrect, and unrepeatable, results each time you run it, whereas if it is the latter case, then there will be little or negative performance benefit from parallelizing. The reason for the latter would be that all the threads would end up waiting their turn to get through the same, single, operation. Since there is nothing else happening in the loop, this would probably have the result that the addition would take exactly the same amount of time, but you'd also pay the cost of all the lock operations and context switching.

A backgroundworker would have at least the same problems as parallelization, unless you did something more clever. One thing that you could do with threading is to break the calculation into a series of sub-calculations. For instance, if you have a quad core system, you could take the total number and divide it by four. You would then spin up four threads. The first thread would perform a loop from 1 to Total/4, the second thread would perform a loop from (Total/4) + 1 to Total/2, the third thread would perform a loop from (total/2)+ 1 to 3 * (Total/4), and the fourth thread would perform a loop from (3*(Total/4)) + 1 to Total. Those four threads would be about as efficient as you could get, as each one would occupy a core completely. The true throughput would probably be coniderably less than four times what you are getting with single threading, though.

The problem that you are running into is that addition of two BigIntegers is no simple matter. It can involve memory acquisition, additions, switches, and more. The performance will not be anywhere close to being as simple as the line looks like.

Quote:

---

Originally Posted by .paul.

1.2 billion is a large loop + 1.2 billion mathematical operations are causing the delay

---

It's FAR more than 1.2 billion mathematical operations. The actual additions that are going on probably take up only a tiny fraction of the total time taken by the operation.