References: rigorous algorithms for elementary computations in base-b with complexity estimates

Question

Definitions/Notation: Fix positive integers $b$ and $M$. Consider the set of real numbers which can be exactly expressed with $2M+1$ coefficients in base $b$, defined by $$\mathcal{X}(b,M):=\{x\in \mathbb{R}:\, (\exists s\in \{0,1\})\,(\exists c_{-M},\dots,c_M\in \{0,\dots,b-1\}\, x=(-1)^s \sum_{i=-M}^M c_i b^i\}.$$
Further, consider the coefficient set $B_M:=\{0,\dots,b-1\}^M\times \{0,\dots b-1\}^{M+1} \times \{0,1\} $, with the "floating point-type identification" $$ \mathcal{X}(b,M)\ni x = (-1)^s\sum_{i=-M}^M c_i b^i \mapsto \big( (c_i)_{i=-M}^{-1} , (c_i)_{i=0}^{M} , \operatorname{sgn}(x) \big) $$
where $\operatorname{sgn}(x):=I_{x\ge 0}$ identifies if $x$ is positive or negative; i.e.\ $\operatorname{sgn}(x)=s$ in the above representation determines the negativity/positivity of $x$, $(c_i)_{i=-M}^{-1}$ are the coefficients for the fractional part of $|x|$ in $[0,1)$ and $ (c_i)_{i=0}^{M}$ are the coefficients for the integer part of $|x|$.

Example/Note: For instance, if $b=2$, then this defines numbers with a finite-length binary expansion.

---

I'm looking for a reference book that rigorously provides algorithms and computational complexity (space and time) estimates for implementation: addition, multiplication, division, exponentiation, etc...(other "elementary operations)) on elements of $\mathcal{X}(b,M)$ in terms of their coefficient "representations" in $B_M$.

Unfortunately, everything I've come across just gives numerical examples or example code... (I'm obviously looking in the wrong place but I just don't know where to look).

Answer 1

In cryptography, one often needs to implement modular (and polynomial) arithmetic $\mathbb{Z}/N\mathbb{Z}$, but your hardware only natively supports computations in $\mathbb{Z}/n\mathbb{Z}$. Typical choices of $(N, n)$ are things like

• $\log_2 N\geq 2048$ (RSA), or $\log_2 N\approx 500$ (ECC), or $\log_2 N\leq 40$ (lattices, though one typically needs polynomial arithmetic for these), and
• $\log_2 n \in\{64,128\}$ (desktops), $\log_2 n\in\{32,64\}$ (phones), and $\log_2 n\in\{8,16\}$ (embedded).

For this reason, cryptographers often treat a problem fairly similar to yours quite carefully. The standard (though now somewhat dated) reference is Chapter 14 of "The Handbook of Applied Cryptography" by Menzes et. al. The paper Multiplying Polynomials without Powerful Multiplication Instructions is more recent, and while it is (in the end) focused on polynomial arithmetic, it contains sections and references more focused on the case of modular arithmetic, e.g. Sections 2.5 and 3.1.