---

Cairo Square Root: A Deep Dive into Integer Algorithms from Scratch

Calculating an integer square root in Cairo without relying on external libraries involves implementing an iterative algorithm. Common approaches include a simple linear search, a more efficient binary search, or a mathematically advanced method like Newton's, each designed to find an integer whose square is equal to or just less than the given number.

The Mission: A Power-Efficient Deep Space Computer

Imagine you're the lead engineer for a deep space exploration rocket. Your mission is to navigate treacherous asteroid fields and slingshot around distant planets. The journey is incredibly long, and every watt of power is precious. The onboard computer, the brain of your vessel, was designed for extreme power efficiency, meaning it has limited computational power and lacks the luxury of comprehensive, high-level math libraries we often take for granted.

One of the first critical calculations for course correction involves finding the square root of a target number. Your challenge isn't just to get the right answer; it's to get it using the most fundamental operations available, ensuring the battery lasts for the entire multi-decade voyage. This scenario perfectly mirrors the constraints of developing for the Cairo Virtual Machine (VM) on Starknet.

In the world of blockchain, every computation has a cost, measured in "gas." Inefficient algorithms burn through user funds and can make a smart contract prohibitively expensive to use. This guide will take you from a simple, brute-force solution to highly optimized algorithms for calculating square roots in Cairo, turning you into a resource-conscious developer ready for the challenges of decentralized application development.

---

What Exactly Is an Integer Square Root?

Before we dive into the code, it's crucial to clarify our objective. When we talk about the square root of a number, say 16, the answer is a clean 4 because 4 * 4 = 16. However, what about the square root of 18? In traditional mathematics, the answer is an irrational number (approximately 4.2426...).

In the context of this kodikra.com module and many computing scenarios, we are concerned with the integer square root. This is defined as the greatest integer that is less than or equal to the actual square root. Therefore, the integer square root of 18 is 4, because 4 * 4 = 16, and the next integer, 5, gives us 5 * 5 = 25, which overshoots our target.

This distinction is vital in environments like Cairo that operate primarily with integers (specifically, field elements or felt252, and standard integer types like u64). We are not looking for floating-point precision; we are looking for the whole number that, when squared, gets us as close as possible to the input number without exceeding it.

---

Why Calculate Square Roots Manually in Cairo?

In most high-level programming languages like Python or JavaScript, you'd simply call math.sqrt() or Math.sqrt() and move on. The Cairo ecosystem, however, demands a deeper understanding of computational efficiency for several key reasons:

• Gas Optimization: Every operation in a Starknet smart contract consumes gas, which has a real-world cost. An inefficient algorithm with many steps (like a poorly implemented loop) can drastically increase transaction fees, making your dApp less competitive.
• Cairo VM Constraints: The Cairo VM is a specialized, non-EVM environment optimized for STARK proofs. While incredibly powerful for verifiable computation, it means that some operations we take for granted might be more resource-intensive. Understanding how to build complex logic from primitive operations is a core skill.
• No Standard "Math" Library: While the Starknet ecosystem has libraries like the OpenZeppelin Contracts for Cairo which include some math utilities, there isn't a universal, built-in "math" library like in other languages. Furthermore, relying on external libraries adds dependencies and potential security surface area to your project. For a fundamental operation, implementing it yourself can be safer and more efficient.
• Algorithmic Foundation: Learning to implement algorithms like square root from scratch builds a strong foundational understanding of computational thinking. This skill is transferable and essential for tackling more complex problems in decentralized finance (DeFi), on-chain gaming, and governance mechanisms. This is a cornerstone of the Cairo 2 learning roadmap.

---

How to Implement Square Root Algorithms in Cairo

We will explore three distinct methods for finding the integer square root, starting with the most straightforward and progressing to the most efficient. Each approach has its own trade-offs in terms of performance and complexity.

Approach 1: The Simple Linear Search (Brute-Force)

The most intuitive way to solve this problem is to simply start checking numbers one by one. We can start with 1, square it, and see if it equals our target number (the radicand). If it's too small, we try 2. Then 3. We continue this process until the square of our candidate number is greater than or equal to the radicand.

This method is often called "brute-force" because it relies on sheer computational power rather than clever logic to find the solution. It's easy to understand and implement, making it a great starting point.

Algorithm Logic Flow

Here is a visual representation of the linear search logic. It's a simple, sequential process of checking and incrementing.

 ● Start (input: radicand)
 │
 ▼
┌──────────────────┐
│ candidate = 1    │
└────────┬─────────┘
         │
         ▼
 ◆ (candidate * candidate) < radicand ?
 │        ╲
 │ Yes     ╲ No
 │          ╲
 ▼           ▼
┌──────────┐  ┌───────────────────┐
│ candidate++│  │ return candidate  │
└──────────┘  └─────────┬─────────┘
     │                   │
     └───────────────────┘
                         │
                         ▼
                        ● End

Cairo Implementation: Linear Search

The solution provided in the kodikra.com module uses this exact approach. Let's analyze the code.

pub fn sqrt(radicand: u64) -> u64 {
    let mut candidate = 1;

    // A small optimization: if radicand is 1 or 2, the answer is 1.
    // The loop handles this, but we can be explicit.
    if radicand > 2 {
        while (candidate * candidate) < radicand {
            candidate += 1;
        };
    }

    // After the loop, `candidate*candidate` is >= `radicand`.
    // If it's `== radicand`, we found the perfect root.
    // If it's `> radicand`, the previous candidate was the integer root, but the loop condition
    // means our current candidate is the one we need to check.
    // Let's refine the logic slightly for clarity. The original code has a subtle bug for non-perfect squares.
    // A corrected version is below. For now, let's analyze the original intent.

    candidate
}

Line-by-Line Code Walkthrough

Let's break down the provided Cairo code to understand every component:

• pub fn sqrt(radicand: u64) -> u64 {: This defines a public function named sqrt. It accepts one argument, radicand, which is a 64-bit unsigned integer (u64). The function is declared to return a value of the same type, u64.
• let mut candidate = 1;: We initialize a mutable variable named candidate with the value 1. This will be our "guess" for the square root, which we will increment in our search.
• if radicand > 2 { ... }: This condition is a minor, slightly confusing optimization. The logic is that for inputs 0, 1, and 2, the integer square root is 0 or 1, and the initial `candidate` value of 1 works. However, the loop itself would handle this correctly. We'll ignore this for a moment and focus on the core loop.
• while (candidate * candidate) < radicand { ... }: This is the heart of the algorithm. The loop continues as long as the square of our current candidate is less than the input radicand.
• candidate += 1;: Inside the loop, if the condition is met, we simply increment our candidate by 1 and try again.
• candidate: After the loop terminates, the function returns the final value of candidate. The loop stops when candidate * candidate is no longer less than radicand (i.e., it's greater than or equal to it).

The Subtle Flaw and a Refined Version

The original code works for perfect squares (like 16, 25, 36). For sqrt(16), the loop runs until candidate is 4. Then `4*4` (16) is not less than 16, the loop stops, and it returns 4. Correct.

However, for a non-perfect square like 18, the loop runs until candidate is 5. `4*4` (16) is less than 18, so it continues. `candidate` becomes 5. `5*5` (25) is not less than 18, so the loop stops and it returns 5. The correct integer square root is 4. The code is off by one for non-perfect squares.

Here is a corrected and cleaner version:

pub fn sqrt_linear_corrected(radicand: u64) -> u64 {
    if radicand == 0 {
        return 0;
    }
    let mut candidate: u64 = 1;
    while candidate * candidate <= radicand {
        // Check for potential overflow before multiplication
        if candidate > 4294967295_u64 { // sqrt(u64::max)
             // If our candidate is this large, its square will overflow u64.
             // We can assume the current candidate is the result if its square is <= radicand.
             // This check is for extreme edge cases.
             break;
        }
        candidate += 1;
    }
    // The loop stops when candidate*candidate > radicand.
    // The correct integer root is the previous value.
    candidate - 1
}

This version is more robust. It handles the edge case of 0 and correctly returns candidate - 1 to account for the loop's overshoot.

---

Approach 2: The Optimized Binary Search

The linear search is inefficient for large numbers. If you need to find the square root of 1,000,000,000,000, you'd be looping for a million iterations! We can do much better. A binary search algorithm is a far more intelligent approach.

The idea is to define a search range, initially from 0 to the number itself (the radicand). We then pick the middle point of this range as our guess. - If the square of our guess is the target, we're done. - If the square is too large, we know the true root must be in the lower half of our range. - If the square is too small, the true root must be in the upper half.

By repeatedly halving the search space, we can converge on the correct answer exponentially faster. For a deep dive into the language itself, explore our complete guide to the Cairo programming language.

Algorithm Logic Flow

The binary search logic is more complex, involving adjusting the search boundaries (`low` and `high`) until they converge.

      ● Start (input: radicand)
      │
      ▼
┌───────────────────────────┐
│ low = 0, high = radicand  │
│ result = 0                │
└────────────┬──────────────┘
             │
             ▼
      ◆ low <= high ?
     ╱         ╲
   Yes          No
    │           │
    ▼           ▼
┌───────────┐  ┌───────────────┐
│ mid = low + │  │ return result │
│ (high-low)/2│  └─────────┬─────┘
└─────┬─────┘            │
      │                  │
      ▼                  ▼
┌───────────────┐      ● End
│ square = mid*mid│
└───────────────┘
      │
      ▼
 ◆ square == radicand ? ───────► Found! return mid
 │
 ▼
 ◆ square < radicand ?
╱         ╲
Yes          No
 │           │
 ▼           ▼
┌───────────┐ ┌──────────────┐
│ result=mid│ │ high = mid - 1 │
│ low=mid+1 │ └──────────────┘
└─────┬─────┘         │
      └───────────────┘

Cairo Implementation: Binary Search

Here is how you would implement an integer square root function using a binary search algorithm in Cairo.

pub fn sqrt_binary_search(radicand: u64) -> u64 {
    if radicand == 0 {
        return 0;
    }

    let mut low: u64 = 1;
    let mut high: u64 = radicand;
    let mut result: u64 = 1;

    while low <= high {
        // To prevent overflow when low+high is large, we use this formula
        let mid = low + (high - low) / 2;

        // Check for overflow before squaring mid
        // If mid > sqrt(u64::max), mid*mid will overflow.
        // u64::max is approx 1.844e19, its sqrt is approx 4.295e9.
        if mid > 4294967295_u64 {
            high = mid - 1;
            continue;
        }

        let square = mid * mid;

        if square == radicand {
            return mid; // Perfect square found
        } else if square < radicand {
            // This is a potential answer, store it and search the upper half
            result = mid;
            low = mid + 1;
        } else {
            // The square is too large, search the lower half
            high = mid - 1;
        }
    }

    result
}

Code Walkthrough

• let mut low: u64 = 1; let mut high: u64 = radicand;: We establish our search space. The root cannot be less than 1 (for positive radicands) or greater than the number itself.
• let mut result: u64 = 1;: This variable is crucial for non-perfect squares. It stores the last "good" guess whose square was less than the radicand.
• while low <= high { ... }: The loop continues as long as our search space is valid.
• let mid = low + (high - low) / 2;: We calculate the midpoint. This method avoids potential overflow that (low + high) / 2 could cause if low + high exceeds the maximum value for a u64.
• if square == radicand { return mid; }: If we land on the perfect root, we return it immediately.
• else if square < radicand { ... }: If our guess is too small, it's a possible candidate for the integer root. We store it in result and then discard the lower half of the search space by setting low = mid + 1.
• else { high = mid - 1; }: If our guess is too large, we discard the upper half by setting high = mid - 1.
• result: Once the loop finishes (when low crosses high), result holds the largest integer whose square is less than or equal to the radicand.

---

Approach 3: The Mathematical Newton's Method

For those seeking peak performance, Newton's method (also known as the Babylonian method for square roots) offers even faster convergence. This is an iterative approximation method from numerical analysis.

The formula is: x_next = (x_current + radicand / x_current) / 2

We start with an initial guess (e.g., the number itself) and repeatedly apply this formula. Each new result (x_next) gets progressively closer to the actual square root. We stop when the guess no longer changes.

Cairo Implementation: Newton's Method

pub fn sqrt_newton(radicand: u64) -> u64 {
    if radicand == 0 {
        return 0;
    }

    // Start with an initial guess. The number itself is a safe choice.
    let mut x: u64 = radicand;
    let mut y: u64 = 1;

    // The loop continues as long as our guess `x` is greater than the result `y`
    // of the division. They converge towards the square root.
    while x > y {
        x = (x + y) / 2;
        y = radicand / x;
    }
    
    // `x` will be the integer square root.
    x
}

Code Walkthrough

• let mut x: u64 = radicand;: We initialize our guess, x, to be the radicand.
• let mut y: u64 = 1;: This variable will hold the result of radicand / x.
• while x > y { ... }: The loop continues as long as our guess x is converging. When x and y become very close or equal, we have found our root.
• x = (x + y) / 2;: This is the core of Newton's method. We are averaging our current guess with the result of dividing the radicand by our guess.
• y = radicand / x;: We update y based on the new x.
• x: When the loop terminates, x holds the integer square root. This method converges extremely quickly, often in just a handful of iterations, even for very large numbers.

---

Performance Showdown: Which Algorithm to Choose?

Choosing the right algorithm depends on your specific needs, particularly the expected range of input values and the importance of minimizing gas costs. Here's a comparison:

Algorithm	Pros	Cons	Time Complexity
Linear Search	- Extremely simple to understand and implement. - Very low code complexity.	- Highly inefficient for large numbers. - Gas cost scales directly with the size of the root.	O(√n)
Binary Search	- Massively more efficient than linear search. - Gas cost is very low and grows logarithmically. - A great balance of performance and readability.	- More complex logic than linear search. - Requires careful handling of boundaries and mid-point calculation.	O(log n)
Newton's Method	- Typically the fastest convergence rate. - Excellent for very large numbers. - Elegant mathematical solution.	- Relies on division, which can be more costly than comparison/addition. - The logic can be less intuitive to developers unfamiliar with the method.	Approximately O(log n)

Recommendation: For almost all practical applications in Starknet smart contracts, the Binary Search approach is the sweet spot. It offers near-optimal performance with code that is still relatively easy to audit and understand. Newton's method is a fantastic alternative if you are certain you will be dealing with extremely large numbers where its faster convergence might save a few extra operations.

---

Real-World Applications in the Starknet Ecosystem

Calculating a square root might seem academic, but it's a building block for more complex operations on-chain:

• DeFi Protocols: Some complex financial models, like certain automated market maker (AMM) bonding curves (e.g., constant product formula x*y=k) or volatility calculations, can involve square roots.
• On-Chain Gaming: Calculating distances between two points in a 2D or 3D game world often requires the Pythagorean theorem (a² + b² = c²), which necessitates finding a square root to solve for 'c'.
• NFTs and Generative Art: Algorithms that generate art or metadata based on mathematical patterns could use square roots for creating circular or radial designs.
• Zero-Knowledge Proofs: While Cairo abstracts much of the underlying cryptography, understanding fundamental math operations is key to building more complex ZK-powered applications.

---

Frequently Asked Questions (FAQ)

Why can't I just use a floating-point library in Cairo?

The Cairo VM and Starknet are designed around integer arithmetic, specifically field elements (felt252). There is no native support for floating-point numbers because they are non-deterministic and create complexities for verifiable computation. Libraries exist to simulate fixed-point (decimal) arithmetic, but for integer roots, direct implementation is far more efficient.

What happens if the input number is not a perfect square?

All the algorithms discussed are designed to find the integer square root. For an input like 20, the function will return 4, because 4*4=16 is the largest perfect square less than or equal to 20. This is the expected and correct behavior for integer math.

How does algorithmic choice impact Starknet gas fees?

Gas fees on Starknet are determined by the number and type of computations performed. A linear search on a large number could involve millions of loop iterations, each one consuming gas. A binary search might only take a few dozen iterations for the same input. This difference could translate to a transaction being orders of magnitude cheaper, which is critical for user adoption.

What is the largest number these functions can handle?

The functions are written to use the u64 type, which has a maximum value of 18,446,744,073,709,551,615. However, a crucial limitation is the multiplication: candidate * candidate. This operation can overflow if candidate exceeds the square root of u64::max (which is approximately 4.29 x 10⁹). Our binary search implementation includes a check to handle this edge case. For numbers larger than u64, you would need to use larger integer types like u128 or u256 and adjust the overflow checks accordingly.

Is Newton's method always better than binary search?

Not necessarily. While Newton's method often converges in fewer iterations, each iteration involves a division operation (radicand / x), which is computationally more expensive than the additions, subtractions, and comparisons used in binary search. For most number ranges encountered in smart contracts, the performance difference is negligible, and binary search's simpler logic can be an advantage for code clarity and security auditing.

Can this logic be adapted to find other roots, like a cube root?

Absolutely. The binary search logic is highly adaptable. To find a cube root, you would simply change the comparison from mid * mid to mid * mid * mid. Newton's method also has a generalized formula for finding the nth root, making these powerful algorithmic patterns you can reuse.

---

Conclusion: Mastering Core Algorithms in Cairo

We've journeyed from a simple, power-constrained deep space computer to the gas-conscious world of the Starknet virtual machine. What began as a basic problem—finding a square root—unfolded into a deep exploration of algorithmic trade-offs. You've seen how a simple brute-force linear search, while easy to write, is impractical for real-world applications.

By advancing to a binary search, you learned how to slash computational costs exponentially, a critical skill for any serious Cairo developer. Finally, with Newton's method, you touched upon the elegance of mathematical approximations that deliver lightning-fast results. This journey from a naive solution to an optimized one is the essence of effective software engineering, especially in resource-constrained environments like blockchain.

The lessons learned in this kodikra.com module are fundamental. Mastering them will not only help you solve specific problems but will also instill a mindset of efficiency and optimization that is invaluable for building the next generation of decentralized applications. This is a key step in your journey through the Cairo 2 learning path.

Disclaimer: The code snippets in this article are based on Cairo syntax and features that are current as of the latest stable version. The Cairo language is under active development, and syntax may evolve. Always consult the official documentation for the most up-to-date information.

---

Published by Kodikra — Your trusted Cairo learning resource.