views:

620

answers:

5

Given Wikipedia's article on Radix Point, how would one calculate the binary equivalent of 10.1 or the hex equivalent of 17.17? For the former, what is the binary equivalent of a tenth? For the latter, the hex representation of 17/100?

I'm looking more for an algorithm than for solutions to just those two examples.

+2  A: 

The algorithm is quite simple, but in practice you can do a lot of tweaks both with lookup tables and logs to speed it up. But for the basic algorithm, you may try something like this:

shift=0;

while v>=base,  v=v/base, shift=shift+1;  

Next digit: 
if v<1.0 && shift==0, output the decimal point
else 
   D=floor(v)
   output D
   v=v-D
v=v*base
shift = shift-1
if (v==0) exit;
goto Next Digit

You may also put a test in there to stop printing after N digits for longer repeating decimals.

SPWorley
Wish I could tick two things. This deserves a tick as much as the one that got ticked.
boost
+1  A: 

The 'binary equivalent' of one tenth is one half, i.e instead of 1/10^1, it's 1/2^1.

Each digit represents a power of two. The digits behind the radix point are the same, it's just that they represent 1 over the power of two:

 8 4 2 1 . 1/2 1/4 1/8 1/16

So for 10.1, you obviously need an '8' and a '2' to make the 10 portion. 1/2 (0.5) is too much, 1/4 ( 0.25 ) is too much, 1/8 (0.125) is too much. We need 1/16 (0.0625), which will leave us with 0.0375. 1/32 is 0.03125, so we can take that too. So far we have:

 8 4 2 1 . 1/2 1/4 1/8 1/16 1/32
 1 0 1 0    0   0   0   1     1

With an error of 0.00625. 1/64 (0.015625) and 1/128 (0.0078125) are both too much, 1/256 (0.00390625) will work:

 8 4 2 1 . 1/2 1/4 1/8 1/16 1/32 1/64 1/128 1/256
 1 0 1 0    0   0   0   1     1    0   0     1

With an error of 0.00234375.

The .1 cannot be expressed exactly in binary ( just as 1/3 can't be expressed exactly in decimal ). Depending on where you put your radix, you eventually have to stop, probably round, and accept the error.

Chris Arguin
+3  A: 

A terminating number (a number which can be represented by a finite number of digits) n1 in base b1, may end up being a non-terminating number in a different base b2. Conversely, a non-terminating number in one base b1 may turn out to be a terminating number in base b2.

The number 0.110 when converted to binary is a non-terminating number, as is 0.1710 when converted to a hexadecimal number. But the terminating number 0.13 in base 3, when converted to base 10 is the non-terminating, repeating number 0.(3)10 (signifying that the number 3 repeats). Similarly, converting 0.110 to binary and 0.1710 to hexadecimal, one ends up with the non-terminating, repeating numbers 0.0(0011)2 and 0.2(B851E)16

Because of this, when converting such a number from one base to another, you may find yourself having to approximate the number instead of having a representation which is completely accurate.

Roshan
+6  A: 

To convert decimal 10.1 to binary, separate the integer and fractional parts and convert each separately.

To convert the integer part, use repeated integer division by 2, and then write the remainders in reverse order:

10/2 = 5 remainder 0

5/2 = 2 remainder 1

2/2 = 1 remainder 0

1/2 = 0 remainder 1

Answer: 1010

To convert the fractional part, use repeated multiplication by 2, subtracting off the integer part at each step. The integer parts, in order of generation, represent your binary number:

0.1 * 2 = 0.2

0.2 * 2 = 0.4

0.4 * 2 = 0.8

0.8 * 2 = 1.6

0.6 * 2 = 1.2

0.2 * 2 = 0.4

0.4 * 2 = 0.8

... (cycle repeats forever)

So decimal 0.1 is binary 0.000110011001100...

(For a more detailed explanation see routines dec2bin_i() and dec2bin_f() in my article http://www.exploringbinary.com/base-conversion-in-php-using-bcmath/ .)

For hexadecimal, use the same procedure, except with a divisor/multiplier of 16 instead of 2. Remainders and integer parts greater than 9 must be converted to hex digits directly: 10 becomes A, 11 becomes B, ... , 15 becomes F.

Rick Regan
Remember that you should have some sort of stopping mechanism in that algorithm, since some decimal numbers can not be represented exactly in binary. Which means the algorithm could run forever unless you have a stopping point =)
Svish
Yes, I was implying that when I said ``... (cycle repeats forever)'', plus the code in the article I linked to discusses that.
Rick Regan
A: 

Before I twiddle with this in the light of my GMP library, here's where I got to trying to make Rick Regan's PHP code generic for any base from 2 up to 36.

Function dec2base_f(ByVal ddecimal As Double, ByVal nBase As Long, ByVal dscale As Long) As String
    Const BASES = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" 'up to base 36
    Dim digitCount As Long
    Dim wholeNumber As Double
    Dim digit As String * 1
    digitCount = 0
    dscale = max(dscale, Len(CStr(ddecimal)) - Len("0."))
    Dim baseary_f As String
    baseary_f = "0."
    Do While ddecimal > 0 And digitCount < dscale
        ddecimal = ddecimal * nBase
        digit = Mid$(BASES, Fix(ddecimal) + 1)
        baseary_f = baseary_f & digit '"1"
        ddecimal = ddecimal - Fix(ddecimal)
        digitCount = digitCount + 1
    Loop
    dec2base_f = baseary_f
End Function

Function base2dec_f(ByVal baseary_f As String, nBase As Double) As Double
    Const BASES As String = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    Dim decimal_f As Double
    Dim i As Long
    Dim c As Long
    For i = Len(baseary_f) To Len("0.") + 1 Step -1
        c = InStr(BASES, Mid$(baseary_f, i, 1)) - 1
        decimal_f = decimal_f + c
        decimal_f = decimal_f / nBase
    Next
    base2dec_f = decimal_f
End Function

Debug.Print base2dec_f(dec2base_f(0.09, 2, 200), 2) --> 0.09
Debug.Print base2dec_f(dec2base_f(0.09, 8, 200), 8) --> 0.09
Debug.Print base2dec_f(dec2base_f(0.09, 16, 200), 16) --> 0.09
boost
My PHP code is based on BCMath, which is an arbitrary-precision, decimal-string based library. Your code is based on double-precision, floating-point binary. I'm not sure you're getting what you want by adapting my code in this way.
Rick Regan
I will be getting what I want once I stop using Doubles and start using GMP. The code above was more a proof of concept rather than production code. I've already got lots of stuff going with GMP, and now, thanks to you, I do stuff like =BASEPOWER( 16, 123, "-A" ), i.e. raise 0x123 to the negative A.
boost
I assume you're using GMP floating-point (type mpf_t)?From the GMP manual (http://gmplib.org/gmp-man-4.3.0.pdf), p. 48: ``The mantissa in stored in binary... One consequence of this is that decimal fractions like 0.1 cannot be represented exactly.''So, make sure to use enough precision to get the conversion accurate to the number of places you want, taking into account the bases being used (e.g., one base 32 digit is equal to five base 2 digits).
Rick Regan
eek, erk, hrm and all the other noises I make when someone points out something I've missed. Thanks for the warning.
boost