# Integer decomposition algorithm

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?

• Is $B$ an integer? Commented Mar 23, 2022 at 2:32
• 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?
– D.W.
Commented Mar 23, 2022 at 6:25
• 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 Commented Mar 23, 2022 at 6:26
• 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). Commented Aug 24, 2022 at 13:48

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$$.