P is for Practical PerlMonks

### Converting decimals to binary

by ketema (Scribe)
 on Nov 11, 2004 at 15:24 UTC Need Help??

ketema has asked for the wisdom of the Perl Monks concerning the following question:

I need help with an algorithm to map decimal values to binary integers. Here is the situation: Say you have a list of decimal numbers: (0.15, 0.015, 0.85), if you were to attempt to convert these directly to binary you would of course get 0.

However, lets assume that we decide to only use a max of two bits, the only numbers we can represent are 0,1,2, and 3 (00,01,10,11). SInce our decimal numbers are constrained between 0 and 1, we can simply divide 1 by 4 and approximate with an if block:
so all numbers from 0 to .25 map to 00, from .25 to .5 map to 01, .5 to .75 to 10, and .75 to 1 to 11

Now of course that is not very precise, but it illustrates what I want to do. To icrease accuracy we just increase the number of bits used and divide the 0 to 1 space more finely. On a 32 bit processor we can have 32 1's which is 4294967295 unique integers.

1 divided by above number is 2.3283064370807973754314699618685e-10, that is a pretty fine division, however I don't want to write an if statement that long. What is the best way to figure out where a decimal would lie in a given range then map it to the correct binary representation?

2004-11-12 Edited by Arunbear:

• Changed title from 'Mapping Algorithm', as per Monastery guidelines

Replies are listed 'Best First'.
Re: Converting decimals to binary
by ikegami (Pope) on Nov 11, 2004 at 15:54 UTC

There is something call fixed point numbers (as opposed to floating point), and it sounds like that's what you need. In this case, I fixed the point (B-scaling) to 0 (unsigned) integer bits (allowing numbers from 0 to +1, not including +1).

```
foreach (
0.750
0.500,
0.400,
0.250,
0.125,
) {
my \$num    = \$_;
my \$num_B0 = \$num * 4294967296;  # 0..+1 not incl +1.
#my \$num_B1 = \$num * 2147483648;  # 0 to just over +1.

printf("%f = %s B0\$/",
\$num,
unpack('B32', pack('N', \$num_B0)),
);
}

__END__
output
======
0.750000 = 11000000000000000000000000000000 B0
0.500000 = 10000000000000000000000000000000 B0
0.400000 = 01100110011001100110011001100110 B0
0.250000 = 01000000000000000000000000000000 B0
0.125000 = 00100000000000000000000000000000 B0

.5, .25 and .125 are round numbers cause they're 2^(-1), 2^(-2) and 2^(-3) respectively.

The machine for which I write software doesn't support floating point numbers, so we use fixed point arithmetic (which any integer arithmetic machine can do). It can be a pain at times, since we deal with an extreme number of decimal numbers like valve positions, temperature measurements, etc. (It's the control system of a nuclear power plant.)

Let me know if you want to know how to do math with fixed point numbers.

How does multiplying by 4294967296 not include 1 but multiplying by 2147483648 does?

In response to the first reply, if I just multiply the decimal by the "accuracy" per say then take the integer portion am I losing more accuracy, than the fixed point answer provided by number 2? Are these two solutions the same?

```I don't know of any sources, but here's some background.

Let's use smaller numbers to demonstrate. Let's say we have 4 bit numb
+ers.

+---+---+---+---+
|   |   |   |   |
+---+---+---+---+

As a little refresher, let's forget decimal numbers for a second.

+---+---+---+---+
| 0 | 1 | 1 | 1 |  7 = 0*2^3 + 1*2^2 + 1*2^1 + 0*2^0
+---+---+---+---+

I'm going to call that B4, since 4 bits are used by the integer portio
+n of the number.

+---+---+---+---+
| 0 | 1 | 1 | 1 |  7 B4
+---+---+---+---+

So how would you store a decimal number? Let's take 1.75, for example.

+---+---+---+---+   +   +
| 0 | 0 | 0 | 1 | 1   1    1.75 = 1*2^0 + 1*2^(-1) + 1*2^(-2)
+---+---+---+---+   +   +

Unfortunately, I can't just add bits to my register.
What if we shifted the bits?

+---+---+---+---+
| 0 | 1 | 1 | 1 |  1.75 * 2^2 = [ 1*2^0 + 1*2^(-1) + 1*2^(-2) ] * 2
+^2
+---+---+---+---+

Another way of phrasing that is in terms of number of integer bits lef
+t.

+---+---+---+---+
| 0 | 1 | 1 | 1 |  1.75 B2 = [ 1*2^0 + 1*2^(-1) + 1*2^(-2) ] * 2^(4
+-2)
+---+---+---+---+

In other words, using smaller B-scalings increases precision:
The following show the precision for a given scaling.

+---+---+---+---+
| 0 | 0 | 0 | 1 |  [ 1*2^0    ] * 2^(4-4) = 1 B4
+---+---+---+---+

+---+---+---+---+
| 0 | 0 | 0 | 1 |  [ 1*2^(-1) ] * 2^(4-3) = 0.5 B3
+---+---+---+---+

+---+---+---+---+
| 0 | 0 | 0 | 1 |  [ 1*2^(-2) ] * 2^(4-2) = 0.25 B2
+---+---+---+---+

+---+---+---+---+
| 0 | 0 | 0 | 1 |  [ 1*2^(-3) ] * 2^(4-1) = 0.125 B1
+---+---+---+---+

+---+---+---+---+
| 0 | 0 | 0 | 1 |  [ 1*2^(-4) ] * 2^(4-0) = 0.0625 B0
+---+---+---+---+

Nothing says we have to stop at 0.

+---+---+---+---+
| 0 | 0 | 0 | 1 |  [ 1*2^(-5) ] * 2^(4--1) = 0.03125 B-1
+---+---+---+---+

The downside is that biggest number we can represent goes down
as the precision increases.

+---+---+---+---+
| 1 | 1 | 1 | 1 |  [ 1*2^3    + 1*2^2    + 1*2^1    + 1*2^0    ] *
+2^(4-4) = 15 B4
+---+---+---+---+

+---+---+---+---+
| 1 | 1 | 1 | 1 |  [ 1*2^2    + 1*2^1    + 1*2^0    + 1*2^(-1) ] *
+2^(4-3) = 7.5 B3
+---+---+---+---+

+---+---+---+---+
| 1 | 1 | 1 | 1 |  [ 1*2^1    + 1*2^0    + 1*2^(-1) + 1*2^(-2) ] *
+2^(4-2) = 3.75 B2
+---+---+---+---+

+---+---+---+---+
| 1 | 1 | 1 | 1 |  [ 1*2^0    + 1*2^(-1) + 1*2^(-2) + 1*2^(-3) ] *
+2^(4-1) = 1.875 B1
+---+---+---+---+

+---+---+---+---+
| 1 | 1 | 1 | 1 |  [ 1*2^(-1) + 1*2^(-2) + 1*2^(-3) + 1*2^(-4) ] *
+2^(4-0) = 0.9375 B0
+---+---+---+---+

+---+---+---+---+
| 1 | 1 | 1 | 1 |  [ 1*2^(-2) + 1*2^(-3) + 1*2^(-4) + 1*2^(-5) ] *
+2^(4--1) = 0.46875 B-1
+---+---+---+---+

We can go the other way, if need be.

+---+---+---+---+
| 1 | 1 | 1 | 1 |  [ 1*2^4    + 1*2^3    + 1*2^2    + 1*2^1    ] *
+2^(4-5) = 30 B5
+---+---+---+---+

+---+---+---+---+
| 0 | 0 | 0 | 1 |  [ 1*2^1    ] * 2^(4-5) = 2 B5
+---+---+---+---+

<blockquote><i>How does multiplying by 4294967296 not include 1 but mu
+ltiplying by 2147483648 does?</i></blockquote>

Multiplying by 4294967296 (2^32) gives 32 bits for the decimal portion
+,
leaving no bits (32-32) for the integer portion. In other words, B0.
1 does not fit into no bits.

+   +---+-----
1 | 0 | ...         1 B0
+   +---+-----

Multiplying by 2147483648 (2^31) gives 31 bits for the decimal portion
+,
leaving 1 bit (32-31) for the integer portion. In other words, B1.
1 fits in one bit.

+---+---+-----
| 1 | 0 | ...     1 B1
+---+---+-----

So what's the advantage over floating-point numbers?
Floating-point numbers does this the same way, and it does it for you.
However, in order to do that, it must save the scaling (called "expone
+nt")
along with the number. That means floats require more memory to store
+than these.

So what good is any of this anyway?
You can use integer arithmetic on these numbers!

X Bi + Y Bi = (X+Y) Bi
X Bi - Y Bi = (X-Y) Bi
X Bi * Y Bj = (X*Y) B(i+j)
X Bi / Y Bj = (X/Y) B(i-j)
X Bi >> j   = X B(i+j)
X Bi << j   = X B(i-j)

You can also compare numbers of the same scaling.

X Bi <  Y Bi
X Bi >  Y Bi
X Bi == Y Bi
etc.

A = ...    # B1
B = ...    # B1
C = A + B  # POTENTIAL OVERFLOW!
# 1 B1 + 1 B1 will overflow, for example

There are two ways of avoiding overflow.
You can make sure in advance that the numbers won't cause an overflow,
+ or
you can switch to a different B-scaling (at the cost of a bit of preci
+sion).

A = ...     # B1
A = A >> 1  # B2
B = ...     # B1
B = B >> 1  # B2
C = A + B   # B2

We do lots of works with values in [0.0..1.0]. When we need to calcula
+te by
how much a valve should be open, we calculate it using values in [0.0.
+.1.0].
Later on, we convert them to the right value to send to the Analog Out
+put.
It sounds like you want to deal with numbers in this same range, so I
+thought
the following would be very useful to you:

A = ...          # B1  Must be between 0.0 and 1.0.
B = ...          # B1  Must be between 0.0 and 1.0.
C = A * B        # B2
C = C << 1       # B1  Safe, since 1.0 * 1.0 = 1.0.

Although we've only dealt unsigned numbers, everything
I've said so far applies to signed 2s complement numbers.

You can look how it's done in FORTH. FORTH-Users don't have floating point numbers (unless one has written a library that is), so they do all with fixed point arithmetic. And it's very fast. You should find some examples if you google for FORTH.

Re: Converting decimals to binary
by fglock (Vicar) on Nov 11, 2004 at 15:56 UTC
```use strict;
use Bit::Vector;

sub frac_bin {
my \$frac = shift;
my \$i = int( \$frac * 2 ** 32 );
print "input: \$frac\n";
my \$vec = Bit::Vector->new_Dec( 32, \$i );
my \$result = \$vec->to_Bin;
print "binary fraction: \$result\n";
return \$result;
}

my \$bits;
\$bits = frac_bin ( 0.5 );
\$bits = frac_bin ( 0.75 );
\$bits = frac_bin ( 1 / 3 );

result:

```input: 0.5
binary fraction: 10000000000000000000000000000000
input: 0.75
binary fraction: 11000000000000000000000000000000
input: 0.333333333333333
binary fraction: 01010101010101010101010101010101
Re: Converting decimals to binary
by JediWizard (Deacon) on Nov 11, 2004 at 15:42 UTC

Would it not work to simply multiply the value in question by the number of unique integers you wish to approximate, and take the integer portion of the result?

```print int(.99 * 4); # output = 3
print int(.2 * 4);  # output = 0

From there you simply need to convert the resulting number into a binary value. For that, use pack.

May the Force be with you

Create A New User
Node Status?
node history
Node Type: perlquestion [id://407067]
Approved by JediWizard
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others studying the Monastery: (7)
As of 2020-02-19 17:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
What numbers are you going to focus on primarily in 2020?

Results (84 votes). Check out past polls.

Notices?