💻 computer science

Fixed-Point Integer Approximations for Square Root and Division on ESP32:A Benchmark-Driven Analysis

This paper benchmarks fixed-point Q16 integer approximations for square root and division on the ESP32-S3, demonstrating that a lookup table with interpolation significantly outperforms native hardware floating-point implementations in speed while maintaining high accuracy for resource-constrained embedded applications.

Original authors: Lucas Lima Freitag

Published 2026-07-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Lucas Lima Freitag

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a math problem inside a tiny, battery-powered robot that lives in your backyard. This robot needs to do things like figure out how far it is from a tree or how fast it's spinning, which requires complex math like finding square roots or dividing numbers. Usually, computers have a special, super-fast "math engine" (called a Floating-Point Unit) built just for these tricky decimal numbers. But sometimes, that engine is too big, too heavy, or just too unpredictable. It might take a long time to solve a problem one moment and a short time the next, which is a nightmare for a robot that needs to react instantly to avoid crashing.

So, engineers often use a different trick: they pretend all numbers are whole numbers (integers) by pretending the decimal point is stuck in a fixed spot. This is called "fixed-point arithmetic." It's like doing math on a ruler where you can only measure in whole millimeters, not fractions of a millimeter. It's faster and more predictable, but it can be less precise. The big question for the makers of tiny, smart devices (like the ESP32 chips found in many modern gadgets) is: Can we make these "whole number" tricks fast enough to beat the fancy, built-in math engine, without losing too much accuracy?

This paper dives into that exact question using a popular chip called the ESP32-S3. The researchers tested two clever ways to do square roots and division using only whole numbers and a "cheat sheet" (called a Lookup Table or LUT). Imagine a Lookup Table like a giant menu at a restaurant. Instead of cooking a meal from scratch every time (which is slow), you just look up the order on the menu and grab the pre-made dish. The team built a menu with 1,024 entries for numbers between 1 and 10. They also tested a different method that uses a mathematical shortcut (a series expansion) to guess the answer without a menu at all.

The results were surprisingly clear. When the researchers asked the chip to find a square root, the "menu" method was incredibly fast. It took only 15 clock cycles (the tiny ticks of the chip's internal clock) compared to 91 cycles for the built-in math engine. That's a speedup of about 6 times! For division, the menu method was also faster, taking 29 cycles versus 62 for the native engine. The best part? The answers were almost perfect. The square root method was off by only 0.007%, and the division method by 0.004%. That's like measuring the distance to the moon and being off by less than a single grain of sand.

However, the paper also found a catch. The "shortcut" method that didn't use a menu (the base-2 series) was actually slower than the built-in math engine, taking 113 cycles. It was a trade-off: you saved memory space because you didn't need the menu, but you lost speed. The researchers also noted that while the menu method is fast, it does use up some of the chip's memory (about 8 kilobytes) to store the tables. But for most tiny devices, that's a small price to pay for the massive speed boost.

In the end, the paper suggests that for real-time tasks—like keeping a drone steady or fusing data from multiple sensors—the "menu" approach is a winner. It turns a slow, unpredictable math problem into a lightning-fast, predictable one. The researchers even showed that if you were running a complex sensor system, using these methods could save enough time to let the device sleep longer or process more data. While the built-in math engine is still there and works fine, these integer tricks offer a powerful alternative for when speed and timing certainty are the most important things. The paper doesn't claim this is the only way to do math, but it proves that for the ESP32-S3, a well-organized cheat sheet can beat the factory-installed calculator.

Technical Summary: Fixed-Point Integer Approximations for Square Root and Division on ESP32

Problem Statement
Real-time embedded systems, particularly those utilizing microcontrollers like the ESP32-S3, often require mathematical operations such as square roots and divisions within strict timing budgets. While the ESP32-S3 integrates a single-precision hardware Floating-Point Unit (FPU), these operations exhibit variable latency and consume significant clock cycles (approximately 91 cycles for square root and 62 for division). This variability complicates Worst-Case Execution Time (WCET) analysis, a critical requirement for hard real-time control loops, sensor fusion, and deterministic systems. Furthermore, reliance on the FPU introduces dependencies that may be undesirable in deeply embedded or power-constrained environments where integer arithmetic offers predictable timing and lower power consumption.

Methodology
This study evaluates fixed-point Q16 (16 fractional bits) integer approximations for square root and division on the ESP32-S3, benchmarking them against native hardware FPU implementations. The research focuses on two primary integer-based approaches:

Lookup Table (LUT) Method:
- Implementation: Two 1024-entry tables are precomputed for the range $[1, 10)$ using midpoint sampling to minimize error.
- Square Root: Direct table lookup using an index derived from the input via multiplication and bit-shifting (avoiding hardware division).
- Division: Implemented by multiplying the dividend by the precomputed reciprocal of the divisor found in the LUT.
- Optimization: The index calculation uses a fixed-point multiplier (7282) and a right-shift (22) to approximate the division required for binning, ensuring the operation remains purely integer-based.
Base-2 Series Expansion Method:
- Implementation: An alternative division method that rounds the divisor to the nearest power of two.
- Algorithm: The quotient is approximated using a geometric series expansion to correct for the difference between the rounded divisor and the actual divisor. The implementation uses six terms of the series, providing a purely integer alternative without table storage.

Benchmarking Setup
The authors developed a reproducible test harness running on an ESP32-S3 (240 MHz Xtensa LX7 dual-core). The methodology involved:

Operands: Generated using the hardware random number generator (esp_random) to avoid software pseudo-random artifacts.
Scale: Benchmarks were executed across iteration counts ranging from 1,000 to 1,000,000.
Measurement: Cycle counts were captured using the esp_cpu_get_cycle_count() register, measuring only the computation loops.
Error Analysis: Relative error was calculated by comparing the cumulative sum of custom integer results against the native FPU results.

Key Results
The study provides cycle-accurate comparisons and error characterizations:

LUT-Based Square Root: Achieved a 6.1× speedup over the native FPU, reducing execution time from ~91 cycles to 15 cycles. The relative error was negligible at 0.007%.
LUT-Based Division: Achieved a 2.1× speedup, reducing execution time from ~62 cycles to 29 cycles, with a relative error of 0.004%.
Base-2 Series Division: This method was 1.8× slower than the native FPU (approx. 113 cycles vs. 62 cycles) but offered a zero-storage alternative with 0.15% relative error.
Stability: Both cycle counts and error rates remained stable across all iteration counts, confirming deterministic timing and negligible cache effects (the 8 kB LUTs fit entirely within the 16 kB data cache).
Memory Footprint: The LUT approach requires 8 kB of RAM (4 kB per table), which is well within the ESP32-S3's 512 kB SRAM capacity.

Significance and Contributions
The paper claims to fill a gap in the literature by providing the first direct microbenchmark comparison between native single-precision FPU operations and LUT-based fixed-point alternatives on the ESP32-S3. The primary contributions include:

Performance Optimization: Demonstrating that LUT-based integer arithmetic can significantly outperform hardware FPU operations on the ESP32-S3, particularly for square roots, while maintaining high precision suitable for sensor data (12–16-bit ADCs).
Deterministic Timing: Establishing that integer LUT methods eliminate the timing variability associated with FPU operations, making them ideal for hard real-time systems where WCET must be guaranteed.
Trade-off Analysis: Providing a clear trade-off summary where LUT methods offer the best speed-accuracy balance for applications with available RAM, while the Base-2 series offers a storage-free alternative for memory-constrained scenarios, albeit with a performance penalty.
Practical Applicability: The methods are presented as drop-in replacements for floating-point code in applications such as 9-axis IMU sensor fusion (e.g., Madgwick/Mahony filters), where the cycle savings (e.g., 4.3× improvement in a 1 kHz fusion loop) can free up CPU time for additional tasks or power gating.
Reproducibility: The authors provide a web-based interface and open-source Arduino sketch to allow interactive benchmarking and verification of results.

The paper concludes that for resource-constrained, real-time embedded applications on the ESP32-S3, fixed-point LUT approximations offer a superior alternative to native FPU operations when deterministic timing and execution speed are prioritized over the marginal memory cost of lookup tables.

More like this