Integer Square Root

Integer Square Root

The greatest integer Root whose square does not exceed the nonnegative integer Radicand.

floor(sqrt(N))

The mathematical definition of the integer square root of a nonnegative integer N.

Root² <= N < (Root + 1)²

The inequality that characterizes the correct integer square root.

Radicand

The nonnegative integer input whose integer square root is being determined.

Root

The integer result produced by IntegerSquareRoot.

Remainder

The amount remaining after the square-root construction process represented by the working remainder.

IntegerSquareRoot

A combinational RTL module that constructs an integer square root through repeated shift, trial, compare, subtract, and root-bit decisions.

ROOT_WIDTH = (WIDTH + 1) / 2

The number of bits allocated for the integer Root.

Why is ROOT_WIDTH approximately half of WIDTH?

Squaring an n-bit root can require roughly 2n bits, so a WIDTH-bit radicand needs approximately half as many root bits.

Why is WIDTH + 1 used before dividing by 2?

Integer division then rounds the required root width upward when WIDTH is odd.

WIDTH = 8 → ROOT_WIDTH = 4

What root width results from the default 8-bit Radicand?

WIDTH = 7 → ROOT_WIDTH = 4

What root width results from a 7-bit Radicand?

output reg [((WIDTH + 1) / 2) - 1:0] Root

Declares Root with the calculated integer-square-root result width.

PADDED_WIDTH = 2 * ROOT_WIDTH

Defines an even working width suitable for processing the Radicand in two-bit groups.

Why does the algorithm use PADDED_WIDTH?

The square-root procedure consumes Radicand information in pairs of bits, so an even number of working bits simplifies the grouping.

PaddedRadicand

The Radicand after zero extension to the even PADDED_WIDTH required by the two-bit-at-a-time algorithm.

reg [PADDED_WIDTH - 1:0] PaddedRadicand

Declares the even-width combinational Radicand representation used internally.

PaddedRadicand = {{(PADDED_WIDTH - WIDTH){1'b0}}, Radicand}

Zero-extends Radicand to PADDED_WIDTH.

Why is PaddedRadicand zero-extended rather than sign-extended?

IntegerSquareRoot treats Radicand as a nonnegative unsigned integer.

Even WIDTH

PADDED_WIDTH normally equals WIDTH because the Radicand already contains an even number of bits.

Odd WIDTH

PADDED_WIDTH becomes WIDTH + 1 so that a leading zero creates an even number of Radicand bits.

WIDTH = 8 → ROOT_WIDTH = 4 → PADDED_WIDTH = 8

What are the default square-root working widths?

WIDTH = 7 → ROOT_WIDTH = 4 → PADDED_WIDTH = 8

How does padding handle an odd-width Radicand?

WorkingRemainder

The evolving partial remainder used while successive Radicand bit pairs are processed.

WorkingRoot

The evolving root value constructed one root bit per loop iteration.

TrialValue

The candidate subtraction value used to determine whether the next Root bit should become 1.

reg [PADDED_WIDTH + 1:0] WorkingRemainder

Provides the extended working width used by the square-root remainder calculations.

reg [ROOT_WIDTH - 1:0] WorkingRoot

Stores the root being progressively constructed inside the combinational algorithm.

reg [PADDED_WIDTH + 1:0] TrialValue

Stores the trial quantity compared with and potentially subtracted from WorkingRemainder.

PaddedRadicand = padded input; WorkingRemainder = 0; WorkingRoot = 0; TrialValue = 0

The initialization performed at the beginning of the combinational square-root calculation.

Why are the working variables initialized inside always @(*)?

The combinational procedure must define their starting values before the unrolled decision stages are evaluated.

for (i = ROOT_WIDTH - 1; i >= 0; i = i - 1)

The procedural loop that processes ROOT_WIDTH two-bit Radicand groups from the most-significant group toward the least-significant group.

ROOT_WIDTH iterations

How many decision stages does the IntegerSquareRoot loop execute?

Because one root bit is constructed for each two-bit group of the padded Radicand.

Why are there ROOT_WIDTH iterations?

i = ROOT_WIDTH - 1

The first loop index, corresponding to the most-significant two-bit Radicand group.

i = 0

The final loop index, corresponding to the least-significant two-bit Radicand group.

Why does the loop count downward?

The expression PaddedRadicand[(2*i) +: 2] then processes two-bit groups from the most-significant group toward the least-significant group.

(2 * i)

The starting bit index of the current two-bit Radicand group.

+: 2

A Verilog indexed part-select meaning select two bits upward starting at the calculated base index.

PaddedRadicand[(2 * i) +: 2]

Selects the two-bit Radicand group beginning at bit 2*i.

When i = 0, PaddedRadicand[(2*i) +: 2] selects bits [1:0].

Which Radicand bits are selected during the final loop iteration?

For WIDTH=8 and i=3, PaddedRadicand[(2*i) +: 2] selects bits [7:6].

Which pair is processed first for the default 8-bit design?

For WIDTH=8, the pair order is [7:6] → [5:4] → [3:2] → [1:0].

In what order does the default IntegerSquareRoot process Radicand information?

Why are Radicand bits processed in pairs?

Each square-root decision constructs one binary root bit while incorporating the next two bits of Radicand information.

WorkingRemainder = WorkingRemainder << 2

Shifts the current partial remainder left by two positions before the next Radicand pair is inserted.

Why shift WorkingRemainder by 2 rather than 1?

The algorithm brings down two Radicand bits during each root-building stage.

WorkingRemainder[1:0] = PaddedRadicand[(2 * i) +: 2]

Inserts the current Radicand pair into the two newly opened low-order positions of WorkingRemainder.

Shift left 2 → insert next Radicand pair

The operation that brings the next two bits of Radicand information into the square-root working remainder.

Why are the new Radicand bits inserted into WorkingRemainder[1:0]?

The left shift creates two empty least-significant positions specifically for the next two-bit group.

{{(PADDED_WIDTH + 2 - ROOT_WIDTH){1'b0}}, WorkingRoot}

Widens WorkingRoot with leading zeros to the width used for TrialValue arithmetic.

TrialValue = (ExtendedWorkingRoot << 2) | 1'b1

The trial quantity constructed from the current WorkingRoot before deciding the next root bit.

WorkingRoot << 2

Forms the root-dependent upper portion of the square-root trial quantity.

| 1'b1

Forces the least-significant bit of TrialValue to 1.

Why does TrialValue depend on WorkingRoot?

The validity of the next root bit depends on the root bits that have already been accepted.

WorkingRemainder >= TrialValue

The decision condition that determines whether the current trial value fits into the working remainder.

TrialValue fits

The condition in which WorkingRemainder is large enough to accept the trial subtraction.

TrialValue does not fit

The condition in which WorkingRemainder is smaller than TrialValue.

WorkingRemainder = WorkingRemainder - TrialValue

The arithmetic update performed when the trial succeeds.

WorkingRoot = (WorkingRoot << 1) | 1'b1

The root update performed when the trial succeeds, shifting previous root information and appending a new 1 bit.

WorkingRoot = WorkingRoot << 1

The root update performed when the trial fails, shifting previous root information and appending a new 0 bit.

Successful square-root trial

Subtract TrialValue from WorkingRemainder and append a 1 to WorkingRoot.

Failed square-root trial

Do not subtract TrialValue and append a 0 to WorkingRoot.

Why does a successful trial produce a Root bit of 1?

The current trial quantity fits within the available working remainder, so that root contribution can be accepted.

Why does a failed trial produce a Root bit of 0?

The current trial quantity is too large, so the candidate contribution must be rejected.

WorkingRoot << 1 creates the next root-bit position.

What purpose does the left shift of WorkingRoot serve in every iteration?

| 1'b1 appends an accepted bit of 1.

How does the successful branch record its root-bit decision?

No OR with 1 leaves the appended bit at 0.

How does the failed branch record its root-bit decision?

One Radicand pair → one trial → one Root bit

What amount of algorithmic progress occurs during each loop iteration?

Bring down pair → construct TrialValue → compare → optionally subtract → append Root bit

The conceptual sequence of one IntegerSquareRoot decision stage.

Root bits are constructed from more-significant decisions toward less-significant decisions.

In what conceptual direction is WorkingRoot built?

Why must earlier WorkingRoot bits influence later TrialValue calculations?

The validity of each new root bit depends on the partial root already constructed.

Root = WorkingRoot

The final assignment that exposes the completely constructed working root.

Remainder = WorkingRemainder[WIDTH - 1:0]

The final assignment that exposes the lower WIDTH bits of the completed working remainder.

Combinational Integer Square Root

This implementation evaluates all ROOT_WIDTH decision stages as one combinational logic network.

Why is this IntegerSquareRoot combinational rather than multi-cycle?

It contains no posedge-triggered state registers; the entire algorithm is described inside always @(*) and the procedural loop is evaluated as combinational logic.

Does the for loop mean the circuit waits one clock cycle per iteration?

No. In this RTL the procedural loop describes repeated combinational hardware/logic evaluation rather than clocked temporal iterations.

Procedural Loop in Combinational RTL

A coding construct that can describe multiple repeated logic stages without implying multiple clock cycles.

Why is this distinction important?

A loop in Verilog does not automatically mean hardware reuses one arithmetic unit over time; the surrounding RTL structure determines whether the implementation is combinational or sequential.

Unrolled Decision Stages

A hardware interpretation in which the repeated algorithmic steps are represented within one combinational path rather than reused across multiple clock cycles.

Iterative Algorithm vs. Iterative Microarchitecture

An algorithm may consist of repeated decisions even when the chosen RTL architecture unrolls those decisions combinationally instead of executing them across cycles.

Why can IntegerSquareRoot still teach iterative arithmetic even though this implementation is combinational?

The mathematical algorithm is decomposed into repeated state-like transformations, but the RTL chooses to unroll those transformations within one combinational evaluation.

Combinational Unrolling

Implementing repeated algorithm stages spatially so the complete result can be produced without clocked iteration.

Temporal Reuse

Reusing a smaller datapath across multiple clock cycles to execute successive algorithm iterations.

Combinational vs. Multi-Cycle Square Root

The same mathematical square-root algorithm can be implemented using more combinational hardware or by reusing arithmetic structures across clock cycles.

What determines whether square root should be combinational or multi-cycle?

Area, timing, latency, and implementation goals rather than the mathematical square-root specification alone.

Why can a combinationally unrolled square root have a longer critical path?

Multiple dependent compare/subtract decision stages may have to propagate through the combinational network before Root becomes valid.

Why might a multi-cycle square-root implementation use less hardware?

It can reuse a smaller set of arithmetic structures across successive clock cycles instead of spatially representing the repeated stages.

Arithmetic Function ≠ Fixed Architecture

A mathematical operation such as square root does not uniquely determine whether its hardware must be combinational or iterative across clock cycles.

Advanced Arithmetic as Simpler Decisions

The design principle that an apparently complex arithmetic operation can often be decomposed into shifts, comparisons, additions/subtractions, and repeated decisions.

Square Root as Decision Construction

The result is progressively determined by testing whether each candidate root contribution can be accepted.

Division vs. Integer Square Root

Division constructs quotient information through repeated remainder decisions, while square root constructs root information through repeated trial decisions.

Division: one quotient-bit decision per iteration

How does iterative division construct its result?

Square Root: one root-bit decision per stage

How does this square-root algorithm construct its result?

Partial Remainder in Division

Working information that carries the consequences of earlier quotient decisions into later division steps.

WorkingRemainder in Square Root

Working information that carries the consequences of earlier root decisions into later square-root stages.

TrialRemainder in Division

A tentative divisor subtraction used to determine a quotient bit.

TrialValue in Square Root

A root-dependent candidate value used to determine a root bit.

Both division and square root turn arithmetic into repeated yes/no decisions.

What architectural similarity connects the two major Part 06 arithmetic examples?

Because a complex numerical result can emerge from a sequence of simpler comparisons and conditional arithmetic updates.

Why are division and square root useful examples of iterative arithmetic?

When an arithmetic operator looks advanced, ask what sequence of simpler decisions could construct its result.

What designer mental model does the IntegerSquareRoot example reinforce?