METHOD FOR SQUARE ROOT COMPUTATION USING OPTIMIZED ARITHMETIC FOR HIGH-SPEED AND LOW-POWER APPLICATIONS

Abstract

ABSTRACT The present invention relates to a hardware-implemented method for square root computation. The method segments input numbers into predefined ranges, utilizes lookup tables for perfect squares, and employs addition and subtraction operations instead of division. This approach ensures high computational speed and low power consumption, making it ideal for embedded systems, signal processing, and real-time applications. The method leverages Binary Coded Decimal (BCD) conversion, range identification, and iterative refinement to achieve precise square root calculations with minimal resource usage. Figure 2.

Specification

Description:METHOD FOR SQUARE ROOT COMPUTATION USING OPTIMIZED ARITHMETIC FOR HIGH-SPEED AND LOW-POWER APPLICATIONS

FIELD OF THE INVENTION
The present invention relates to a method for square root computation, emphasizing hardware implementation to achieve high computational speed and low power consumption. More specifically, the present invention relates to a method that addresses the inefficiencies of traditional algorithms by introducing optimized arithmetic techniques that eliminate the need for division and multiplication, making the method suitable for resource-constrained environments such as embedded systems, real-time processing, mobile devices, and image and signal processing.

BACKGROUND OF THE INVENTION
Square root computation is a fundamental mathematical operation utilized in various domains, including signal processing, scientific computing, and control systems. The ability to compute square roots efficiently is critical in applications where accuracy, speed, and power efficiency are paramount. Traditional methods, while effective, often struggle to meet these performance requirements in hardware-constrained environments.
Historically, square root computation relied on software-based algorithms such as Newton-Raphson and binary search. These techniques, although widely adopted, involve iterative calculations and division operations that increase computational time and energy consumption. Such approaches are less effective in real-time applications requiring rapid data processing.
Hardware-based implementations have emerged to address these challenges, providing faster computation compared to software methods. However, these implementations often come at the cost of increased complexity, greater hardware resource utilization, and higher power consumption, making them less suitable for embedded systems or mobile devices with stringent energy constraints.
The need for a hardware method that optimizes speed without sacrificing energy efficiency has become apparent. Traditional approaches frequently prioritize computational accuracy but fail to balance power efficiency and real-time responsiveness. This gap necessitates the development of innovative techniques to streamline square root computation while reducing resource demands.
The present invention introduces an optimized method for square root computation, inspired by ancient Vedic Mathematics. By eliminating division and multiplication and utilizing addition and subtraction operations, this method addresses the limitations of existing approaches. The invention achieves faster computation, lower power consumption, and reduced hardware complexity, offering a robust solution for modern applications.

SUMMARY OF THE INVENTION
The present invention relates to a method for square root computation that leverages optimized arithmetic operations for hardware implementation. The method is based on segmenting input numbers into predefined ranges and using lookup tables for perfect squares to streamline computation. This approach eliminates the need for division operations, relying instead on addition and subtraction to determine square roots efficiently.
In one embodiment, the present invention relates to a method that begins by converting input values into Binary Coded Decimal (BCD) format for efficient processing. It identifies the range of the input value, retrieves boundary values, and determines the square root through iterative addition or subtraction. This novel technique not only reduces computational complexity but also minimizes power usage, making it ideal for embedded systems, signal processing, and mobile applications.

BRIEF DESCRIPTION OF THE DRAWINGS
Figure 1 illustrates the block diagram of the proposed method.
Figure 2 illustrates the general framework of the proposed method.
Figure 3 depicts the flowchart of the proposed method.
Figure 4 shows the RTL view of conventional square root method.
Figure 5 shows the RTL view of proposed square root method.
Referring to the drawings, the embodiments of the present invention are further described. The figures are not necessarily drawn to scale, and in some instances the drawings have been exaggerated or simplified for illustrative purposes only. One of ordinary skill in the art may appreciate the many possible applications and variations of the present invention based on the following examples of possible embodiments of the present invention.

DETAILED DESCRIPTION OF THE INVENTION
The following description outlines various embodiments of the invention for illustrative purposes, without limiting its scope. Skilled persons in the field will appreciate that other configurations may also fall within the scope of this disclosure. Terms used herein carry their standard meanings in the relevant field, and synonyms may be used interchangeably. Examples provided are illustrative and do not limit the scope of the invention.
The present invention relates to a hardware-optimized method for computing square roots, specifically designed for high-speed and low-power applications. Traditional methods, which often rely on iterative calculations and division and multiplication operations, result in significant computational overhead and power consumption. This invention overcomes such limitations by employing a novel process that replaces division and multiplication with simple arithmetic operations, namely addition and subtraction. The method is particularly suited for embedded systems, real-time computing environments, and applications demanding minimal energy consumption.
The process begins by converting the input value into Binary Coded Decimal (BCD) format. This format simplifies the computational steps and ensures compatibility with the hardware system. Once the input is converted, it is analyzed to determine whether it falls into a predefined range of numbers. This segmentation is central to the invention's efficiency, as it narrows the scope of computation to a manageable subset of values.
For perfect squares, the invention leverages a lookup table containing precomputed square roots for numbers from 1 to 25. This table allows for instantaneous retrieval of square root values, significantly reducing computation time. For non-perfect squares, the computation is done by checking whether the input number lies within the predecessor and successor square root values, and an approximation of the result is obtained.
The next stage of the process involves verifying the input number's position within the identified range. A comparator module evaluates whether the input exceeds or falls below the midpoint of the range. If the number exceeds the midpoint, the method adds the square root value of the input number to the base value. Conversely, if the number is below the midpoint, the method subtracts the square root value of the input number from the base value.
To ensure accuracy, the method employs iterative refinement steps. These iterations adjust the computed value by analyzing residual differences until the desired precision is achieved. The refined result is then output in BCD format for further processing or display.
The invention also incorporates specific handling for numbers ending in unique digit patterns. For example, numbers ending in 1, 4, 6, or 9 require only the last two digits to be evaluated. For numbers ending in 0 or 5, the last three digits are analyzed. This targeted approach reduces unnecessary calculations, enhancing overall efficiency.
In hardware implementations, the system includes key modules such as comparators, adders, subtractors, and Block Random Access Memory (RAM). The Block RAM stores the lookup table for quick access to precomputed values. The addition and subtraction operations are carried out by dedicated arithmetic units designed for minimal delay and power consumption.

Method for computing square roots
The computation process begins with an Initial Module that converts the input number to Binary Coded Decimal (BCD) for efficient processing, as shown in Figure 1. Following this, a digit verification module examines the digits of the input number. If the input number ends in 1, 4, 6, or 9, this module examines only the last two digits, and if the number ends in 5 or 0, the module examines the last three digits to ensure accurate computation. After verifying the relevant digits, the data retrieval module retrieves the exact address of these digits from Block RAM (Random Access Memory) and directs the outputs to the Adder-Subtractor module. The range module checks if the input number falls within a predefined range limit. If the input meets this criterion, it is passed to the Comparator Module, where it is evaluated against the specified range. Depending on whether the input exceeds or falls below the base value, the Adder-Subtractor module performs addition or subtraction, refining the result for efficient square root calculation.
Thus the proposed method determines the square root of the perfect square numbers by applying the below rule:
To find the square root of perfect squares not directly available in the lookup table, the process involves segmenting the squared values into groups of 50. Within each segment, the midpoint is designated as the base value. If the given number lies in the first half of the segment, which is below the base value, the square root value obtained from the lookup table is subtracted from the base value. Conversely, if the number falls in the second half of the segment, the base value is added to the square root value obtained from the lookup table, following a specific set of rules. First, the last digit of the given number is checked to determine if it is 1, 4, 6, 9, 0, or 5. If the last digit is 1, 4, 6, or 9, the last two digits of the given number are referred to in the lookup table to find the corresponding square root value. If the last digit is 0 or 5, the last three digits of the number are used instead to retrieve the square root value from the lookup table. Figure 2 illustrates the given number is greater or lesser than the midpoint (base value).
This process applies to decimal values, especially perfect squares, where the last two digits are examined. The method proposed in the present invention enables efficient square root computation without conventional division, streamlining the process and reducing computational load.
Table 1: Square of numbers from 1-25
12 =01 62=36 112=121 162=256 212=441
22 =04 72=49 122=144 172=289 222=484
32=09 82=64 132=169 182=324 232=529
42=16 92=81 142=196 192=361 242=576
52=25 102=100 152=225 202=400 252=625
Table 1 illustrates perfect square numbers from 1 to 25. For each square value, the last two digits are used as a reference to calculate the final answer. Below are examples that clarify this method, specifically for numbers ending in 1, 4, 6, and 9.

Elucidation 1:
Below the Base value
Evaluate the square root of 6241.
Since the number ends in 41, its square root is 21. Given that 6241 is less than the base of 10000, we subtract:
100-21= 79.
(75)2−−−−−−−−−−−−−−−−−−−−(100)2−−−−−−−−−−−−−−−−−−(125)2
5625−−−−−−−−−−−−−−−−−−−−−10000 −−−−−−−−−−−−−−−−−−−15625

Elucidation 2:
Below the Base value
Evaluate the square root of 2304.
For a number ending in 04, the square root is 2. As 2304 is less than 2500. Subtract the square root of 04 from the base value 2500.
50-2= 48.
(25)2−−−−−−−−−−−−−−−−−−−−(50)2 −−−−−−−−−−−−−−−−−−(75)2
625−−−−−−−−−−−−−−−−−−−−−2500 −−−−−−−−−−−−−−−−−−−5625

Elucidation 3:
Above the Base value
Evaluate the square root of 4096.
The number ends in 96, so the square root is 14. Since 4096 is greater than 2500:
50+14= 64.
(25)2−−−−−−−−−−−−−−−−−−−−(50) 2 −−−−−−−−−−−−−−−−−−(75)2
625−−−−−−−−−−−−−−−−−−−−−2500 −−−−−−−−−−−−−−−−−−−5625

Elucidation 4:
Below the Base value
Evaluate the square root of 8649.
As the number ends in 49, the square root is 7. With 8649 being less than 10000:
100-7= 93.
(75)2−−−−−−−−−−−−−−−−−−−−(100)2−−−−−−−−−−−−−−−−−−(125)2
5625−−−−−−−−−−−−−−−−−−−−−10000 −−−−−−−−−−−−−−−−−−−15625

For numbers ending in 5 or 0, the method requires evaluating the last three digits:
Elucidation 5:
Above the Base value
Evaluate the square root of 13225.
With the last three digits being 225, the square root is 15. Since 13225 is greater than 10000:
100+15=115
(75)2−−−−−−−−−−−−−−−−−−−−(100)2−−−−−−−−−−−−−−−−−−(125)2
5625−−−−−−−−−−−−−−−−−−−−−10000 −−−−−−−−−−−−−−−−−−−15625

Elucidation 6:
Below the Base value
Evaluate the square root of 35721.
For a number ending in 21, the square root of 11 is used, as the square of 11 ends with 21. Given that 35721 is less than 40000:
200-11=189
(175)2−−−−−−−−−−−−−−−−−−−−(200)2−−−−−−−−−−−−−−−−−−(225)2
30800−−−−−−−−−−−−−−−−−−−−−40000 −−−−−−−−−−−−−−−−−−−50625

Hardware-Based Process for Optimized Square Root Calculation
1. Input Capture Module: Collect values for the necessary variables from the user or an external input source.
2. Perfect Square Verification Module: The system evaluates whether the input value is a perfect square.
3. Range Identification Module: The range within which the input value resides is determined by the system's logic.
4. Boundary Retrieval Module: The system obtains the lower and upper boundary values of the identified range.
5. Position Initialization: The location variable is initialized to '1' to indicate the start of processing.
6. Range Check and Calculation: If the starting range is less than or equal to the ending range, the following calculations are performed:
• Numerator Calculation: Compute the difference between the end-range and start-range values.
• Fixed Scaling Division: Set a denominator constant of 100.
• Middle Value Calculation: Divide the Numerator by the Denominator to determine the Middle Value; if the range check fails, the Middle Value is set to 0.
7. Base Comparison Logic:
• For inputs less than the base and ending in 5 or 0, the output is computed as the Middle Value minus the square root of the last three digits.
• For other values, the output is derived by subtracting the square root of the last two digits from the Middle Value.
Figure 3 outlines the said method for calculating square roots without using division and multiplication, employing a flowchart to guide the computation. The method includes:
1. Initialization: The process begins with an input perfect square number and two range boundaries-625 (lower limit) and 5625 (upper limit).
2. Range Examination: The input number is examined recursively to verify if it falls within this range. If so, the algorithm compares the input against these boundaries to understand its relative position within the range.
3. Computation of Median: The middle value of the range, which is set to 50 (corresponding to the square root of 2500), is used as a reference. For numbers within this range, this median assists in estimating the square root.
4. Addition and Subtraction: Based on whether the input number exceeds or is below the calculated midpoint, the square root is computed through addition or subtraction operations rather than traditional division.
Thus the method is efficient for perfect square inputs, leveraging comparison-based steps and range segmentation, which are beneficial for hardware implementation in low-power and high-speed applications, as shown in your document. The elimination of division and multiplication operations in favor of addition and subtraction provides both speed advantages and power savings.

Simulation and Verification of the Method
The method described leverages Altera Quartus-II and Verilog HDL to simulate and verify the effectiveness of a hardware-based square root computation method versus the traditional long division approach. Here's a breakdown of the process:
1. Simulation Setup: The simulation was executed in Altera Quartus-II, specifically using the CYCLONE IV GX family with device model EP4CGX15BF14C6. This device is suitable for optimizing speed and power performance, making it ideal for testing the proposed method.
2. Implementation Techniques:
• Traditional Method: Implemented using the long division algorithm, where Verilog HDL was employed to model the square root calculation. The RTL (Register Transfer Level) view, shown in Figure 4, provides a visualization of how data flows through various sub-modules.
• Proposed Method: The new technique utilizes Vedic mathematical principles to compute square roots without division and multiplication, relying on comparison and arithmetic operations (addition/subtraction) alone. This configuration optimizes speed and reduces power requirements, as demonstrated by RTL visualization.
3. Comparison and Results:
• Sub-Modules: The data path and controller were developed as sub-modules in Verilog, where each performs distinct roles in executing the square root calculation.
• Performance Metrics: The proposed method achieved better performance metrics compared to the traditional method, reducing logic usage and dissipating less power. The RTL perspectives illustrate how these methods manage data and computational resources differently, confirming the proposed method's advantage in real-time and embedded applications.
The simulation results affirm that the proposed method significantly outperforms the traditional long division approach in both speed and energy efficiency, which is crucial for high-speed, low-power applications.
The proposed method for square root computation, implemented in Verilog HDL, is structured using several specialized sub-modules to optimize both accuracy and efficiency in hardware. The key components involved in the square root calculation are:
1. Comparator: This module is essential for comparing the input number against predefined ranges to determine the necessary calculations. It helps ascertain if the input exceeds or falls below a base value within each range, guiding the addition or subtraction operations.
2. Range Module: This module categorizes the input based on specific ranges, allowing for efficient handling of numbers within certain intervals (e.g., perfect squares within predefined segments). By structuring inputs into ranges, the process achieves faster computation by minimizing the need for extensive calculation across broader ranges.
3. LSB Digit Checker: This module examines the last two least significant bits (LSBs) of the input number. For inputs ending in particular digits (such as 1, 4, 6, or 9), specific calculations are performed to improve accuracy, especially for perfect squares.
4. Block RAM (Random Access Memory): This component is used to store key data values for efficient retrieval during calculations. The RAM holds fixed values associated with perfect squares, optimizing speed and reducing real-time computation demands.
5. Binary to BCD Converter: Converts binary input values to Binary Coded Decimal (BCD) format. This conversion is crucial for simplifying and organizing the computation steps, as BCD enables better handling of decimal data in the hardware.
6. Adder-Subtractor Module: Based on the input's comparison results, this module either adds or subtracts values to achieve the square root estimation. This functionality allows the system to avoid traditional division-based calculations, which saves time and energy.
Each of these modules was crafted and combined within the Verilog HDL framework, with their interactions visualized in the RTL (Register Transfer Level) view in Figure 5. This configuration facilitates an efficient square root estimation while minimizing resource utilization, making it particularly suitable for high-speed and low-power applications. The use of Verilog's modular approach allows for the flexible integration of each component, thereby maximizing performance and scalability.

Synthesis Reports and Hardware Resource Utilization
The synthesis reports for both the traditional square root approach and the proposed square root method provide insights into the hardware resources utilized during their implementation. The comparison made based on Tables 2 and 3.
Table 2: Synthesis Report of Conventional Square root method
S.No. Parameters Total
1. Combinational Functions 392/14400 (3%)
2. Logic Registers 71/14400 (1%)
3. Total Pins 34/81 (42%)

• Logic Elements: 392 out of the available elements were used, representing a higher resource demand.
• Registers: 71 registers were required to store intermediate values, indicating a more complex structure.
• Pins: 34 pins were utilized, a significant allocation of I/O resources, reflecting the approach's demand on hardware.
Table 3: Synthesis Report of the proposed Square root method
S.No. Parameters Total
1. Combinational Functions 150/14400 (1%)
2. Logic Registers 51/14400 (0.3%)
3. Total Pins 23/81 (28%)

The proposed method significantly optimized resource use:
• Logic Elements: Only 150 were used, a reduction compared to the traditional method, highlighting a more streamlined design.
• Registers: 51 registers were used, further indicating efficiency in handling intermediate values.
• Pins: Only 23 pins were required, reducing the load on I/O resources.
These metrics confirm that the proposed square root method is more efficient, with fewer logic elements, registers, and pins used. This optimization is crucial for applications where space, power, and processing speed are limited, showcasing the method's advantages for real-time and embedded systems.
The synthesis reports for the conventional and the proposed square root methods indicate key improvements in logic utilization and power efficiency. A detailed breakdown based on Tables 3, 4, and 5 are provided below.
Power Dissipation Analysis
The estimated power dissipation for both methods was analyzed to evaluate their energy efficiency.
• Logic Elements: The square root method uses only 150 logic elements, demonstrating a 2% improvement over the traditional method. This reduction highlights the efficiency gained by eliminating complex operations like division.
• Pins: The method requires just 23 pins, reducing the hardware footprint and making it more adaptable for resource-constrained environments.
Table 4: Estimated Power of Conventional Square root method
S.No. Parameters Power Dissipated
1. Thermal Power Dissipation 66.37mW
2. Core Static Thermal Power Dissipation 58.85mW
3. I/O Thermal Power Dissipation 7.52mW

The power analysis further illustrates the benefits of the proposed method
• Thermal Power Dissipation: The method shows lower overall thermal power dissipation, indicating its suitability for low-power applications.
• Core Static Power Dissipation: The method reduces core static power slightly, which contributes to sustained efficiency, especially in energy-sensitive applications.
• I/O Power Dissipation: The method's I/O power is also lower, enhancing its viability in systems where minimizing energy draw from I/O operations is crucial.
These results suggest that the proposed square root method offers improved efficiency in both logic utilization and power dissipation compared to the traditional approach, making it ideal for high-speed, low-power systems such as mobile and embedded applications.
The power analysis presented in Tables 4 and 5 offers a comparative view of the conventional and suggested square root methods in terms of power dissipation. Here are the specific insights:
Table 5: Estimated Power of Square root method
S.No. Parameters Power Dissipated
1. Thermal Power Dissipation 64.58mW
2. Core Static Thermal Power Dissipation 58.83mW
3. I/O Thermal Power Dissipation 5.74mW

Performance Metrics: Area Utilization
The proposed method demonstrates a reduction in I/O thermal power dissipation (by 1.78 mW) and a slight decrease in core static power dissipation, resulting in an overall decrease of 1.79 mW in total thermal power compared to the traditional method. These improvements underscore the efficiency of the approach, particularly for low-power applications.
Table 6: Performance metrics Comparison-Area Utilization
Parameter Conventional Method Proposed Method
Totallogicelements 392 150
Totalpins 34 23

Total Pins and Logic Elements: The method employs 23 pins and 150 logic elements, which is more resource-efficient compared to the traditional long division method.
Overall Performance Analysis
The findings in Table 7 highlight a significant advantage of the proposed power dissipation method over the conventional approach, particularly in terms of Total Power Dissipation (TPD), Core Static TPD, and I/O TPD. The proposed method not only consumes less power but also simplifies calculations, especially for square roots of larger numbers.
Table 7: Performance metrics Comparison-Power Dissipation
Parameter Conventional Method(mW) Proposed Method(mW)
Power dissipation 66.37mW 64.58mW
Static power dissipation 58.85mW 58.83mW
I/O power dissipation 7.52mW 5.74mW

Thus the analysis across Tables 4, 5, 6 and 7 illustrates that the proposed method not only achieves a reduction in power dissipation but also optimizes hardware resource usage, making it an ideal choice for applications requiring both high speed and energy efficiency. This method provides substantial gains in area utilization and power efficiency relative to the traditional approach.
Calculating square roots through traditional means can be complex and time-consuming, particularly as the numbers grow larger. In contrast, the proposed method is easier to understand and implement, allowing for a flexible range of calculations. This adaptability leads to more efficient results.
When evaluating the performance of both methods, the proposed square root calculation outperforms the conventional method in several areas. The computational effort required is notably reduced, with only 1% of logic elements utilized compared to the traditional method. Additionally, the proposed method occupies just 28% of pin resources and achieves an optimal power dissipation of 64.58 milliwatts.
Crucially, the proposed technique primarily relies on addition and subtraction, whereas the conventional method necessitates division, adding to its complexity. Overall, the data suggests that the proposed method excels in speed, area efficiency, and power dissipation, making it a superior choice for practical applications.

It may be appreciated by those skilled in the art that the drawings, examples and detailed description herein are to be regarded in an illustrative rather than a restrictive manner. , Claims:We Claim:

1. A hardware-implemented method for square root computation, comprising:
a. converting an input number into Binary Coded Decimal (BCD) format for processing using a BCD conversion module;
b. identifying the input number's range using predefined boundaries stored in a lookup table within a hardware memory module;
c. verifying whether the input is a perfect square and, if so, retrieving the square root directly from the lookup table;
d. analyzing the last two or three digits of the input number using a digit verification module to determine the initial computational parameters;
e. performing addition or subtraction operations using an Arithmetic Logic Unit (ALU) based on the input number's position relative to the midpoint of the identified range;
f. iteratively refining the computed value through arithmetic operations to achieve the desired precision using hardware logic;
g. outputting the computed square root in BCD format via an output module for further processing or display;
characterized in that, the method eliminates the use of division and multiplication operations, thereby enhancing computational speed and reducing power consumption in hardware environments.
2. The method as claimed in claim 1, wherein the predefined boundaries for range identification are stored in Block Random Access Memory (Block RAM) to ensure fast retrieval and efficient hardware implementation.
3. The method as claimed in claim 1, wherein the digit verification module is configured to analyze the last two digits for numbers ending in 1, 4, 6, or 9, and the last three digits for numbers ending in 0 or 5, for accurate parameter determination.
4. The method as claimed in claim 1, wherein the Arithmetic Logic Unit (ALU) is optimized to perform addition and subtraction operations with minimal delay and power consumption.
5. The method as claimed in claim 1, wherein the iterative refinement step is executed using a hardware comparator to ensure precision in the square root calculation.
6. The method as claimed in claim 1, wherein the hardware memory module includes a lookup table storing square root values for perfect squares within a predefined range of numbers.
7. The method as claimed in claim 1, wherein the output module formats the computed square root in Binary Coded Decimal (BCD) format for compatibility with external display or processing systems.
8. The method as claimed in claim 1, wherein the hardware implementation is configured for deployment in low-power and real-time systems, including embedded devices and mobile processors.

Documents