Fixed-Dimension Dyadic Matrix Routines Have Polynomial Bit Cost

Query each Cauchy procedure at precision $q+4$, obtaining a rational $r$ with $\mathrm{\mid }r-x\mathrm{\mid }\le 2^{-q-4}$. Round $r$ to a dyadic $a$ with $\mathrm{\mid }a-r\mathrm{\mid }\le 2^{-q-4}$ and return $[a-2^{-q-3},a+2^{-q-3}]$; it contains $x$ and has width $2^{-q-2}$. This rounding costs $O(L+q^2)$ for an $L$-bit rational: scan its numerator and denominator to determine their binary lengths, discard values below the error tolerance, and otherwise retain their leading $q+O(1)$ bits before long division. Since $\mathrm{\mid }r\mathrm{\mid }\le 4$, truncating both integers at that relative precision changes the quotient by at most $2^{-q-5}$ after a fixed guard increase; the dyadic division rounding fits the remaining error budget. The scan costs $O(L)$ and the shortened division $O(q^2)$, while $L=O((q+1{)}^c)$ by the query-time bound. If the fixed composition has no operations, copying this input interval already gives the claimed enclosure. Choose $q=p+K^{\mathrm{\prime }}(B+1)+K^{\mathrm{\prime }}\lceil {\log }_2(p+2)\rceil +C_0$ with sufficiently large fixed $K^{\mathrm{\prime }},C_0$. The interval endpoints have $O(p+B)$ bits after the binary point. Addition, comparison, and rounding use $O(p+B)$ bit operations; schoolbook multiplication and long division use $O((p+B{)}^2)$. Outward rounding at $q$ fractional bits adds at most $C{2}^{-q}$ local error per operation. Induction through the fixed expression tree, using the input bound $3$ and divisor lower bound $2^{-B}$, gives a bound $M=2^{K(B+1)}$ for all exact intermediate magnitudes and error-amplification factors, with fixed $K$: sums and products of a fixed number of quantities bounded by $2^{K(B+1)}$ remain so after increasing $K$, while a quotient has magnitude at most $M{2}^B$ and error gain at most $2^{O(B+1)}$ by the estimate below. The expression has only a fixed number of such operations, so one larger $K$ covers every stage. For a quotient $x\mathrm{/}y$, let $x^{\mathrm{\prime }},y^{\mathrm{\prime }}$ be its midpoint inputs, each within $\delta$ of the exact value, where $\delta \le 2^{-B-1}$. Then $\mathrm{\mid }{y}^{\mathrm{\prime }}\mathrm{\mid }\ge 2^{-B-1}$ and $\mathrm{\mid }{x}^{\mathrm{\prime }}\mathrm{\mid }\le 2M$, so $\mid \frac{x}{y}-\frac{x^{\mathrm{\prime }}}{y^{\mathrm{\prime }}}\mid \le 2^B\delta +M{2}^{2B+2}\delta =2^{O(B+1)}\delta$. The stated guard precision therefore makes propagated input and rounding errors at most $2^{-p-4}$. Each Cauchy query costs $O((q+1{)}^c)$ and each dyadic operation costs $O((p+B{)}^2)$, so the fixed routine costs $O((p+B+1{)}^{\max (c,2)})$ and encloses the exact answer.

To compute $\sqrt{x}$ for $0\le x\le 1$, request an interval $[x_{-},x_{+}]$ of width at most $2^{-2p-12}$ and set $\mathrm{\ell }=\max (0,x_{-})$ and $u=\min (1,x_{+})$. Then $\mathrm{\ell }\le x\le u$ and $u-\mathrm{\ell }\le 2^{-2p-12}$. The inequality $\mathrm{\mid }\sqrt{x}-\sqrt{y}\mathrm{\mid }\le \sqrt{\mathrm{\mid }x-y\mathrm{\mid }}$ shows that the input uncertainty contributes at most $2^{-p-6}$. Bisect separately for the exact rational endpoints $\mathrm{\ell },u$ on $[0,1]$, comparing squared dyadic midpoints with those endpoints. After $O(p)$ bisections the two square roots are enclosed by dyadic intervals of width at most $2^{-p-4}$; monotonicity encloses $\sqrt{x}$ in their combined interval, whose width is at most $2^{-p-6}+2^{-p-3}<2^{-p}$. Each comparison uses $O(p^2)$ bit operations, so the total is $O(p^3)$. For normalization, choose a fixed power of two $R\ge 3\sqrt{d}$ and compute $\mathrm{\parallel }v{\mathrm{\parallel }}_2=R\sqrt{{\sum }_i(v_i\mathrm{/}R{)}^2}$ to $q$ bits, so the square-root input lies in $[0,1]$. The norm changes by at most $\mathrm{\parallel }v-v^{\mathrm{\prime }}{\mathrm{\parallel }}_2$; division by a norm at least $2^{-B}$ and the preceding division estimate show that $q$ guard bits suffice to return each coordinate of $v\mathrm{/}\mathrm{\parallel }v{\mathrm{\parallel }}_2$ within $2^{-p}$. The vector has fixed dimension, so this costs $O((p+B+1{)}^{\max (c,3)})$.

Request the entries of $A$ to $q^{\mathrm{\prime }}$ bits, where $q^{\mathrm{\prime }}=p+2\lceil {\log }_2(p+2)\rceil +C_0$ and $C_0$ is a sufficiently large absolute constant. Let $A^{\mathrm{\prime }}$ be the midpoint matrix. Since $d$ is fixed, $\mathrm{\parallel }A-A^{\mathrm{\prime }}\mathrm{\parallel }\le C{2}^{-q^{\mathrm{\prime }}}$ and $\mathrm{\parallel }{A}^{\mathrm{\prime }}\mathrm{\parallel }\le 3\mathrm{/}2$. The telescoping identity for powers gives $\mathrm{\parallel }{A}^j-A^{\mathrm{\prime }j}\mathrm{\parallel }\le j(3\mathrm{/}2{)}^{j-1}\mathrm{\parallel }A-A^{\mathrm{\prime }}\mathrm{\parallel }$, so their exponential series differ by at most $e^{3\mathrm{/}2}\mathrm{\parallel }A-A^{\mathrm{\prime }}\mathrm{\parallel }$. Truncate the series for $e^{A^{\mathrm{\prime }}}$ at $m=24(p+2)$. Using $j!\ge 2^{j-1}$, its tail is at most $8(3\mathrm{/}4{)}^{m+1}<2^{-p-4}$. Compute terms recursively as $T_0=I$ and $T_j=T_{j-1}{A}^{\mathrm{\prime }}\mathrm{/}j$, rounding each product and division outward to $q^{\mathrm{\prime }}$ fractional bits. The error recurrence is $e_j\le (3\mathrm{/}2)e_{j-1}\mathrm{/}j+C{2}^{-q^{\mathrm{\prime }}}$; after $j=1$, its multiplier is at most $3\mathrm{/}4$, so $e_j\le C^{\mathrm{\prime }}{2}^{-q^{\mathrm{\prime }}}$ uniformly. Summing $m$ terms contributes at most $C^{\mathrm{\prime }}m{2}^{-q^{\mathrm{\prime }}}$. The choice of $q^{\mathrm{\prime }}$ makes total error, including the input perturbation, less than $2^{-p}$. There are $O(p)$ products and divisions of fixed-size matrices with $O(p)$-bit operands, hence the dyadic arithmetic cost is $O((p+1{)}^3)$. Including Cauchy queries as in step 1.1, the routine cost is $O((p+1{)}^{\max (c,3)})$. For $\mathrm{\parallel }E\mathrm{\parallel }\le 1\mathrm{/}2$, request the entries to the same precision and let $E^{\mathrm{\prime }}$ be the midpoint, so $\mathrm{\parallel }{E}^{\mathrm{\prime }}\mathrm{\parallel }\le 3\mathrm{/}4$. The series difference between $E$ and $E^{\mathrm{\prime }}$ is bounded by ${\sum }_{j\ge 1}\mathrm{\parallel }{E}^j-E^{\mathrm{\prime }j}\mathrm{\parallel }\mathrm{/}j\le 4\mathrm{\parallel }E-E^{\mathrm{\prime }}\mathrm{\parallel }$. Truncate the logarithm series for $E^{\mathrm{\prime }}$ at $m=24(p+2)$. Its tail is at most ${\sum }_{j>m}(3\mathrm{/}4{)}^j\mathrm{/}j\le 4(3\mathrm{/}4{)}^{m+1}<2^{-p-4}$. Successive computed powers have errors bounded by a geometric sum of their rounding errors, since $\mathrm{\parallel }{E}^{\mathrm{\prime }}\mathrm{\parallel }\le 3\mathrm{/}4$. After multiplication by $1\mathrm{/}j$ and summation, total power, coefficient and outward-rounding error is at most $C(m+1)2^{-q^{\mathrm{\prime }}}$, below $2^{-p-2}$ after increasing the fixed constant $C_0$. Thus the logarithm interval also has diameter at most $2^{-p}$ and dyadic arithmetic cost $O((p+1{)}^3)$; including Cauchy queries, its cost is $O((p+1{)}^{\max (c,3)})$.

Let $\alpha$ be a fixed algebraic real constant, described by a rational polynomial $f$ and an open rational interval with nonroot endpoints on which $f$ has opposite endpoint signs and exactly one real root, namely $\alpha$. At each bisection, evaluate $f$ exactly at the rational midpoint. If it is a root, return it exactly; otherwise the unique-root and sign-change conditions identify the half containing $\alpha$. After $O(p)$ bisections the interval has width at most $2^{-p-3}$; round its lower endpoint down and its upper endpoint up to multiples of $2^{-p-3}$. The resulting dyadic interval has width at most $3\cdot 2^{-p-3}<2^{-p}$. An exact rational root is enclosed by the same outward-rounding rule. Each evaluation has $O(p)$-bit operands and fixed degree, and there are $O(p)$ bisections, giving $O(p^3)$ bit operations. Real and imaginary parts are handled separately. The number of matrix coordinates is fixed, so all coordinatewise bounds above give the claimed matrix-interval bounds.