A-6.3 Approximate Decomposition

PIC

Figure 2: An illustration of approximate decomposition

If no level ℓ satisfies βℓ∣q, then some lower-order digits of q (in base β) must be discarded during decomposition, as shown in Figure 2. Such lower bits can be rounded to the nearest multiple of q βℓ during decomposition. In such a case, the decomposition is an approximate decomposition. Formally, when βℓ ∤ q we can write

γ = ∑ i=1ℓγ i q βi + 𝜀,γi ∈{0,…,β −1},|𝜀|≤ q 2βℓ

(using nearest-integer rounding and identifying γ with its integer representative)The polynomial case is analogous, coefficient-wise.