SqrtLab: A Deep Dive into BigInt Square Roots

An independent exploration of integer square root algorithms for arbitrarily large numbers. The goal of this lab was to organically discover, build, and understand how math engines handle massive numbers, rather than just reading a textbook.

🧪 What Is SqrtLab?

This repository is a personal laboratory. I wanted to understand how programming languages (like Python) compute the square root of numbers with thousands or tens of thousands of digits so efficiently.

Instead of just reading CPython's source code or the GMP documentation, I started from scratch:

1. Built a brute-force approach.
2. Moved to Bounded Binary Search.
3. Implemented Classic Newton-Raphson.
4. Experimented with division-free algorithms (Goldschmidt).
5. Independently derived a hybrid approach: using Newton's method on the top bits for a highly accurate initial seed, followed by a bit-by-bit refinement.

It turns out, this hybrid approach (which I playfully called BEAST during testing) is mathematically identical to the industry standard techniques used by CPython and GMP! Arriving at the same conclusion as the experts through independent trial, error, and logic was the real achievement here.

⚙️ The Algorithms (sqrt_algos.py)

#	Algorithm	Approach	Complexity (practical)
1	Linear Search	Brute force	O(√n) — unusable for big n
2	Bounded Binary Search	Bit-length bounds + bisect	O(log n)
3	Classic Newton	Newton-Raphson, start from n	O(log n · M(n))
4	Hybrid Newton	Bit-shift seed + Newton	O(log n · M(n))
5	Classic Div-Free	Reciprocal Newton (no division)	O(log n · M(n))
6	Hybrid Div-Free	Bit-shift seed + Div-Free	O(log n · M(n))
7	CPython Standard	CPython's bit-doubling method	O(log n · M(n))
8	BEAST (Hybrid Fixed)	Newton seed + CPython polish	O(log n · M(n))
9	Goldschmidt	Pure multiplication approach	O(log n · M(n))

📊 Benchmark Results

Machine: Windows, Python 3.14 Tests: Focused comparison in cpython_netwon_fixed.py (Best of 50 runs).

Correctness

Every algorithm was put through a gauntlet of 200,000 integers + massive random numbers (up to 50,000 bits). All methods achieved 100% accuracy. A critical lesson learned was the necessity of a final correction step (+1 / -1 check) to fix off-by-one errors inherent in floating-point/integer math boundaries.

Speed

Algorithm	10^1000	10^10000	10^50000
math.isqrt (C-builtin)	0.0118 ms	0.5305 ms	6.1351 ms
CPython-port (Pure Python)	0.0303 ms	0.7799 ms	8.2069 ms
BEAST (Pure Python)	0.0345 ms	0.7792 ms	8.1046 ms
Goldschmidt (Pure Python)	0.6453 ms	23.7827 ms	284.7614 ms

💡 The Honest Conclusion & Lessons Learned

• Reinvention is the best teacher: Independently deriving the BEAST hybrid method and later realizing it mirrors professional big-integer implementations was an incredible learning experience. It proved that the logic was sound.
• Python Overhead: CPython-port and BEAST performed nearly identically. They are both about ~1.3x slower than the native math.isqrt, simply because math.isqrt is compiled in C. You cannot beat a compiled C function with pure Python, but you can match its algorithmic efficiency.
• Div-Free in Software: Goldschmidt (division-free) is amazing for hardware (FPU) implementations because logic gates do multiplication fast. However, in pure Python BigInt arithmetic, swapping 1 division for 3 massive multiplications is a net loss in performance.

🚀 How to Run

# Full algorithm suite (correctness + benchmark)
python sqrt_algos.py

# Focused CPython/BEAST/Goldschmidt (200k correctness + speed)
python cpython_netwon_fixed.py

# Standalone correctness test
python test_correctness_final.py

License

MIT