Join 150,099 VB.NET Programmers for FREE! Get instant access to thousands of VB.NET experts, tutorials, code snippets, and more! There are 1,870 people online right now. Registration is fast and FREE... Join Now!
How does one convert a N-bit binary number into decimal string representation? When N>32?
Problem
I have an array of UInt16 each containing a 16-bit section of the N-bit binary number. ie a(0) = bit 0 to bit 15 b(1) = bit 16 to bit 31 b(2) = bit 32 to bit 47 b(3) = bit 48 to bit 64 etc
What I would like is a Function similiar to the one below.
CODE
Public Function Convert_To_Decimal(byref ArrayOf16BitSections() as UInt16) as String ' code to perform conversion. end Function
This is the code have devised, but its slow.
CODE
Const C_0 As Char = CChar("0") Const C_1 As Char = CChar("1") Const C_2 As Char = CChar("2") Const C_3 As Char = CChar("3") Const C_4 As Char = CChar("4") Const C_5 As Char = CChar("5") Const C_6 As Char = CChar("6") Const C_7 As Char = CChar("7") Const C_8 As Char = CChar("8") Const C_9 As Char = CChar("9")
Dim Mod10(99) As Integer Dim Div10(99) As Integer Dim mCharsA() As Char = _ {CChar("0"), CChar("2"), CChar("4"), CChar("6"), CChar("8"), CChar("0"), CChar("2"), CChar("4"), CChar("6"), CChar("8")} Dim mCharsB() As Char = _ {CChar("1"), CChar("3"), CChar("5"), CChar("7"), CChar("9"), CChar("1"), CChar("3"), CChar("5"), CChar("7"), CChar("9")}
Public Sub Initialise() For i As Integer = 0 To 99 Mod10(i) = i Mod 10 Div10(i) = i \ 10 Next End Sub
Public Shadows Function Convert_To_Decimal(mDigits() as uint16) As String
Initialise dim ToString as string="" Dim pwr As New Text.StringBuilder pwr.Append("1") Dim value As New Text.StringBuilder : value.Append("0") Dim hw As Integer = 0 While hw <= mDigits.Count - 1 If (mDigits(hw) And &H1) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H2) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H4) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H8) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H10) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H20) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H40) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H80) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H100) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H200) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H400) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H800) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H1000) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H2000) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H4000) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) If (mDigits(hw) And &H8000) > 0 Then value = addStrs(value, pwr) pwr = TwiceString2(pwr) hw += 1 End While Return ToString End Function
Public Function addStrs(ByRef A As Text.StringBuilder, ByRef B As Text.StringBuilder) As Text.StringBuilder addStrs = New Text.StringBuilder If A.Length > B.Length Then B.Insert(0, "0", A.Length - B.Length) ElseIf A.Length < B.Length Then A.Insert(0, "0", B.Length - A.Length) End If
Dim Tally As Integer = 0 Dim Carry As Integer = 0 Dim av As Integer = 0 Dim bv As Integer = 0 Dim i As Integer = A.Length While i > 0 i -= 1 av = Asc(A(i)) - Asc(C_0) bv = Asc(B(i)) - Asc(C_0) 'CInt(Val(CStr(B(i)))) Tally = av + bv + Carry Carry = Div10(Tally) ' \ 10 addStrs.Insert(0, Mod10(Tally).ToString) End While If Carry = 1 Then addStrs.Append(CChar("1"), 0) End Function
Public Function TwiceString2(ByRef n As Text.StringBuilder) As Text.StringBuilder TwiceString2 = New Text.StringBuilder(n.Length + 1) Dim carry As Integer = 0 Dim i As Integer = n.Length While i > 0 i -= 1 If carry = 0 Then Select Case n(i) Case Is <= C_4 TwiceString2.Insert(0, mCharsA(Asc(n(i)) - Asc(C_0))) : carry = 0 Case Else TwiceString2.Insert(0, mCharsA(Asc(n(i)) - Asc(C_0))) : carry = 1 End Select Else Select Case n(i) Case Is <= C_4 TwiceString2.Insert(0, mCharsB(Asc(n(i)) - Asc(C_0))) : carry = 0 Case Else TwiceString2.Insert(0, mCharsB(Asc(n(i)) - Asc(C_0))) : carry = 1 End Select End If End While If carry = 1 Then TwiceString2.Insert(0, "1") End Function
Note: Uint16 are 32bits wide but the lower 16bits are only initialised at this stage. (Else where in the project are used.)
My thoughts about speeding it up are: 1) Convert for item of the the array to BCD 2) Convert that to an ASCII string.
Any and all help or suggestions are welcome and appreciated.
This post has been edited by AdamSpeight2008: 29 May, 2008 - 06:54 PM
A snippet has been made in the Visual Basic section to target this very problem (it isn't .NET compliant, but should serve some sort of educative purpose) (click).
If that was of no use to you, you may want to check this out (click).
This one is fun. Unfortunately, I have to get back to work...
For translating your numbers to bits in a string, this might be faster.
CODE
Function BitsForDec(ByVal n As UInt16) As String Dim i As Integer, bits As String = "" For i = 15 To 0 Step -1 bits += IIf((n And 2 ^ i) > 0, "1", "0") Next Return bits End Function
Function BitsForDec(ByVal digits() As UInt16) As String Dim i As Integer, bits As String = "" For i = digits.Length - 1 To 0 Step -1 bits += BitsForDec(digits(i)) Next Return bits End Function
I couldn't get your addStrs to work. It if really does work, the following code should get what you're looking for:
CODE
Function GetDecStrForBits(ByVal bits As String) As String Dim i As Integer, decStr As String = "" For i = 0 To bits.Length - 1 decStr = addStrs(decStr, decStr) If (bits(i) = "1") Then decStr = addStrs(decStr, "1") End If Next Return decStr End Function
Never mind, sometimes it's hard to let the puzzles go. Here's the whole thing.
CODE
Function BitsForDec(ByVal n As UInt16) As String Dim i As Integer, bits As String = "" For i = 15 To 0 Step -1 bits += IIf((n And 2 ^ i) > 0, "1", "0") Next Return bits End Function
Function BitsForDec(ByVal digits() As UInt16) As String Dim i As Integer, bits As String = "" For i = digits.Length - 1 To 0 Step -1 bits += BitsForDec(digits(i)) Next Return bits End Function
Function GetDecStrForBits(ByVal bits As String) As String Dim i As Integer, decStr As String = "" For i = 0 To bits.Length - 1 decStr = AddStrings(decStr, decStr) If (bits(i) = "1") Then decStr = AddStrings(decStr, "1") End If Next Return decStr End Function
Public Function AddStrings(ByVal a As String, ByVal b As String) As String Dim padLen As Integer = a.Length - b.Length
If padLen > 0 Then b = "".PadLeft(padLen, "0") & b ElseIf a.Length < b.Length Then a = "".PadLeft(-1 * padLen, "0") & a End If
Dim sb As String = "" Dim i As Integer, tally As Integer, carry As Integer = 0 For i = a.Length - 1 To 0 Step -1 tally = Integer.Parse(a(i)) + Integer.Parse(b(i)) + carry carry = Math.Floor(tally / 10.0) sb = (tally Mod 10).ToString() & sb Next If carry <> 0 Then sb = carry & sb Return sb End Function
Function GetDecStrForArray(ByVal digits() As UInt16) As String Return GetDecStrForBits(BitsForDec(digits)) End Function
I think there's a bug in your carry logic at the end or addStr. Here's some test code I wrote, you may wish to try it on yours:
CODE
Sub TestAddStr(ByVal a As UInteger, ByVal b As UInteger) Dim c As UInteger = (a + b) Dim s As String = AddStrings(a.ToString(), b.ToString()) If (c.ToString() <> s) Then Debug.WriteLine(a & "+" & b & " = " & c & ":" & s) End If End Sub
Dim rnd As New Random(), i As Integer : For i = 0 To 200 : TestAddStr(rnd.Next(), rnd.Next()) : Next
I don't know if it any faster, but I think it's shorter.
There are doubtless many places for improvement. But in the end you're using VB.NET. Have you considered something a little more robust, if only for the heavy lifting part?
Modifying your slightly Baavgai, reduces the times to
2^4096 in 7811ms 12345^1234 in 302015ms (It finished! )
About twice as fast. (Appending strings with A_String &= Other_String are really slow.) Thats why I sometime use the Text.StringBuilder class.
Also Mod and / are slow.
Note on following code. Call Initialise first to build the divide and mod lookup tables.
CODE
Public Mod10(99) As Integer Public Div10(99) As Integer
Public Sub Initialise() For i As Integer = 0 To 99 Mod10(i) = i Mod 10 Div10(i) = i \ 10 Next End Sub
Function BitsForDec(ByVal n As UInt16) As Text.StringBuilder BitsForDec = New Text.StringBuilder Dim i As Integer ' Dim bits As String = "" For i = 15 To 0 Step -1 If (n And CLng(2 ^ i)) > 0 Then BitsForDec.Append("1") Else BitsForDec.Append("0") End If Next ' Return bits End Function
Function BitsForDec(ByVal digits() As UInt16) As Text.StringBuilder Dim i As Integer Dim bits As New Text.StringBuilder 'String = "" For i = digits.Length - 1 To 0 Step -1 bits.Append(BitsForDec(digits(i))) Next Return bits End Function
Function GetDecStrForBits(ByVal bits As String) As String Dim i As Integer, decStr As String = ""
For i = 0 To bits.Length - 1 decStr = AddStrings(decStr, decStr) If (bits(i) = "1") Then decStr = AddStrings(decStr, "1") End If Next Return decStr End Function
Public Function AddStrings(ByVal a As String, ByVal b As String) As String Dim padLen As Integer = a.Length - b.Length If padLen > 0 Then b = "".PadLeft(padLen, CChar("0")) & b ElseIf a.Length < b.Length Then a = "".PadLeft(-1 * padLen, CChar("0")) & a End If Dim sb As New Text.StringBuilder Dim i As Integer, tally As Integer, carry As Integer = 0 For i = a.Length - 1 To 0 Step -1 tally = Integer.Parse(a(i)) + Integer.Parse(b(i)) + carry carry = Div10(tally) sb.Insert(0, Mod10(tally).ToString) Next If carry <> 0 Then sb.Insert(0, carry.ToString) ' & sb Return sb.ToString End Function
Function GetDecStrForArray(ByVal digits() As UInt16) As String Return GetDecStrForBits(BitsForDec(digits).ToString) End Function
There are doubtless many places for improvement. But in the end you're using VB.NET. Have you considered something a little more robust, if only for the heavy lifting part?
In my opinion is that improving the algorithms is better way the go, then language.
Would like to learn C, C++ , C# but not found a decent book with examples that work in the express versions. Any recommendations?
Modified my code, now times are: 2^4096 in 375ms 12345^1234 in 8598ms
If i could get my implemention of the Double Dabble algorithm to work.
Timings are now. 2^4096 in 125ms 12345^1234 in 6705ms
Achieved my aim of a single function, bonus that it self contained. I think it's the best peice of code I ever written.
CODE
Public Function Convert_To_DecimalString(ByRef RawBinary As List(Of UInt16)) As String ' Convert the contents of RawBinary to a Deciaml String using the "Double Dabble" method. ' Engineered by AdamSpeight2008 Dim BCD As New List(Of Byte) BCD.Add(0) Dim Binary As New List(Of UInt16) Binary.AddRange(RawBinary.ToArray) Binary.Reverse Dim carryIn As Byte = 0 Dim CarryOut As Byte = 0 Dim a As Integer = Binary.Count << 4 Dim i As Integer = 0 While a > 0 carryIn = 0 i = Binary.Count While i > 0 i -= 1 CarryOut = (Binary(i) And &H8000) >> 15 Binary(i)=(Binary(i) <<1) + CarryIn carryIn = CarryOut End While i = BCD.Count While i > 0 i -= 1 ' Dabble If BCD(i) >= 5 Then BCD(i) = CByte(BCD(i) + 3) CarryOut = (BCD(i) And &H8) >> 3 BCD(i) = ((BCD(i) << 1) And &HF) + carryIn carryIn = CarryOut End While If carryIn = 1 Then BCD.Insert(0, carryIn) a -= 1 End While ' Convert BCD to ASCII string Dim s As New Text.StringBuilder i = 0 While i < BCD.Count s.Append(BCD(i).ToString) i += 1 End While Return s.ToString End Function
This post has been edited by AdamSpeight2008: 30 May, 2008 - 05:32 PM
ms
)
Done It. 
| 
