0

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.

aquaticapetheory
  • 105
  • 1
    If $-1$ is allowed, the result is not unique, e.g. $2^{-1} + 2^{-3} - 2^{-5} = 2^{-1} + 2^{-4} + 2^{-5}$. We can just convert $x$ to regular binary, and use the $-1$ to help reduce the chains of $1$'s, e.g. $2^{-2} + 2^{-3} + 2^{-4} + 2^{-5} = 2^{-1} - 2^{-5}$. – player3236 Feb 09 '21 at 01:01
  • Any number can be expressed in binary, octal, decimal, hexadecimal. or any other base. – herb steinberg Feb 09 '21 at 03:57
  • @player3236 Yes, I realize this. Is there a way to automate this process? – aquaticapetheory Feb 09 '21 at 12:48

0 Answers0