How do I convert a very long binary number to decimal?

Question

I have a binary number represented as 11.1111111 (the . being analogous to a decimal point). There are 2 bits before the point, and 1024 bits after the point. It was an exercise in calculating e to a high level of precision, but now I am stuck as to how to convert it to decimal. Just in case you guys want to know the number, here it is:

10.1011011111100001010100010110001010001010111011010010101001101010101111110111000101011000100000001001110011110100111100111100011101100010111001110001011000001111001110001011010011011010010101101010011110000100110110010000010001010001100100001100111111101111001100100100111001110111001110001001001001101100111110111110010111110100101111111000110110001101100011000011000111010111011000111101101000000110110010000000101010111011000100011000010111101011010011110111110001111011010101110101011111110101100101011000010010010000110011111101010001111101011111000001100110111011010000100001010110001101100101010101010011110111101101000110101111001110110101010101110001001101011110011111110101011111001001001101011001100001001111000011000111000011100000111001101000101101110111111000101010011010001001110110101111001111101111111010000111001000011101111100010101100010100001001101101010110111100111001101010011000010101100110010100100111101001000001110100111100101111010101111000000101010110001100000101011001100100100111110110011101011

How do I convert this to 2.718.... (there should be about 309 digits after the decimal point) I can't simply multiply each bit by 2^x because after a while, the number 2^x will = 0, even when using a double precision float. I'm using Visual Basic, so I'm not sure there are any larger variables exist.

[Edit by Spektre]

Just have run your string with my code (based on the link in my comment) and the result is:

e(bigdecimal)=2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642742746639193200305992181741359662904357290033429526059563073813232862794349076323382988075319525101901157383418793070215408914993488416750924476146066808226480016847741185374234544243710753907774499206955170189257927265177296267786175561825444670874889747782175809270565601486538810885558129926100522647929865142359038501319247028975364903531383896590857864585070203793060262761378008328322397393650711101939331201
e      (text)=2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642742746639193200305992181741359662904357290033429526059563073813232862794349076323382988075319525101901157383418793070215408914993488416750924476146066808226480016847741185374234544243710753907774499206955170189
e (reference)=2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334295260595630738132328627943490763233829880753195251019011573834187930702154089149934884167509244761460668082264800168477411853742345442437107539077744992069551702761838606261331384583000752044933826560297606737113200709328709127443747047230696977209310141692836819025515108657463772111252389784425056953696770785449969967946864454905987931636889230098793127736178215424999229576351482208269895193668033182528869398496465105820939239829488793320362509443117301238197068416140397019837679320683282376464804295311802328782509819455815301756717361332069811250996181881593041690351598888519345807273866738589422879228499892086805825749279610484198444363463244968487560233624827041978623209002160990235304369941849146314093431738143640546253152096183690888707016768396424378140592714563549061303107208510383750510115747704171898610687396965521267154688957035035402123407849819334321068170121005627880235193033224745015853904730419957777093503660416997329725088687696640355570716226844716256079882651787134195124665201030592123667719432527867539855894489697096409754591856956380236370162112047742722836489613422516445078182442352948636372141740238893441247963574370263755294448337998016125492278509257782562092622648326277933386566481627725164019105900491644998289315056604725802778631864155195653244258698294695930801915298721172556347546396447910145904090586298496791287406870504895858671747985466775757320568128845920541334053922000113786300945560688166740016984205580403363795376452030402432256613527836951177883863874439662532249850654995886234281899707733276171783928034946501434558897071942586398772754710962953741521115136835062752602326484728703920764310059584116612054529703023647254929666938115137322753645098889031360205724817658511806303644281231496550704751025446501172721155519486685080036853228183152196003735625279449515828418829478761085263981395599006737648292244375287184624578036192981971399147564488262603903381441823262515097482798777996437308997038886778227138360577297882412561190717663946507063304527954661855096666185664709711344474016070462621568071748187784437143698821855967095910259686200235371858874856965220005031173439207321139080329363447972735595527734907178379342163701205005451326383544000186323991490705479778056697853358048966906295119432473099587655236812859041383241160722602998330535370876138939639177957454016137223618789365260538155841587186925538606164779834025435128

The first is converted from text to my arbnum data-type and then converted back to text, middle is pure text to text conversion (like in the link with conversion to hex prior to that) and last is reference e

Here the hex string of your binary string:

e (hex)      =2.B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF324E7738926CFBE5F4BF8D8D8C31D763DA06C80ABB1185EB4F7C7B5757F5958490CFD47D7C19BB42158D9554F7B46BCED55C4D79FD5F24D6613C31C3839A2DDF8A9A276BCFBFA1C877C56284DAB79CD4C2B3293D20E9E5EAF02AC60ACC93ECEBh

I truncated down do decimal nibble sizes so there may be left 1,2 or 3 bits unprocessed at the end ...

Answer 1

1. convert your binary string to hex

   the integer part is easy "10." -> "2." the fractional part is also easy:

   10.1011011111100001010100010110 bin
   10.1011 0111 1110 0001 0101 0001 0110 bin
    2.B    7    E    1    5    1    6    hex
   

   as you can see each nibel integer value is also the hex digit 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F Here some C++ code:

   int i,j,l; char *t16="0123456789ABCDEF";
   AnsiString s0="10.your binary number",s1="2.";
   for (i=4,l=s0.Length();i<=l;)
       {
       j=0;
       if ((i<=l)&&(s0[i]=='1')) j+=8; i++;
       if ((i<=l)&&(s0[i]=='1')) j+=4; i++;
       if ((i<=l)&&(s0[i]=='1')) j+=2; i++;
       if ((i<=l)&&(s0[i]=='1')) j+=1; i++;
       s1+=char(t16[j]);
       } // here s1 holds the hex string
   

   this can be significantly speed-up by preallocationg the resulting s1 size

2. run hex to dec string conversion

   AnsiString str_hex2dec(const AnsiString &hex)
       {
       char c;
       AnsiString dec="",s;
       int i,j,l,ll,cy,val;
       int  i0,i1,i2,i3,sig;
       sig=+1; l=hex.Length();
       if (l) { c=hex[l]; if (c=='h') l--; if (c=='H') l--; }
       i0=0; i1=l; i2=0; i3=l;
       for (i=1;i<=l;i++)      // scan for parts of number
           {
           char c=hex[i];
           if (c=='-') sig=-sig;
           if ((c=='.')||(c==',')) i1=i-1;
           if ((c>='0')&&(c<='9')) { if (!i0) i0=i; if ((!i2)&&(i>i1)) i2=i; }
           if ((c>='A')&&(c<='F')) { if (!i0) i0=i; if ((!i2)&&(i>i1)) i2=i; }
           if ((c>='a')&&(c<='f')) { if (!i0) i0=i; if ((!i2)&&(i>i1)) i2=i; }
           }
   
       l=0; s=""; if (i0) for (i=i0;i<=i1;i++)
           {
           c=hex[i];
                if ((c>='0')&&(c<='9')) c-='0';
           else if ((c>='A')&&(c<='F')) c-='A'-10;
           else if ((c>='a')&&(c<='f')) c-='A'-10;
           for (cy=c,j=1;j<=l;j++)
               {
               val=(s[j]<<4)+cy;
               s[j]=val%10;
               cy  =val/10;
               }
           while (cy>0)
               {
               l++;
               s+=char(cy%10);
               cy/=10;
               }
           }
       if (s!="")
           {
           for (j=1;j<=l;j++) { c=s[j]; if (c<10) c+='0'; else c+='A'-10; s[j]=c; }
           for (i=l,j=1;j<i;j++,i--) { c=s[i]; s[i]=s[j]; s[j]=c; }
           dec+=s;
           }
       if (dec=="") dec="0";
       if (sig<0) dec="-"+dec;
   
       if (i2)
           {
           dec+='.';
           s=hex.SubString(i2,i3-i2+1);
           l=s.Length();
           for (i=1;i<=l;i++)
               {
               c=s[i];
                    if ((c>='0')&&(c<='9')) c-='0';
               else if ((c>='A')&&(c<='F')) c-='A'-10;
               else if ((c>='a')&&(c<='f')) c-='A'-10;
               s[i]=c;
               }
           ll=((l*1234)>>10);  // num of decimals to compute
           for (cy=0,i=1;i<=ll;i++)
               {
               for (cy=0,j=l;j>=1;j--)
                   {
                   val=s[j];
                   val*=10;
                   val+=cy;
                   s[j]=val&15;
                   cy=val>>4;
                   }
               dec+=char(cy+'0');
               for (;;)
                   {
                   if (!l) break;;
                   if (s[l]) break;
                   l--;
                   }
               if (!l) break;;
               }
           }
   
       return dec;
       }
   

   This C++/VCL code is based on dec to/from hex string conversion in C++

Here some full results (no truncating):

e (number)=2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320030599218174135966290435729003342952605956307381323286279434907632338298807531952510190115738341879307021540891499348841675092447614606680822648001684774118537423454424371075390777449920695517018925792726517729626778617556182544467087488974778217580927056560148653881088555812992610052264792986514235903850131924702897536490353138389659085786458507020379306026276137800832832239739365071110193933120100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
e (text)  =2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334295260595630738132328627943490763233829880753195251019011573834187930702154089149934884167509244761460668082264800168477411853742345442437107539077744992069551701892
e (const) =2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334295260595630738132328627943490763233829880753195251019011573834187930702154089149934884167509244761460668082264800168477411853742345442437107539077744992069551702761838606261331384583000752044933826560297606737113200709328709127443747047230696977209310141692836819025515108657463772111252389784425056953696770785449969967946864454905987931636889230098793127736178215424999229576351482208269895193668033182528869398496465105820939239829488793320362509443117301238197068416140397019837679320683282376464804295311802328782509819455815301756717361332069811250996181881593041690351598888519345807273866738589422879228499892086805825749279610484198444363463244968487560233624827041978623209002160990235304369941849146314093431738143640546253152096183690888707016768396424378140592714563549061303107208510383750510115747704171898610687396965521267154688957035035402123407849819334321068170121005627880235193033224745015853904730419957777093503660416997329725088687696640355570716226844716256079882651787134195124665201030592123667719432527867539855894489697096409754591856956380236370162112047742722836489613422516445078182442352948636372141740238893441247963574370263755294448337998016125492278509257782562092622648326277933386566481627725164019105900491644998289315056604725802778631864155195653244258698294695930801915298721172556347546396447910145904090586298496791287406870504895858671747985466775757320568128845920541334053922000113786300945560688166740016984205580403363795376452030402432256613527836951177883863874439662532249850654995886234281899707733276171783928034946501434558897071942586398772754710962953741521115136835062752602326484728703920764310059584116612054529703023647254929666938115137322753645098889031360205724817658511806303644281231496550704751025446501172721155519486685080036853228183152196003735625279449515828418829478761085263981395599006737648292244375287184624578036192981971399147564488262603903381441823262515097482798777996437308997038886778227138360577297882412561190717663946507063304527954661855096666185664709711344474016070462621568071748187784437143698821855967095910259686200235371858874856965220005031173439207321139080329363447972735595527734907178379342163701205005451326383544000186323991490705479778056697853358048966906295119432473099587655236812859041383241160722602998330535370876138939639177957454016137223618789365260538155841587186925538606164779834025435128
e (hex)   =2.B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF324E7738926CFBE5F4BF8D8D8C31D763DA06C80ABB1185EB4F7C7B5757F5958490CFD47D7C19BB42158D9554F7B46BCED55C4D79FD5F24D6613C31C3839A2DDF8A9A276BCFBFA1C877C56284DAB79CD4C2B3293D20E9E5EAF02AC60ACC93ECEBh

The AnsiString is just VCL string class with automatic reallocation so you can add strings simply by +,+= operator ...

[Edit1] description of hex2dec string conversion

Ok we have hex string containing number in hex format and want to compute dec which should hold the same number in decimal format at the end.

1. scan for parts of number

   This just scans the hex string with single O(n) loop and remember where special characters are:

   • i0 first integer digit
   • i1 last integer digit (before decimal point)
   • i2 first fractional digit (after decimal point)
   • i3 last fractional digit
   • sig is set to +1 from start and if - is detected then it is set to -1 means the sign of number

   So we can use that latter for simpler number extraction.

2. convert integer part

   integer part is computed by summing the hex digit values for example:

   • 51Ah = 500h + 10h + Ah = 5*16^2 + 1*16^1 + 10*16^0 = 1306

   This is usually rewritten like this:

   • 51Ah = (((5)*16 +1)*16 +10) = 1306

   You can think of that like you are multiplying number by target BASE(16) in source BASE(10) arithmetics.

   So you start read from the most significant digit first. Add its value to number. If no other integer digit present you stop otherwise multiply the decadic string by 16 and read/add next digit. That is what the second for loop does.

   • if (i0) for (i=i0;i<=i1;i++) if integer part present go through all its digits

   • c is set to the decadic value of processed digit <0,F>hex -> <0,15>dec

   The nested for (cy=c,j=1;j<=l;j++) is just multiplying integer decadic string s by 16. At the start s=""; l=0; where s is decadic result string but in reverse digit order and not coded in ASCII instead values of digits are there directly so {0,1,2,...9} instead of {"0","1",...} and l is number of digits inside s. VCL string are indexed from 1 so that is why for starts with 1 not 0. So how you multiply decadic string by 16?

   123*16= 100*16 +  20*16 +  3*16
         =1600    + 320    + 48
   

   So again read digit decadic value <0,9> (start with least significant one) into val. Multiply it by 16 (or bit-shift left by 4 bits that <<4 is the same as *16 ) and add the carry cy from previous digit if needed (it is set to the hex digit value from start so it also add that ...). now the result is usually more than 1 digit that is where carry goes. So set the resulting digit of s to s[j]=val%10 and set carry to val/10 you can ignore the 10^(j-1) because when you are processing s[j] the powers of 10 are represented by j position so if you store back to s[j] the value of that digit is already powered... This must be done from least significant digit because the higher digits are still changing while computing.

   After this the while (cy>0) is just adding new digits to s if result needs additional one to fit in.

   After this is just s converted from digit values to ASCII in normal order (not reversed anymore) copied to final dec string and signum added if needed. That is all for integer part.

3. fractional part starts with if (i2)

   Fractions are converted to another BASE by multiplying it by target BASE(10) in source BASE(16) arithmetic. So multiply by 10=Ah in hexa arithmetics ...

       ------------
       0.B7Eh -> B7Eh
       ------------
       B7Eh * Ah = 7 2ECh
       2ECh * Ah = 1 D38h
       D38h * Ah = 8 430h
       430h * Ah = 2 9E0h
       -------------
       0.B7Eh -> 0.7182 dec
       ------------
   

   OK if fractional part is present add to the final dec string decimal point .. And extract all fractional hex digits into s string (most significant digit first) convert from ASCII to hex digit values <0,15> and set l to number of fractional digits. the ll is then computed which is the number of decimal fractional digits represented by l hexa fractional digits ll=l*1234/1024 As you can see on the example you can sometimes loop the conversion infinitely generating new fractional digits so ll tels when to stop...

   The conversion starts after the ll computation. for (cy=0,i=1;i<=ll;i++) is just looping through all the result digits to compute. In each its iteration the s is multiplied by 10 but this time in hex arithmetics. That is why s[j]=val%16 and cy=val/16. I use bit operations AND and Bit-shift instead but the result is the same. After the multiplication the carry contains the decimal fractional digit so it is added to the final result.

   The last for just check if the subresult in s is not ending with zeros and if it is it cut them off (by l--) and if no more valid digits left stop the process. This speed up the process a lot for huge numbers...

Hope it is described enough for you...

Answer 2

Each binary digit after the decimal point represents the decimal weight of 2^-n, starting with n=1.

This can be evaluated using any bignum library using Horner's method as: (this is just pseudocode)

power_of_five = 1;
digits = 0;
while digits_left
  digits = digits * 10;
  power_of_five = power_of_five * 5;
  if (next_digit_is_set)
     digits = digits + power_of_five;
end

This will result a 1024 digit bignum, out of which only the first 309 are significant.