# Converting Binary To Decimal

Page 1 of 1

## 13 Replies - 32561 Views - Last Post: 30 May 2008 - 07:22 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=53348&amp;s=bdbb400c744358ee2c772f28ab2a6162&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

# Converting Binary To Decimal

Posted 29 May 2008 - 07:52 PM

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.

```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.

```  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
End Function

Public Function addStrs(ByRef A As Text.StringBuilder, ByRef B As Text.StringBuilder) As 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
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 - 07:54 PM

Is This A Good Question/Topic? 0

## Replies To: Converting Binary To Decimal

### #2 RodgerB

• D.I.C Lover

Reputation: 66
• Posts: 2,284
• Joined: 21-September 07

## Re: Converting Binary To Decimal

Posted 30 May 2008 - 01:10 AM

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).

Hope that helps.

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

## Re: Converting Binary To Decimal

Posted 30 May 2008 - 03:41 AM

Nope both fail when both overflow and crash when N>63.

The method used is similar to one they use but it doesn't overflow.

Im talking about really big numbers,

Example 1: 2^4096
Calculated in: 9ms (258x16bits, N=4128)
Decimalised in: 2590ms. (1234 Digits)

Example 2: 12345^1234

Calculation time: 6149ms (1050x16bits, N=16800)
Decimalised in: 175866 ms (5049 Digits)

### #4 baavgai

• Dreaming Coder

Reputation: 7327
• Posts: 15,237
• Joined: 16-October 07

## Re: Converting Binary To Decimal

Posted 30 May 2008 - 09:10 AM

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.

```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:
```Function GetDecStrForBits(ByVal bits As String) As String
Dim i As Integer, decStr As String = ""
For i = 0 To bits.Length - 1
If (bits(i) = "1") Then
End If
Next
Return decStr
End Function

```

Hope this helps.

### #5 baavgai

• Dreaming Coder

Reputation: 7327
• Posts: 15,237
• Joined: 16-October 07

## Re: Converting Binary To Decimal

Posted 30 May 2008 - 10:20 AM

Never mind, sometimes it's hard to let the puzzles go. Here's the whole thing.

```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
If (bits(i) = "1") Then
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

ElseIf a.Length < b.Length Then
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:

```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.

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

## Re: Converting Binary To Decimal

Posted 30 May 2008 - 11:39 AM

```  If Carry = 1 Then
tmp.Insert(0, CChar("1"))
End If
Return tmp.ToString

```

Tested your code baavgai , timings 2^4096 in 15005ms
123456^1234 in ms

This post has been edited by AdamSpeight2008: 30 May 2008 - 11:59 AM

### #7 baavgai

• Dreaming Coder

Reputation: 7327
• Posts: 15,237
• Joined: 16-October 07

## Re: Converting Binary To Decimal

Posted 30 May 2008 - 12:17 PM

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?

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

## Re: Converting Binary To Decimal

Posted 30 May 2008 - 12:17 PM

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.

```

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
If (bits(i) = "1") Then
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
ElseIf a.Length < b.Length Then
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

```

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

## Re: Converting Binary To Decimal

Posted 30 May 2008 - 12:59 PM

baavgai, on 30 May, 2008 - 12:17 PM, said:

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.

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

## Re: Converting Binary To Decimal

Posted 30 May 2008 - 06:11 PM

Done It.

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.

```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.
Dim BCD As New List(Of Byte)
Dim Binary As New List(Of UInt16)
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 - 06:32 PM

### #11 baavgai

• Dreaming Coder

Reputation: 7327
• Posts: 15,237
• Joined: 16-October 07

## Re: Converting Binary To Decimal

Posted 30 May 2008 - 06:34 PM

I was considering doing a BCD shift, but you beat me to it.

Excellent job.

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

## Re: Converting Binary To Decimal

Posted 30 May 2008 - 06:37 PM

Thank you.

### #13 kyrotomia

Reputation: 3
• Posts: 72
• Joined: 05-May 07

## Re: Converting Binary To Decimal

Posted 30 May 2008 - 07:13 PM

I feel like I'm asking a stupid question. But I am interested in knowing how did you measure your code "executing time"...

• MrCupOfT

Reputation: 2298
• Posts: 9,535
• Joined: 29-May 08

## Re: Converting Binary To Decimal

Posted 30 May 2008 - 07:22 PM

Dim myClock as New StopWatch
myClock.start
' Code to execute
myClock.stop
console.write(myClock.Milliseconds.toString)
myClock.Reset 'Set Clock back to Zero