corollaryroutine

Exact division and square root in multiplication time

So division and square root also take O(n(lg⁡n)1−κ)O(n(\lg n)^{1-\kappa}) time
payoff of the main theorem
Corollary·cor:exact-arithmetic·§1.4 Other arithmetic operations

Statement (paper)

There are deterministic machines with fixed finite alphabets and fixed finite numbers of one-dimensional tapes performing the following tasks in O(n(lg⁡n)1−κ)O(n(\lg n)^{1-\kappa}) worst-case time, for every n≥1n\ge1. For x,y∈{0,1}nx,y\in\{0,1\}^n, put a=val⁡(x)a=\operatorname{val}(x) and b=val⁡(y)b=\operatorname{val}(y). If b>0b>0, the division machine takes x#yx\#y and returns bin⁡n(q)#bin⁡n(r)\operatorname{bin}_n(q)\#\operatorname{bin}_n(r), where q=⌊a/b⌋q=\lfloor a/b\rfloor and r=a−bqr=a-bq. The square-root machine takes xx and returns bin⁡n(⌊a⌋)\operatorname{bin}_n(\lfloor\sqrt a\rfloor). Leading zeroes are allowed, and κ\kappa is as in Theorem .

In plain English

On fixed-alphabet, fixed-tape deterministic machines, integer division with remainder and integer square root of nn-bit inputs, with leading zeroes allowed, can be computed exactly in O(n(lg⁡n)1−κ)O(n(\lg n)^{1-\kappa}) time. Division returns ⌊a/b⌋\lfloor a/b\rfloor and a−b⌊a/b⌋a-b\lfloor a/b\rfloor for b>0b>0, and square root returns ⌊a⌋\lfloor\sqrt a\rfloor, each padded to nn bits.

Why it's here

This shows that the multiplication bound of the main theorem carries over to division and square root. The proof runs Newton iteration for the reciprocal and the inverse square root with precision doubling, so the total cost is dominated by the last step and is O(B(n))O(B(n)). A final constant-size correction step then makes the quotient, remainder and root exact.
Classified routine:
Follows from the main theorem by the classical Newton-iteration reduction of division and square root to multiplication (e.g. Cook 1966; Brent–Zimmermann, Modern Computer Arithmetic), whose precision doubling keeps the total cost within a constant factor of one multiplication, plus a constant-size final correction.

Uses

thmInteger multiplication in O(n (lg n)^{1-κ}) time

Used by

Nothing in the paper

Inside the proof

claimNormalization and rounding conventions for Newton iterationclaimRounded reciprocal Newton step residual boundclaimCapped doubling gives reciprocal to precisionclaimRounded Newton square-root error analysisclaimNewton routines cost O(B(p)) on fixed tapesclaimExact quotient and root by correction tests

Sources

PaperOpen
Section
§1.4 Other arithmetic operations
Page
—
Label
cor:exact-arithmetic
Line
sections/00-introduction.tex:194
Leannot aligned

Phase 2 aligns this node to a Lean declaration.