THE INTEGER SQRT square root digit by digit — only add, subtract, and shift
You can extract an integer square root with no multiplication and no division — the same long-hand method taught for decimal roots, run in base 4. Start with the largest power of four not exceeding n; at each step test whether the current root plus that bit, when “squared into place,” still fits under n. Because the trial term is res + bit and the update is a shift, every operation is an add, a subtract, or a shift. It converges two bits at a time to ⌊√n⌋ — exact, deterministic, hardware-friendly.
THE TECHNIQUE base-4 digit-by-digit — test res+bit, shift; add/sub/shift only
The demo extracts ⌊√144⌋ = 12 by the base-4 digit method, using only add, subtract, and shift (no multiply, no divide): live demo
HISTORY & CREDIT digit-by-digit sqrt · base-4 binary form
“Square root needs multiplication.” — the digit-by-digit method needs only add, subtract, and shift; it is long-division’s cousin. cited
the trial · at each base-4 place, test n ≥ res + bit — the “squared into place” term is just a shift of the partial root. the update · if it fits: n −= res+bit; res = (res>>1)+bit; else res >>= 1 — two bits per step. lineage · the pencil-and-paper square-root algorithm, transposed to binary — classic in fixed-point hardware.
The root assembled two bits at a time by trial-subtract and shift — √n with no multiply. resource
RECOMMEND FOR I-13 digit-by-digit root, on the compiler
On the canonical compiler, the base-4 method returns ⌊√144⌋ = 12 using only add/subtract/shift:
$ i13 run tk_isqrt.i13 # base-4 trial-subtract, add/sub/shift only
RUN OK · 175 step(s) · peak stack 5 · call depth 5
n = 144
s = 12 -- floor(sqrt(144))
same = 1 -- exact integer root, no multiply/divide
Recommend as a NULL — resource, the reduce-to-primitives kind. Integer sqrt computes ⌊√n⌋ (i13 prints 12) using only the cheapest ops; a multiply-based Newton isqrt would give the same integer. So the differences are entirely which primitives are used and how many steps — resource (B40). It rounds out the batch’s “hard function from cheap ops” family with division (416) and GCD (417). NULL — same root, leaner mechanism.