Author: | Wojciech Muła |
---|---|

Added on: | 2023-02-05 |

Suppose we have a binary fraction, that is positive and less than 1:

0.101011000... = 0.671875 | | || | | |+-- 1/2^6 | | +--- 1/2^5 | +----- 1/2^3 +------- 1/2^1

We want to express it as a ratio of two integer numbers.

The value of the sample number is:

1 1 1 1 ---- + ---- + ---- + ---- 1 3 5 6 2 2 2 2

We want to add these fractions, and to do this we have to find the common denominator. In our case it will be the product of all denominators we have:

2^{1}⋅ 2^{3}⋅ 2^{5}⋅ 2^{6}= 2^{1 + 3 + 5 + 6}= 2^{15}

Note that the exponent is simply sum of positions (counted from 1) of bits equal 1.

The numerator has the sum of four products; each product contains all but single power:

(2^{3}⋅ 2^{5}⋅ 2^{6}) + (2^{1}⋅ 2^{5}⋅ 2^{6}) + (2^{1}⋅ 2^{3}⋅ 2^{6}) + (2^{1}⋅ 2^{3}⋅ 2^{5})

It is simpler to express products using the denominator's power:

2^{15 − 1}+ 2^{15 − 3}+ 2^{15 − 5}+ 2^{15 − 6}= 2^{14}+ 2^{12}+ 2^{10}+ 2^{9}

Finally, we need to reduce the fraction. To do this, we simply find the minimum exponent from the numerator (it is 9) and subtract it from all powers of two present in the fraction. Thus finally we have:

(2

^{14 − 9}+ 2^{12 − 9}+ 2^{10 − 9}+ 2^{9 − 9})/2^{15 − 9}=(2

^{5}+ 2^{3}+ 2^{1}+ 2^{0})/2^{6}=(32 + 8 + 2 + 1)/64 =

(32 + 8 + 2 + 1)/64 = 43/64 = 0.671875

The algorithm uses only simple arithmetic and bit operations.

Sample source code is available on Github.