Converting Binary To Decimal

How do you convert an N-bit binary number into dectimal, when N > 3

Page 1 of 1

13 Replies - 30698 Views - Last Post: 30 May 2008 - 07:22 PM Rate Topic: -----

#1 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • 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
		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 - 07:54 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Converting Binary To Decimal

#2 RodgerB  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 66
  • View blog
  • 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. :)
Was This Post Helpful? 0
  • +
  • -

#3 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • 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)
Was This Post Helpful? 0
  • +
  • -

#4 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 7008
  • View blog
  • Posts: 14,661
  • 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... :P

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
		decStr = addStrs(decStr, decStr)
		If (bits(i) = "1") Then
			decStr = addStrs(decStr, "1")
		End If
	Next
	Return decStr
End Function



Hope this helps.
Was This Post Helpful? 0
  • +
  • -

#5 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 7008
  • View blog
  • Posts: 14,661
  • 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. :P

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:

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. ;)
Was This Post Helpful? 0
  • +
  • -

#6 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon

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

Re: Converting Binary To Decimal

Posted 30 May 2008 - 11:39 AM

Correction to AddStrings

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



It helps to know your head from r's . :blush:

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

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

Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 7008
  • View blog
  • Posts: 14,661
  • 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?
Was This Post Helpful? 0
  • +
  • -

#8 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • 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
			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


Was This Post Helpful? 0
  • +
  • -

#9 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon

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

Re: Converting Binary To Decimal

Posted 30 May 2008 - 12:59 PM

View Postbaavgai, 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.
Was This Post Helpful? 0
  • +
  • -

#10 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon

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

Re: Converting Binary To Decimal

Posted 30 May 2008 - 06:11 PM

:bananaman: Done It. :bananaman:

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.
 ' 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 - 06:32 PM

Was This Post Helpful? 0
  • +
  • -

#11 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon


Reputation: 7008
  • View blog
  • Posts: 14,661
  • 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.
Was This Post Helpful? 0
  • +
  • -

#12 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon

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

Re: Converting Binary To Decimal

Posted 30 May 2008 - 06:37 PM

Thank you.
Was This Post Helpful? 0
  • +
  • -

#13 kyrotomia  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • 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"...
Was This Post Helpful? 0
  • +
  • -

#14 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon

Reputation: 2298
  • View blog
  • 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
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1