AW: Converting to and from FAC

From: Spiro Trikaliotis (Spiro.Trikaliotis_at_gmx.de)
Date: 2000-10-19 09:08:52

Hi Nicholas,

> [COPLIN, Nicholas.]  how did we go from 0.5 (base 10) = 0.1 ?

Ok, let's start more from the beginning.

A decimal number like 123 means exactly

123 = 1*10^2 + 2*10^1 + 3*10^0.

The same goes for digital numbers, e.g., 1001 means

1001 = 1*2^3 + 0*2^2 + 0*2^1 + 1*2^0.


Now, what meaning does a number like 0.123 (decimal) have? Well, it's

0.123 = 0*10^0 + 1*10^-1 + 2*10^-2 + 3*10^-3

Same for digital numbers:

0.1001 = 0*2^0 + 1*2^-1 + 0*2^-2 + 0*2^-3 + 1*2^-4.

Now, having a look at the negative powers of 2, we see that:

2^-1 = 0.5
2^-2 = 0.25
2^-3 = 0.125
2^-4 = 0.0625
...

So, 0.5 (decimal) is exactly 2^-1, so we get 0.5 (dec) = 0.1 (binary).


So, how can we automize this?

You surely know how to convert a positive decimal integer into binary:
You divide by 2, look if there's a remainder, and write it down.

The algorithm is (in a BASIC-like pseudo-code):

DEC2BIN_INTEGER(x)
  REM x = [number to convert]
  binary$ = "" : REM empty string

  do
     rem = remainder of (x/2)
     x   = INT(x/2)
     binary$ = valuetoascii(rem) + binary$
  while (x>0)

  RETURN BINARY$


Converting a fractional number (or the fractional part of a number) into
binary is as easy: You multiply with 2, look if the result is bigger than
1. If yes, you add a '1' at the tail of your number, if no, you add a
'0'.

So, what's the algorithm?

DEC2BIN_FRACTIONAL(x)
   rem x = [fractional part to convert]

   binary$ = "."

   do
     x = x*2
     if (x>1) then
        binary$ = binary$ + "1"
        x = x-1
     else
        binary$ = binary$ + "0"
     endif
   while ((x <> 0) OR (MAX_LENGTH_REACHED))

   RETURN binary$

What's the meaning of MAX_LENGTH_REACHED? You should notice that in most
circumstances without it, the while loop would never terminate, since
most decimal numbers cannot be written exactly in binary! With
MAX_LENGTH_REACHED, which must be calculated at your choice, you force
quitting the LOOP.

Now, how do we convert any positive number to decimal? It's easy, just
have a look at the integer part and the fractional part one after the
other, e.g.,

DEC2BIN_POSITIVE(x)
   rem x = [positive number]
   i = INT(x)
   PRINT DEC2BIN_INTEGER(i) ; DEC2BIN_FRACTIONAL(x-i)


One last word: How long do you need your MAX_LENGTH_REACHED? It must be
long enough so that your resulting string (integer AND fractional part
together) gives you at least 32 digits for the 4 mantissa bytes. I would
recommend at least 33 digits, so you can round the value in a appropriate
way.

HTH,
   Spiro.

--
------------------------------------------------------------------------
Spiro R. Trikaliotis            Otto-von-Guericke-Universitaet Magdeburg
Phone: +49 (0)391 67-12560                     Fakultaet fuer Informatik
Fax:   +49 (0)391 67-11161               Institut fuer verteilte Systeme
EMail: spiro@ivs.cs.uni-magdeburg.de   Echtzeitsysteme und Kommunikation
http://ivs.cs.uni-magdeburg.de/EuK/             PF 4120, 39016 Magdeburg
------------------------------------------------------------------------

-
This message was sent through the cbm-hackers mailing list.
To unsubscribe: echo unsubscribe | mail cbm-hackers-request@dot.tml.hut.fi.

Archive generated by hypermail 2.1.1.