Computing Integer Square Root with Binary Shifts

An integer square root algorithm calculates the greatest integer less than or equal to the square root of a given non-negative integer. This article explains the mechanics of computing exact integer square roots using a digit-by-digit binary method, detailing how bitwise shifts, remainder tracking, and binary subtraction determine each bit of the final result without relying on costly floating-point operations.

What Is an Integer Square Root?

The integer square root of a non-negative integer \(n\), often denoted as \(\lfloor\sqrt{n}\rfloor\), is the largest integer \(r\) such that:

\[r^2 \le n < (r + 1)^2\]

In software systems, especially on microcontrollers, embedded hardware, or cryptographic engines without a dedicated Floating-Point Unit (FPU), computing square roots via floating-point approximation introduces performance overhead and rounding errors. Integer square root algorithms solve this problem by operating strictly within discrete integer domains.

The Principle of the Binary Bit-by-Bit Method

The binary bit-by-bit algorithm is the base-2 adaptation of the traditional pen-and-paper long division method for finding square roots.

In base 10, numbers are grouped into pairs of digits starting from the decimal point. In base 2, bits are processed in pairs (2 bits at a time) from the most significant bits down to the least significant bits. This 2-to-1 relationship exists because squaring a number doubles its bit length:

\[(2^k)^2 = 2^{2k}\]

At each step, the algorithm determines the next bit of the root (either 0 or 1). Because binary only has two possible digits, the decision does not require estimating a quotient digit; it only requires a single test to determine if the next bit can be a 1.

Mathematical Formulation

Let \(r\) be the partial root computed so far. When shifting to the next bit, the current root becomes \(2r\).

If the next bit to append is 1, the new root candidate is \((2r + 1)\). The difference between the square of the new candidate and the square of the previous base is:

\[(2r + 1)^2 - (2r)^2 = 4r + 1\]

Therefore, to test whether the next bit of the root is 1, the algorithm shifts the current remainder to include the next two bits of the input, and then checks if the remainder is greater than or equal to \((4r + 1)\).

• If Remainder \(\ge 4r + 1\): The next root bit is 1. Subtract \((4r + 1)\) from the remainder, and update the root to \((2r + 1)\).
• If Remainder \(< 4r + 1\): The next root bit is 0. The remainder remains unchanged, and the root updates to \(2r\).

Step-by-Step Algorithm Execution

1. Initialization:
   • Set the remainder register to 0.
   • Set the root register to 0.
   • Determine the highest power-of-four mask less than or equal to \(n\) (or iterate through bit pairs from MSB to LSB).
2. Loop Iteration (for each 2-bit pair):
   • Shift the remainder left by 2 bits.
   • Bring down the current 2 bits of the input number and add them to the remainder.
   • Shift the current root left by 1 bit.
   • Compute the trial value: test_value = (root << 1) + 1.
   • If remainder >= test_value:
     • remainder = remainder - test_value
     • root = root + 1
3. Termination:
   • Once all bit pairs from the input are processed, the root variable contains \(\lfloor\sqrt{n}\rfloor\), and the remainder variable contains \(n - r^2\).

Example: Computing \(\lfloor\sqrt{27}\rfloor\)

The decimal value 27 in 6-bit binary is 01 10 11\(_2\) (grouped in pairs). The expected root is 5 (101\(_2\)) with a remainder of 2.

• Step 1 (Bits: 01):
  • Remainder becomes 01\(_2\) (1).
  • Root is 0. Test value: (0 << 1) + 1 = 1.
  • Since \(1 \ge 1\): Remainder \(= 1 - 1 = 0\), Root becomes 1.
• Step 2 (Bits: 10):
  • Remainder becomes 00 shifted left by 2 plus 10\(_2 = 2\).
  • Root is 1 (shifted candidate: root << 1 = 2). Test value: (1 << 1) + 1 = 3.
  • Since \(2 < 3\): Remainder stays \(2\), Root becomes 10\(_2\) (2).
• Step 3 (Bits: 11):
  • Remainder becomes 2 shifted left by 2 plus 11\(_2 = 11\).
  • Root is 2 (10\(_2\)). Test value: (2 << 1) + 1 = 5 (101\(_2\)).
  • Since \(11 \ge 5\): Remainder \(= 11 - 5 = 6\) (or \(1011_2 - 1001_2 = 2\)).
  • Root becomes 101\(_2\) (5).

Final result: Root is \(5\), with a final remainder of \(2\).

Computational Advantages

The binary shift-based integer square root algorithm requires only basic arithmetic and logical operations: left shifts, additions, subtractions, and comparisons. It executes in deterministic \(O(b)\) time, where \(b\) is half the number of bits in the input integer, making it highly efficient for hardware logic, DSP applications, and low-level firmware.