Decimal to Binary - Optimising

[x-ice]

How can i optimise (or just make it better) this code?

Option Explicit On
Option Strict On
 
Imports System.Math
 
Public Class clsNumConv
    Public Function Dec2Bin(ByVal DecNum As Int32, ByVal ShowDecNum As Boolean) As String
        Dim DivNum As Int32
        'Establish how many divisions will be done, +1 for number rounding
        DivNum = CInt(Log(DecNum) / (Log(2)) + 1)
        'Create array with number of columns needed according to 'DivNum'
        Dim BinNums(DivNum, 2) As Int16
        'Assign 'DecNum' to columns 1, row 0 of array
        BinNums(0, 1) = CShort(DecNum)
        Dim intRowNum As Int32 = 1 'Divisions loop counter
        Dim RevBinNum As String
        'Calculate divisions
        For intRowNum = 1 To UBound(BinNums) 'To highest subscript of array
            'Divide previous value by 2
            BinNums(intRowNum, 1) = CShort(Math.Floor(BinNums(intRowNum - 1, 1) / 2))
            'Calculate modulus
            BinNums(intRowNum, 2) = CShort(BinNums(intRowNum - 1, 1) Mod 2)
            'Make binary number string
            RevBinNum &= CStr(BinNums(intRowNum, 2))
        Next
        Dim FinalBinNum As String
        'Assign string to 'strBin'" (reverse the string, as the binary number is backwards)
        FinalBinNum = StrReverse(RevBinNum)
        'Remove leading zeros
        FinalBinNum = FinalBinNum.TrimStart("0"c)
        'Check "ShowDecNum" to establish whether or not to show original number
        If ShowDecNum = True Then
            'Output binary number, along with original decimal number
            Return DecNum & "^10" & " = " & FinalBinNum & "^2"
        Else
            'Output binary number
            Return FinalBinNum & "^2"
        End If
    End Function
End Class

[penagate]

I don't know about .NET... but if you want any ideas check out my "Dumpbits" function in codebank, which does binary output of numbers and strings. Link in my sig

[x-ice]

I don't know about .NET... but if you want any ideas check out my "Dumpbits" function in codebank, which does binary output of numbers and strings. Link in my sig

Umm, you seem to do it totally different to me.

[penagate]

Indeed... I'm not sure how adaptable my function is to .NET but the concept is there. Maybe you might be able to optimise yours based on mine

[x-ice]

Indeed... I'm not sure how adaptable my function is to .NET but the concept is there. Maybe you might be able to optimise yours based on mine

If you know anything about vb.net, does my error handling look like it is in the correct place?

[penagate]

I don't think you need any error handling at all actually.

[x-ice]

I don't think you need any error handling at all actually.

Yeh, looking at it now, its kind of error prove.

I was wondering if it would make much difference if i decreased the size (changed it to int16 perhaps) of the array, because i dont need all the space provided by int32. Will this small change make the function faster or save memory?

[Merri]

How much faster do you need? To optimize, you need to make the maths easier to use and also get rid of most of the string handling and use a byte array instead (though I don't know speed stuff on VB.NET).

One thing would be to get rid of ^. It is very slow to call.

[x-ice]

How much faster do you need? To optimize, you need to make the maths easier to use and also get rid of most of the string handling and use a byte array instead (though I don't know speed stuff on VB.NET).

One thing would be to get rid of ^. It is very slow to call.

I'm not using ^ as a mathematical operator, i'm using it in a string, just for display purposes (see image for example). How can i make the maths easier to use? I cant get rid of the string handling stuff, i need it.

I have changed the array to a byte array, but when i enter any number above 255 i get an overflow. This is a problem because i want the user to be able to convert any number to binary.

p.s. i dont need it to be faster, its very fast already.

[Merri]

Might be, they've probably improved the string handling in VB.NET a whole lot. I confused the ^ operator from penagate's code. Anyways, here is a fast VB6 alternative if you're interested to see an alternative method (commented code so you should be able to follow along):

Option Explicit
 
Public Function LongToBin(ByVal Value As Long, Optional ByVal Bits As Byte = 32) As String
    Static tmpArr() As Byte
    Dim A As Long, B As Long, C As Long
    ' wanted no bits, return nothing
    If Bits = 0 Then Exit Function
    ' can return only 32 bits
    If Bits > 32 Then Bits = 32
    ' count where we are
    A = Bits + Bits
    ' reserve enough memory (VB strings are Unicode/BSTR)
    ReDim Preserve tmpArr(A - 1)
    ' see if we need upper byte at all...
    If Bits = 32 Then
        ' highest bit can not be active if value is zero or above
        If Value >= 0 Then
            tmpArr(0) = 48
        Else
            tmpArr(0) = 49
        End If
        ' always the same...
        C = 2
        B = &H40000000
    Else
        ' starting position in the byte array
        C = 0
        ' with hex values we set the upper most bit position
        Select Case Bits
            Case 31
                B = &H40000000
            Case 30
                B = &H20000000
            Case 29
                B = &H10000000
            Case 28
                B = &H8000000
            Case 27
                B = &H4000000
            Case 26
                B = &H2000000
            Case 25
                B = &H1000000
            Case 24
                B = &H800000
            Case 23
                B = &H400000
            Case 22
                B = &H200000
            Case 21
                B = &H100000
            Case 20
                B = &H80000
            Case 19
                B = &H40000
            Case 18
                B = &H20000
            Case 17
                B = &H10000
            Case 16
                B = &H8000
            Case 15
                B = &H4000
            Case 14
                B = &H2000
            Case 13
                B = &H1000
            Case 12
                B = &H800
            Case 11
                B = &H400
            Case 10
                B = &H200
            Case 9
                B = &H100
            Case 8
                B = &H80
            Case 7
                B = &H40
            Case 6
                B = &H20
            Case 5
                B = &H10
            Case 4
                B = &H8
            Case 3
                B = &H4
            Case 2
                B = &H2
            Case 1
                B = &H1
        End Select
    End If
    ' here all the work is done!
    Do
        ' check if the bit is active and set character to be
        ' 48 = "0" or 49 = "1" (And limits to the active byte only)
        tmpArr(C) = ((Value And B) \ B) Or 48
        ' check if we need to exit
        If B = 1 Then Exit Do
        ' to the next character in the array...
        C = C + 2
        ' to the next bit
        B = B \ 2
    Loop
    ' convert byte array to string and return the value
    LongToBin = CStr(tmpArr)
End Function

[x-ice]

Ok thx, instead of changing my whole code i think i'll stick with an integer array.

[jmcilhinney]

You'd need to add a bit to get the display you want but here's the most succinct conversion routine I think there is:

Public Function Dec2Bin(ByVal decNum As Integer) As String
        Dim binNum As String = String.Empty
 
        Do
            binNum = (decNum Mod 2).ToString() & binNum
            decNum = decNum \ 2
        Loop While decNum > 0
 
        Return binNum
    End Function

Edit:
This for non-negative integers only. It would need a bit of extra work for negatives, either using absolute values or some two's complement calcs.

[wossname]

Following JMC's lead I thought it would be fun to do it in C#.

The code is longer but its actually about 5 times faster. No concatenation, no floating point operations. I have used uint's instead of int32's because there is no requirement for converting negative numbers and the largest number containable is twice as large.

I know its in C# but that's the idea, C# lets you use pointers and unmanaged arrays and stuf like that. I just benchmarked this and it runs 1,000,000 (1 million) times in an average time of 0.66 seconds on my old, slow P4 1.8ghz PC.

Whoooooosh! I can't get it to go any faster at the moment, if anyone knows a quicker way then let me know.

public static unsafe string ToBinary(uint val)
{
    sbyte* bin = stackalloc sbyte[32]; //32 bytes
    sbyte* index = bin; //duplicate the array pointer and use this as the iterator
    sbyte* stop = bin + 32; //stop after 32 bytes in the array

    uint mask = 0x80000000; //bit mask

    do
    {
        if((val & mask) != 0)
            *index =  (sbyte)0x31; 
        else
            *index =  (sbyte)0x30; 

        mask >>= 1;
    } while(++index != stop); //let the index catch up the buffer one and then stop

    index = bin; //reset pointer
    for(mask = 0; mask < 32 ; mask++)
        if(*(index++) == 0x31)
            break;

    return new string(bin, (int)mask, (int)(32 - mask));
} 

[yrwyddfa]

Yeah the first thing I noticed about Wossy's code is that he straight away went for stack allocations.

The standard VB6 code uses two heap allocations just to set up the array. You should probably use SafeArrayCreateVectorEx to reduce this to just one heap allocation (heap allocations are expensive)

There are some (advanced) techniques to get VB to allocate safe array memory on the stack but I won't go into them here (unless you really really want me to)

[wossname]

I'll just mention here that these samples of code are exactly equivalent in speed terms...

1.

        if((val & mask) != 0) 
            *index =  (sbyte)0x31; 
        else 
            *index =  (sbyte)0x30;

2.

        *index = (val & mask) != 0 ? (sbyte)0x31 : (sbyte)0x30;

I used the first because its easier to read but otherwise the performance is identical and I think they probably compile to the same IL code anyway.

I mention this because of the common misconception (stemming from VB6) that inline ?: operators are slower than if() else blocks. In C# this is not true, as demonstrated above, but in VB6 an IIf() was substancially slower than an if...end if block.

Just FYI

[yrwyddfa]

I mention this because of the common misconception (stemming from VB6) that inline ?: operators are slower than if() else blocks. In C# this is not true, as demonstrated above, but in VB6 an IIf() was substancially slower than an if...end if block.

In VB6 the IIF function is most definately slower than IF, ELSE blocks because VB processes both conclusions (the true, and the false one) and then returns the one it should (this is also a cause of some really weird errors) You should avoid the IIF function if you are using VB6. in C/C++/C# it works, as you say, just fine.

[penagate]

I think I am right in saying, in C# the ?: operator is straight logical operation which expands to the If/Elseif, whereas VB6's IIf() function is a double expression evaluation, and a function on top of all that.

[penagate]

I see we agree on that point

[yrwyddfa]

Of course

[wossname]

Natch.