A Piecewise-Linear Approximation-based Energy-Efficient Error-Optimized Unsigned Square Rooter for Accuracy-Critical Applications

Prateek Goyal; Sujit Kumar Sahoo

Source-linked AI summary

A Piecewise-Linear Approximation-based Energy-Efficient Error-Optimized Unsigned Square Rooter for Accuracy-Critical Applications

Prateek Goyal, Sujit Kumar Sahoo

arXiv:2609.04783v1Sep 4, 2026cs.AReess.IV

TL;DR

Accuracy-critical applications need square-root hardware that avoids the usual trade-off between numerical accuracy and resource efficiency. The paper proposes EOSQR, an error-optimized piecewise-linear unsigned square rooter, and evaluates it with FPGA metrics, CEM, and application workloads. EOSQR achieves high accuracy with lower hardware cost and power-delay product than comparable designs while reducing resource use, power, and latency relative to ERAS.

Problem
Existing square-root designs force a trade-off between hardware efficiency and computational accuracy, limiting their use in accuracy-sensitive applications.
Method
EOSQR uses a piecewise-linear, analytically error-optimized approximation framework and is evaluated through FPGA implementation, CEM analysis, and application workloads.
Results
EOSQR achieves the lowest reported error metrics among evaluated approximate designs while reducing dynamic power by 77.54%, LUT utilization by 61.91%, and latency by 53.11% versus ERAS.
Takeaways & Limitations
EOSQR improves the accuracy–efficiency trade-off and maintains practical image-processing and machine-learning applicability across Sobel, K-means, and KNN workloads.
Takeaways & Limitations
The paper's motivation identifies scalability, area, delay, and power penalties as boundary concerns for conventional restoring-array and accuracy-focused designs.

Abstract

from arXiv · show

Approximate computing improves energy efficiency in error-resilient applications, but square root units remain challenging due to the trade-off between hardware cost and computational accuracy. This paper presents an energy-efficient, error-optimized, piecewise-linear approximation-based unsigned square rooter (EOSQR) for 2n-bit inputs that achieves high accuracy with low hardware complexity, using only simple arithmetic and shift operations. The EOSQR design is implemented in Verilog-HDL and evaluated on a 16-bit benchmark synthesized on an Artix-7 FPGA. Compared to representative state-of-the-art approximate square rooters, EOSQR achieves the lowest error among accuracy-critical designs while delivering 61.91 percent resource savings, 77.54 percent power savings, and 53.11 percent latency reduction relative to a precise restoring array-based square rooter. To enable holistic evaluation, a Composite Efficiency Metric (CEM) is introduced to jointly capture accuracy and energy efficiency. EOSQR is further validated across representative image-processing workloads, including Sobel edge detection, K-means colour quantization, and K-nearest-neighbour (KNN) classification. Experimental results demonstrate that EOSQR achieves high computational accuracy with a superior CEM-based accuracy-hardware efficiency trade-off while maintaining visual quality and classification performance, making it well-suited for real-time edge-embedded systems.

I. Introduction

Approximate square-root designs must balance numerical accuracy against hardware efficiency for accuracy-sensitive workloads. The paper proposes EOSQR as a piecewise-linear, error-optimized design evaluated through hardware metrics, CEM, and image-processing and machine-learning applications.

Motivation: Approximate square rooters trade computational accuracy against hardware efficiency, especially in accuracy-critical applications.Existing designs may reduce cost by introducing controlled inaccuracies, while accuracy-focused approaches can increase hardware complexity, power, and delay.
Existing approaches: Restoring-array methods provide accurate computation but incur substantial hardware overhead and scale poorly with operand width.Their iterative subtract-and-restore structure can increase area, switching activity, critical-path delay, and power.
Existing approaches: Series-expansion methods reduce complexity through shift-and-add operations but exhibit larger and non-uniform approximation errors.Their errors include continuity mismatches at interval boundaries and deviations near transition points, limiting suitability for accuracy-critical applications.
Proposed approach: EOSQR introduces a piecewise-linear, error-optimized approximation framework designed to achieve near-accurate results with low hardware complexity.The framework uses analytical optimization, while the implementation is evaluated with standard accuracy and hardware-efficiency metrics.
Evaluation: The paper evaluates EOSQR with a Composite Efficiency Metric and practical workloads including Sobel edge detection, K-means clustering, and KNN classification.These evaluations examine the accuracy–efficiency trade-off and practical applicability across image-processing and machine-learning tasks.

II. Piecewise-Linear Approximation via Error Optimization for Proposed Square Rooter

The proposed square-rooter uses endpoint-matched piecewise-linear interpolation over normalized leading-one intervals, with parameters determined by error optimization. Its interval-invariant formulation scales across unsigned 2n-bit inputs, while implementation adjustments preserve shift-based efficiency for odd r.

Approximation framework: A 2n-bit unsigned input M is decomposed into its leading power-of-two component 2^r and residual y, where 0 ≤ y < 2^r.The leading-one position r identifies the interval, and y is the remainder within it.
Error optimization: The approximation error is minimized by choosing intercept b_r and slope m_r so the linear model matches the square-root function at both interval endpoints.Endpoint matching preserves continuity between successive piecewise-linear segments.
Piecewise interpolation: The square-root curve is represented by linear interpolation between successive interval boundaries, producing an efficient piecewise approximation.The geometric construction maps each input interval to its corresponding square-root output range.
Scalability: The formulation depends on the normalized interval and leading-one position rather than absolute operand magnitude, enabling uniform application across all unsigned 2n-bit numbers.This interval-invariant structure supports scalability to arbitrary word lengths.
Implementation considerations: Odd r requires additional implementation handling because fractional exponents cannot be realized directly with shift-and-add operations alone.The design therefore uses suitable shift-based strategies while approximating the constant factor needed for multiplier-free computation.

1) Energy-Efficient Adjustments for Even r:

For even r, the constant factor in the optimized approximation is replaced with a dyadic approximation suitable for shift-and-add hardware. The overestimation option is selected because it more closely represents the target constant.

Even-r adjustment: The constant factor (√2 − 1) ≈ 0.4142 is approximated using dyadic fractions so multiplication requires only shifts and additions.This preserves a multiplier-free implementation for even r.
Even-r adjustment: The overestimation approximation is selected because it provides a closer representation of the constant factor.

Average Error Introduced Due to Implementation:

The implementation-error analysis evaluates the discrepancy introduced by the feasible hardware realization of the even-r approximation over each line segment.

Implementation error: The implementation error is defined between the proposed linear approximation and the feasible hardware implementations over a line segment of length 2^r.The stated error measure applies to even values of r.
Implementation error: Odd r cannot directly use the fractional exponent 2^(r/2) with shift operations, motivating a reformulation for efficient realization.

2) Energy-Efficient Adjustments for Odd r:

For odd r, the approximation is reformulated to eliminate fractional exponents and then decomposed into terms that can be implemented with shifts and additions. Dyadic choices are selected to compensate opposing approximation errors and preserve continuity.

Odd-r adjustment: The odd-r expression contains two terms that are approximated separately to enable energy-efficient hardware implementation.This decomposition supports realization using shifts and additions only.
Odd-r adjustment: The first term uses an approximation of the relevant square-root factor, with a level shift compensating the r−1 reformulation for magnitude consistency and continuity.
Odd-r adjustment: The second-term constant multiplier is approximated with dyadic fractions so it can be implemented using simple shift-and-add operations.
Odd-r adjustment: For the odd-r slope adjuster, practical dyadic approximations are evaluated for the factor approximately equal to 0.5857.
Odd-r adjustment: Because the first-term approximation slightly overestimates, an underestimation is selected for the second term to compensate the overall approximation error.

Average Error in Second Term Due to Implementation:

The approximation combines terms whose errors largely neutralize, producing a final square-root estimate over the target interval.

The first- and second-term errors largely neutralize, yielding an overall average error in the range [2r, 2r+1).

3) Overall Energy-Efficient Approximation:

EOSQR decomposes square-root computation into a power-of-two base and residue-dependent correction, using shift-and-add operations for an efficient piecewise-linear approximation.

The approximation decomposes square-root computation into a dominant power-of-two base term and a residue-dependent correction component.
The correction factors adjust the slope for even and odd r, compensating for linearization errors and enabling partial error cancellation.
Shift-and-add operations provide an efficient piecewise-linear approximation with low hardware complexity and FPGA-oriented suitability.

A. Architectural Design Flow of the Proposed Square Rooter

EOSQR detects the input’s leading-one position and residual, selects an even or odd computation path, and uses lightweight combinational hardware to produce an accurate approximation.

The leading-one detector and priority encoder determine r, while a subtractor computes the residual y = M − 2^r.
The selector checks r[0] to activate the even or odd computation path.
EOSQR uses shifters, adders, subtractors, and decoders while avoiding multipliers and iterative operations.
For input 32767, EOSQR outputs 184 versus the exact square root 181, producing an error distance of 3.

III. Results and Discussion

EOSQR is evaluated against exact and approximate square rooters using FPGA implementation metrics, exhaustive 16-bit accuracy measures, graphical comparisons, and a composite efficiency analysis.

EOSQR is compared with ERAS and state-of-the-art approximate designs using the Composite Efficiency Metric to assess accuracy-hardware trade-offs.
For fair comparison, tunable designs select t for comparable error levels, while LESQ-EC, OLSR, TSOSQR, and EOSQR have no tunable t.
For 16-bit inputs from 1 to 65535, EOSQR closely follows the exact square-root curve with minimal deviation and lower hardware complexity.
EOSQR achieves the lowest NMED, MRED, MED, EDmax, and MSE among evaluated approximate designs.
EOSQR reduces dynamic power by 77.54%, LUT utilization by 61.91%, and latency by 53.11% relative to ERAS.
Series-expansion designs reduce hardware cost but exhibit degraded numerical accuracy, whereas EOSQR reports NMED = 0.4741×10^-2, MRED = 0.7447×10^-2, MED = 1.2091, and EDmax = 3.

D. Trade-off Evaluations using Composite Efficiency Metric (CEM)

The Composite Efficiency Metric (CEM) combines accuracy, energy efficiency, and hardware cost to compare approximate square rooters. EOSQR is presented as offering a strong accuracy–efficiency balance for real-world workloads.

CEM integrates accuracy, energy efficiency, and hardware cost into a unified square-rooter evaluation metric.ACM captures error behavior, while HWM reflects logic utilization and power-delay characteristics.
MRED and EDmax capture average and worst-case error, while LUT count and PDP represent resource use and energy efficiency.Together, these dimensions assess both computational precision and implementation cost.
A higher CEM indicates stronger average and worst-case accuracy with lower resource and timing overhead.The metric is intended to identify designs that balance precision and hardware efficiency.
EOSQR achieves a superior CEM-based accuracy-efficiency trade-off compared with existing 16-bit square rooters.The evaluation considers accuracy alongside power, latency, and resource utilization.
The evaluated workloads include Sobel edge detection, K-Means color quantization, and KNN classification.These applications assess EOSQR across image-processing and machine-learning scenarios.

A. Edge Detection

EOSQR is evaluated in Sobel edge detection, K-Means color quantization, and KNN classification using approximate square-root computation. The reported results indicate preserved image quality and classification performance across these workloads.

Edge Detection: Sobel edge detection evaluates approximate 16-bit square rooters against an exact implementation using MATLAB–HDL co-simulation.The square root computes gradient magnitude from horizontal and vertical Sobel components.
Edge Detection: EOSQR achieves the highest average PSNR of 50.19 dB and average SSIM of 0.984 among the competing methods.The metrics use exact square-root output as the reference across six 8-bit grayscale images.
K-Means Clustering: K-Means color quantization benchmarks EOSQR during Euclidean-distance computation for clustering and image compression.The evaluation uses a 25-color reconstruction of the Peppers image over five iterations.
K-Means Clustering: EOSQR produces the highest K-Means reconstruction quality, with PSNR of 30.21 dB and SSIM of 0.862.The reported results identify EOSQR as the best-performing square-rooter in this color-quantization evaluation.
KNN Classification: In KNN classification, EOSQR achieves 8.6% accuracy versus 8.7% for the exact implementation, a 0.10% reduction.The study reports lower error metrics than AXSR3-10 and MAHSQR-4 alongside improved delay, power, and logic utilization.
Cross-Workload Findings: The conclusion reports that EOSQR maintains high visual fidelity and classification accuracy while jointly improving accuracy and energy efficiency.These findings cover edge detection, K-Means color quantization, and KNN classification workloads.