---

Mastering Square Root Algorithms in Common Lisp from First Principles

Calculating a square root in Common Lisp without relying on built-in libraries is achieved through iterative algorithms like Newton's method. This technique starts with an initial guess and repeatedly refines it by averaging the guess and the original number divided by that guess, converging on the correct integer root.

Imagine you're the lead engineer for a deep space probe, millions of miles from home. The mission: to navigate uncharted territory, making precise course corrections. The probe's onboard computer is a marvel of efficiency, built with minimal power consumption in mind. This means no fancy, high-level math libraries; every calculation must be performed using fundamental, resource-sparing algorithms. Your first critical task is to implement a navigation function that requires calculating a square root. You can't just call sqrt(). You have to build it from scratch.

This scenario, while dramatic, perfectly captures a common challenge in software engineering: the need to understand what happens "under the hood." Relying on pre-built libraries is standard practice, but true mastery comes from the ability to implement core algorithms from first principles. In this guide, we will embark on that journey. We'll dissect, understand, and implement an efficient square root function in Common Lisp, transforming a seemingly complex mathematical problem into elegant, understandable code. You will not only solve the problem but also gain a deeper appreciation for algorithmic thinking and the power of Lisp.

---

What is a Square Root Algorithm?

At its core, finding the square root of a number N (the radicand) means finding another number x such that x * x = N. For example, the square root of 25 is 5 because 5 * 5 = 25. While this is simple for perfect squares we know by heart, it becomes a computational problem for larger numbers or when we are constrained from using built-in functions.

The challenge presented in the kodikra learning path is specific: we must calculate the square root for positive whole numbers where the result is also a positive whole number (a perfect square). This constraint simplifies the problem by removing the complexity of floating-point arithmetic and irrational numbers, allowing us to focus purely on the integer-based algorithm.

A "square root algorithm," in this context, is a procedure or a set of rules that systematically finds this value x. Instead of trying every single number from 1 up to N (a brute-force approach), we use a more intelligent method of approximation. We start with a reasonable guess and iteratively improve it until our guess, when squared, equals the original number. This iterative refinement is the cornerstone of many powerful numerical methods in computer science.

Key Terminology

• Radicand: The number for which we are trying to find the square root. In sqrt(25), the radicand is 25.
• Perfect Square: An integer that is the square of another integer. For example, 9, 16, and 25 are perfect squares.
• Iteration: A single pass or cycle of a repetitive process. Our algorithm will perform multiple iterations to refine its guess.
• Convergence: The process of an iterative algorithm getting closer and closer to the correct answer with each step.

---

Why Implement It Manually in Common Lisp?

In any modern programming language, including Common Lisp, finding a square root is a solved problem. A simple call to (sqrt 144) would instantly return 12.0. So, why go through the trouble of building our own? The reasons are deeply rooted in the principles of software engineering and computer science education.

1. Understanding Fundamental Algorithms: The "deep space probe" analogy highlights a real-world constraint: resource-limited environments. In embedded systems, custom hardware, or performance-critical kernels, you might not have access to a full standard library. Knowing how to implement core functions like this is an invaluable skill.
2. Educational Value: Writing this function from scratch forces you to think algorithmically. You move from being a user of a tool to the creator of one. This process solidifies your understanding of loops, conditionals, and numerical methods in a practical way.
3. Appreciating Lisp's Power: Common Lisp, with its powerful loop macro and functional paradigms, provides an expressive canvas for implementing such algorithms. This exercise showcases how Lisp's features can be used to write concise yet powerful numerical code.
4. Interview Preparedness: Questions involving the implementation of standard library functions are classic technical interview staples. They test a candidate's problem-solving skills and foundational knowledge, not just their ability to memorize syntax.

By tackling this problem, you are not just learning a piece of Lisp syntax; you are learning to think like a computer scientist, breaking down a problem and building a solution from the ground up. This is a core competency that transcends any single programming language.

---

How Does the Algorithm Work? The Babylonian Method

The most common and efficient approach for this problem is a successive approximation method known as **Heron's method** or the **Babylonian method**, which is a specific application of the more general **Newton's method**. The intuition behind it is surprisingly simple.

Let's say we want to find the square root of a number N.

1. We start with an initial, arbitrary guess, let's call it guess. A common starting point is N / 2.
2. If guess * guess = N, we're done! We found the answer.
3. If not, our guess is either too high or too low. If guess is an overestimate of the true root, then N / guess will be an underestimate. Conversely, if guess is an underestimate, N / guess will be an overestimate.
4. The key insight is that the actual square root lies somewhere between guess and N / guess. A great way to get a better approximation is to take the average of these two values.
5. Our new guess becomes: new_guess = (guess + N / guess) / 2.
6. We repeat this process, with each new guess getting progressively closer to the actual square root.

A Concrete Example: Finding the Square Root of 144

• Radicand (N): 144
• Initial Guess: 144 / 2 = 72

Iteration 1:

• Current Guess: 72
• Check: 72 * 72 = 5184 (too high)
• Calculate N / guess: 144 / 72 = 2
• New Guess (average): (72 + 2) / 2 = 74 / 2 = 37

Iteration 2:

• Current Guess: 37
• Check: 37 * 37 = 1369 (too high)
• Calculate N / guess: 144 / 37 ≈ 3.89 (we'll use integer division, so 3)
• New Guess (average): (37 + 3) / 2 = 40 / 2 = 20

Iteration 3:

• Current Guess: 20
• Check: 20 * 20 = 400 (too high)
• Calculate N / guess: 144 / 20 = 7 (integer division)
• New Guess (average): (20 + 7) / 2 = 27 / 2 = 13 (integer division)

Iteration 4:

• Current Guess: 13
• Check: 13 * 13 = 169 (too high)
• Calculate N / guess: 144 / 13 = 11 (integer division)
• New Guess (average): (13 + 11) / 2 = 24 / 2 = 12

Iteration 5:

• Current Guess: 12
• Check: 12 * 12 = 144. This is our radicand!
• Result: 12. We have converged on the solution.

This iterative process can be visualized with the following flow diagram.

    ● Start (radicand N)
    │
    ▼
  ┌───────────────────┐
  │ guess ← floor(N/2)│
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ Loop Starts       │
  └─────────┬─────────┘
            │
            ▼
    ◆ guess² == N ?
   ╱               ╲
 Yes                No
  │                  │
  ▼                  ▼
[Return guess]   ┌──────────────────────────────────┐
                 │ new_guess ← floor((guess+N/guess)/2) │
                 └────────────────┬─────────────────┘
                                  │
                                  ▼
                             [ guess ← new_guess ]
                                  │
                                  └─────────┐
                                            │
                                            ├─ (Repeat Loop)
                                            │
                                            ▼
                                       ● End Loop

---

Where Is This Implemented? A Detailed Code Walkthrough

Now let's analyze the Common Lisp solution provided in the kodikra module. This implementation elegantly captures the logic of Newton's method using Lisp's powerful features.

(defpackage :square-root
  (:use :cl)
  (:export :square-root))

(in-package :square-root)

(defun square-root (radicand)
  (if (= radicand 1)
      1
      (loop with guess = (floor radicand 2)
            repeat 10
            until (= radicand (* guess guess))
            do (setf guess (floor (+ guess (/ radicand guess)) 2))
            finally (return (and (= radicand (* guess guess)) guess)))))

Section 1: Package Definition

(defpackage :square-root
  (:use :cl)
  (:export :square-root))

(in-package :square-root)

• (defpackage :square-root ...): This defines a new package named square-root. Packages in Common Lisp are namespaces that prevent symbol collisions. It's like creating a module or a library.
• (:use :cl): This clause specifies that our new package should inherit all the standard symbols from the Common Lisp package (:cl), such as defun, if, loop, etc.
• (:export :square-root): This makes the symbol square-root public, meaning it can be accessed from other packages. This is our main function.
• (in-package :square-root): This command switches the current working namespace to our newly created square-root package. All subsequent definitions will belong to this package.

Section 2: Function Definition and Base Case

(defun square-root (radicand)
  (if (= radicand 1)
      1
      ...

• (defun square-root (radicand)): This defines a function named square-root that accepts one argument, radicand.
• (if (= radicand 1) 1 ...): This is an important edge case handler. The square root of 1 is 1. Our iterative algorithm might work for it, but handling it separately is cleaner and avoids a potential division by zero if the guess ever became zero (unlikely with our formula, but good practice). The main loop logic is in the "else" part of this if statement.

Section 3: The `loop` Macro and Iteration Logic

      (loop with guess = (floor radicand 2)
            repeat 10
            until (= radicand (* guess guess))
            do (setf guess (floor (+ guess (/ radicand guess)) 2))
            finally (return (and (= radicand (* guess guess)) guess)))

This is the heart of the function, and it uses Common Lisp's incredibly versatile loop macro. Let's break down each clause:

• with guess = (floor radicand 2): This is an initialization clause. It declares a loop-local variable named guess and sets its initial value to the radicand divided by 2, with any fractional part discarded (thanks to floor). This is our starting guess.
• repeat 10: This is a termination clause. It tells the loop to run a maximum of 10 times. This is a safeguard to prevent an infinite loop, but as we'll see later, it's not the most robust way to handle termination.
• until (= radicand (* guess guess)): This is another termination clause. The loop will stop as soon as the square of our current guess is equal to the radicand. This is our success condition. The loop terminates if either the repeat limit is reached or this condition becomes true.
• do (setf guess (floor (+ guess (/ radicand guess)) 2)): This is the main body of the loop. In each iteration, it calculates the new guess according to Newton's method.
  • (/ radicand guess): Divides the number by the current guess.
  • (+ guess ...): Adds the result to the current guess.
  • (floor ... 2): Divides the sum by 2 and takes the floor to ensure we are working with integers. This is the averaging step.
  • (setf guess ...): Updates the guess variable with this newly calculated value for the next iteration.
• finally (return (and (= radicand (* guess guess)) guess)): The finally clause is executed once the loop terminates, for any reason.
  • It performs one final check: (= radicand (* guess guess)).
  • The (and A B) special operator first evaluates A. If A is false (nil), it stops and returns nil. If A is true, it proceeds to evaluate B and returns the result of B.
  • So, if the final guess squared equals the radicand, the expression returns the guess itself. If not (which would happen if the repeat 10 limit was hit for a non-perfect square), it returns nil. This is a clever, idiomatic way to return the result only on success.

---

Improving the Code: Removing the "Magic Number"

The provided solution is good, but it has one weakness: the repeat 10 clause. This "magic number" implies that 10 iterations are always enough. While true for many numbers within the standard integer range, it's not a mathematically robust guarantee. A better approach is to let the algorithm run until it naturally converges or stabilizes.

An iterative algorithm has converged when the guess stops changing between iterations. We can modify the loop to track the previous guess and stop when the new guess is the same as the old one. This is a much more reliable termination condition.

Optimized Implementation

(defun square-root-optimized (radicand)
  (cond ((< radicand 0) (error "Square root of a negative number is not supported."))
        ((= radicand 0) 0)
        ((= radicand 1) 1)
        (t (loop with guess = (floor radicand 2)
                 with prev-guess = 0
                 until (= guess prev-guess)
                 do (setf prev-guess guess)
                    (setf guess (floor (+ guess (/ radicand guess)) 2))
                 finally (return (and (= radicand (* guess guess)) guess))))))

What's Changed?

1. Better Edge Case Handling: We use a cond statement to handle negative numbers (by raising an error), 0, and 1 explicitly before starting the loop. This makes the function more robust.
2. No More `repeat 10`: The arbitrary limit is gone.
3. Convergence Check: We introduce a new variable, prev-guess. The loop now runs until (= guess prev-guess). It stops when an iteration produces the exact same guess as the previous one, meaning we have found the most stable integer value.
4. State Update: Inside the loop, (setf prev-guess guess) saves the current guess before we calculate the next one.

This optimized version is more robust and correctly implements the convergence principle of the algorithm without relying on an arbitrary iteration count.

---

When to Use This? Pros and Cons

Knowing how to build this algorithm is one thing; knowing when to use it is another. Let's compare our manual implementation against the standard library's cl:sqrt function.

Aspect	Manual Implementation (Newton's Method)	Standard Library cl:sqrt
Use Case	Educational purposes, resource-constrained environments, interviews, integer-only perfect square calculations.	General-purpose, high-performance applications, floating-point calculations.
Performance	Reasonably fast for integers, but slower than highly optimized, low-level native code.	Extremely fast. Often implemented using hardware-level floating-point instructions (FPU).
Data Types	Designed for positive integers and perfect squares. Will fail or give incorrect results for floats or non-perfect squares.	Handles a wide range of number types, including integers, floats, and complex numbers. Returns a float.
Dependencies	None. Completely self-contained.	Part of the Common Lisp standard. Available in any compliant implementation.
Readability	Requires understanding the algorithm. Code is more verbose and complex.	Highly readable and self-explanatory. (sqrt n) is universally understood.
Robustness	Less robust. Our initial version had limitations, and even the optimized one only handles a subset of all possible numbers.	Highly robust. Rigorously tested and handles all edge cases according to the language specification.

The verdict is clear: for everyday programming, always prefer the standard library function. It's faster, safer, and more versatile. However, the value of our manual implementation lies in the knowledge gained, making you a more competent and insightful programmer.

Alternative Approach: Binary Search

Newton's method is not the only way. Another intuitive approach is to use **binary search**. Since the square root of N must lie between 0 and N, we can perform a binary search within this range.

1. Set a search range: low = 0, high = N.
2. Pick the middle point: mid = (low + high) / 2.
3. If mid * mid == N, we found the root.
4. If mid * mid > N, the root must be in the lower half. We set high = mid - 1.
5. If mid * mid < N, the root must be in the upper half. We set low = mid + 1.
6. Repeat until low is greater than high.

This method is also very efficient and demonstrates a different, but equally important, algorithmic paradigm.

    ● Start (N, low=0, high=N)
    │
    ▼
  ┌───────────────────┐
  │ Loop (while low ≤ high) │
  └─────────┬─────────┘
            │
            ▼
  ┌───────────────────┐
  │ mid ← floor((low+high)/2) │
  └─────────┬─────────┘
            │
            ▼
    ◆ mid² == N ? ─── Yes ───▶ [Return mid]
    │
    No
    │
    ▼
    ◆ mid² > N ?
   ╱           ╲
 Yes            No
  │              │
  ▼              ▼
[high ← mid-1] [low ← mid+1]
  │              │
  └──────┬───────┘
         │
         ▼
     (Repeat Loop)

---

Frequently Asked Questions (FAQ)

What exactly is Newton's method for square roots?

Newton's method is a general technique for finding the roots of real-valued functions. For square roots, it's applied to find the root of the function f(x) = x² - N. The iterative formula derived from this is x_n+1 = x_n - f(x_n)/f'(x_n), which simplifies to x_n+1 = (x_n + N/x_n)/2. This is the exact formula we used, also known as the Babylonian or Heron's method.

Why does the initial guess start at radicand / 2?

Starting with radicand / 2 is a simple and effective heuristic. For any number N > 4, its square root will always be less than N/2. This provides a reasonable starting point that is guaranteed to be an overestimate, ensuring the algorithm converges quickly from one direction. While other starting points (like 1, or N itself) would also work, N/2 often reduces the number of initial iterations needed.

What happens if I input a number that is not a perfect square with this function?

The provided function will return nil. The loop will terminate either because the guess stabilizes at an integer whose square is close to but not equal to the radicand, or (in the original version) the repeat 10 limit is hit. The final (and (= radicand (* guess guess)) guess) clause will then fail the equality check, causing the entire expression to evaluate to nil.

How can I handle non-integer square roots in Common Lisp?

For non-integer (floating-point) results, you should always use the built-in cl:sqrt function. It is designed for this purpose and will return a floating-point number. For example, (sqrt 2) will correctly return 1.414213562373095. Our integer-based algorithm is not suitable for this task.

Is this algorithm efficient for very large numbers?

Yes, Newton's method is very efficient. The number of correct digits roughly doubles with each iteration, a property known as quadratic convergence. This means it finds the solution very quickly, even for extremely large numbers. It is significantly more efficient than linear search (checking every number) or even binary search in many cases.

What does the code (and (= radicand (* guess guess)) guess) actually do?

This is an idiomatic Lisp trick. The and macro evaluates its arguments from left to right. It stops and returns nil (Lisp's boolean false) as soon as it encounters an argument that evaluates to nil. If all arguments evaluate to a true value, it returns the value of the last argument. In this case, it first checks if guess*guess equals the radicand. If it's false, and stops and returns nil. If it's true, and continues to the next argument, which is just guess, and returns its value.

Are there other iterative methods besides Newton's method?

Absolutely. As discussed, the binary search method is a great alternative that is often easier to reason about. Other numerical methods include the Bakhshali method, which is an ancient Indian algorithm that offers even faster (quartic) convergence in some cases. For educational purposes, both Newton's method and binary search are excellent algorithms to learn and implement.

---

Conclusion: From Theory to Implementation

We've journeyed from a high-level problem on a deep space probe to a low-level, elegant implementation in Common Lisp. By building a square root function from first principles, we've done more than just solve a coding challenge. We have explored the core of algorithmic thinking, dissected the logic of iterative approximation with Newton's method, and learned to express that logic in the powerful syntax of Common Lisp's loop macro.

You now understand not only how to solve the problem but also why this approach is so effective. You've seen its strengths—speed and independence—and its limitations, leading to a deeper appreciation for the robust, highly-optimized functions available in a language's standard library. This foundational knowledge is what separates a coder from a true software engineer.

As you continue your journey, carry this principle with you: always seek to understand the fundamentals. The libraries and frameworks will change, but the underlying algorithms and problem-solving techniques will remain invaluable for your entire career. To continue building these essential skills, we encourage you to explore our full Common Lisp learning path or dive deeper into our complete set of Common Lisp resources.

Disclaimer: The code in this article is written for educational purposes and tested on modern Common Lisp implementations like SBCL 2.4.x. Behavior may vary on different Lisp environments. Always prefer standard library functions for production code unless specific constraints justify a custom implementation.

---

Published by Kodikra — Your trusted Common-lisp learning resource.