Suppose I have a 32-bit integer $x$, I want to find $\{ x_i \}_{i \in 1\dots\ell}$ such that $x = e + \sum_{i=1}^\ell x_i \cdot 2^{32 - B\cdot i}$ where the error $e$ is as small as possible. The parameter $\ell$ is the level of the decomposition and $B$ is the base of the decomposition. Increasing $\ell$ and decreasing $B$ will result in a more accurate decomposition.

Is there an algorithm that solves this kind of problem?

  • $\begingroup$ Is $B$ an integer? $\endgroup$
    – xskxzr
    Commented Mar 23, 2022 at 2:32
  • $\begingroup$ Some requirements must be missing. Can't you set $x_\ell = x/2^{32-B\ell}$ and all other $x_i=0$? Do you require the $x_i$'s to be integers? Why is this anything other than a base conversion problem? $\endgroup$
    – D.W.
    Commented Mar 23, 2022 at 6:25
  • $\begingroup$ What are $x_i$s? I assume those are integers, right? If so - then using only one integer, when $i$ is the largest - will result in the same accuracy (since all other values are integer multiples of it), so you can solve this algebraically. So maybe restricting $x_i$ to some range (or even bits) would be much more interesting $\endgroup$
    – nir shahar
    Commented Mar 23, 2022 at 6:26
  • $\begingroup$ Assuming that L is fixed, and the B_i are fixed, you would indeed just pick I so that B_i is largest B_i, let x_i = x / 2^(32 - B_i), rounded to the nearest integer, and all other x_k are zero. Error is at most half of 2^(32 - B_i). $\endgroup$
    – gnasher729
    Commented Aug 24, 2022 at 13:48

1 Answer 1


Assuming that $B$ and the $x_i$ are integers, you can recast the question as

$$\frac x{2^{32}}\approx\sum_{i=1}^l x_iP^i$$ where $P:=2^{-B}$, and you look for the best approximation of $\dfrac x{2^{32}}<1$ in base $2^B$ using $l$ digits.

Just write the binary representation of that number and get the digits in $l$ slices of $B$ bits.

E.g. $\frac{123456789_d}{2^{32}}=0.00000111010110111100110100010101_b=0.01655715052_o$ ($o$ for octal) gives all solutions for $B=3$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.