How to find most efficient approximation of a real number with combination of positive and negative powers of two?

46 Views Asked by At

I need to approximate a real number $x$ as a sum of some set of positive and negative powers of two, e.g.

$$ x = \delta_0 2^{n_0} + \delta_1 2^{n_1} + \delta_2 2^{n_2} + \ldots $$

where each $\delta_i$ is $-1$ or $+1$ and each $n_i$ is some integer. Basically, I keep adding or subtracting smaller and smaller powers of two until I get close enough.

For example, $$ x=0.5937 \approx 2^{-1} + 2^{-3} - 2^{-5}=0.59375 $$ and I could keep going to get closer. Note, I'm interested in reals, not integers, and especially $x\in (0,1)$.

The reason I want this is to do multiply by an a priori known constant digitally using shifting and sums, not proper multipliers. I've been picking these out by hand but this seems like it should be a well known algorithm. Please help.