Home
1
Coding Tutorial

Grains in Common-lisp: Complete Solution & Deep Dive Guide

a close up of a computer screen with code on it

Mastering Exponential Growth: A Deep Dive into the Grains Problem with Common Lisp

The Grains problem, a classic mathematical puzzle, elegantly demonstrates the staggering power of exponential growth using a simple chessboard. In Common Lisp, we can solve this not just by calculating the numbers, but by appreciating the language's inherent strengths in handling arbitrarily large integers and its expressive, problem-solving syntax.

The Legend of the Chessboard and the King's Debt

Have you ever underestimated something, only to realize its true scale was far beyond your imagination? This is a common human experience, and it lies at the heart of a centuries-old legend about a wise servant who saved a prince's life. The grateful king, wanting to reward the servant, offered him anything he desired.

The servant, with a clever understanding of mathematics, made a seemingly humble request. Pointing to the king's chessboard, he asked for grains of wheat. He wanted just one grain on the first square, two on the second, four on the third, eight on the fourth, and so on, with the amount doubling on each of the 64 squares.

The king, amused by such a modest-seeming reward, readily agreed. He had no idea he had just promised away a quantity of wheat larger than all the kingdoms on Earth could produce. This story is the foundation of our programming challenge. In this guide, we will not only solve this puzzle using Common Lisp but also unravel the profound concepts it represents, transforming a simple problem into a masterclass on computational thinking.

What Exactly Is the Grains Problem?

The Grains problem is a computational and mathematical exercise derived from the legend. It challenges us to perform two specific calculations:

  • Calculate the number of wheat grains on any single square of the chessboard.
  • Calculate the total number of wheat grains on all 64 squares combined.

The core of the problem is the rule of doubling. If square n has x grains, then square n+1 will have 2x grains. This creates a geometric progression, a sequence where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio. In our case, the common ratio is 2.

Mathematically, the number of grains on square n can be expressed as 2(n-1). We use n-1 because the first square (n=1) has 2(1-1) = 20 = 1 grain, which correctly starts our sequence.

Why Use Common Lisp for This Challenge?

While the Grains problem can be solved in any programming language, Common Lisp offers a particularly elegant and powerful environment for it. Its design philosophy and features make tackling mathematical problems like this both intuitive and efficient.

  • Arbitrary-Precision Integers (Bignums): The total number of grains is colossal, far exceeding the capacity of standard 64-bit integers found in many languages. Common Lisp handles this seamlessly. You don't need to import a special BigInt library; the language automatically promotes numbers to "bignums" when they grow too large. This lets you focus on the logic, not on memory management for numbers.
  • Expressive and Powerful Syntax: Lisp's parenthesized prefix notation is incredibly consistent and maps directly to its underlying data structures (lists). Functions like expt for exponentiation and the versatile loop macro allow for clear and concise implementation of the required logic.
  • Interactive Development (REPL): Common Lisp thrives on its Read-Eval-Print Loop (REPL). You can define a function, test it with various inputs (like different squares), and get immediate feedback. This iterative process is perfect for exploring problems and verifying your logic step-by-step.

Solving this problem within the kodikra Common Lisp learning path provides a perfect introduction to these core language features in a practical context.

How to Calculate Grains on a Single Square

Our first task is to create a function that, given a square number from 1 to 64, returns the number of grains on that specific square. As we established, the formula is 2(n-1).

The Logic Flow

The logic is straightforward: take an input number, subtract one from it, and then calculate 2 raised to the power of that result. Let's visualize this simple flow.

    ● Start: Input `n` (square number)
    │
    ▼
  ┌────────────────┐
  │ Subtract 1     │
  │ (Calculate n-1)│
  └───────┬────────┘
          │
          ▼
  ┌────────────────┐
  │ Raise 2 to the │
  │ power of result│
  └───────┬────────┘
          │
          ▼
    ● End: Return final value

The Common Lisp Implementation

In Common Lisp, we define functions using defun. For exponentiation, the built-in function is expt, which takes a base and an exponent. Here is the code from the kodikra.com module:


(defpackage :grains
  (:use :cl)
  (:export :square :total))

(in-package :grains)

(defun square (n)
  "Calculates the number of grains on a given chessboard square."
  (expt 2 (1- n)))

Code Walkthrough

  1. (defpackage :grains ...): This defines a new package named grains. Packages in Common Lisp are namespaces that prevent naming conflicts. The :use :cl clause means it inherits the standard symbols from the Common Lisp package (like defun, expt, etc.). The :export clause makes the functions square and total available to other packages that might use this one.
  2. (in-package :grains): This command switches the current working namespace to our newly created grains package. All subsequent definitions will belong to it.
  3. (defun square (n)): This is the function definition. defun is the macro for defining a function. square is the function's name, and (n) is its parameter list, meaning it accepts one argument, which we'll call n.
  4. "Calculates the number of grains...": This is a documentation string, or "docstring." It's good practice to describe what a function does. You can later access this documentation programmatically.
  5. (expt 2 (1- n)): This is the core logic.
    • Because of Lisp's prefix notation, we read it from the outside in. The main operation is expt (exponent).
    • It takes two arguments: the base 2 and the exponent.
    • The exponent is calculated by the expression (1- n). This is a convenient shorthand function in Common Lisp for subtracting 1 from n. It's equivalent to (- n 1).
    • The function implicitly returns the result of the last evaluated expression, which is the value computed by expt.

To test this in a REPL, you could load the file and run:


GRAINS> (square 1)
1
GRAINS> (square 3)
4
GRAINS> (square 64)
9223372036854775808

Notice how Common Lisp effortlessly handles the massive number for the 64th square. This is the bignum support in action.

How to Calculate the Total Grains on the Chessboard

Now for the second, more staggering calculation: the total number of grains on all 64 squares. There are two primary ways to approach this: an iterative method that sums up the grains on each square, and a more direct mathematical formula.

Approach 1: Iterative Summation

The most intuitive programming approach is to loop through each square from 1 to 64, calculate the grains on that square using our square function, and add it to a running total.

The Common Lisp Implementation (Iterative)

The loop macro in Common Lisp is an extremely powerful and readable tool for iteration. It has a mini-language of its own for describing complex loops.


(defun total ()
  "Calculates the total number of grains on the entire chessboard."
  (loop for n from 1 to 64
        summing (square n)))

Code Walkthrough

  1. (defun total ()): We define a function named total that takes no arguments.
  2. (loop ...): This invokes the loop macro.
    • for n from 1 to 64: This is a loop clause. It declares a local variable n and specifies that the loop will iterate with n taking on values from 1 up to and including 64.
    • summing (square n): This is another loop clause that does the heavy lifting. For each value of n, it calls our (square n) function. The summing keyword tells the loop to maintain an internal accumulator, add the result of (square n) to it on each iteration, and return the final sum when the loop finishes.

This code is a perfect example of Lisp's readability. It almost reads like plain English: "Loop for n from 1 to 64, summing the result of square n."

Approach 2: The Optimized Mathematical Formula

While the loop works perfectly, it's not the most computationally efficient method. This problem is a classic example of a finite geometric series. The sum of the first k terms of a geometric series is given by the formula: Sk = a(1 - rk) / (1 - r), where a is the first term and r is the common ratio.

In our case, a = 1 (1 grain on the first square), r = 2 (doubling), and k = 64 (64 squares). Our sum is 20 + 21 + 22 + ... + 263. A simpler formula for a geometric series starting with 20 is just 2k - 1.

So, the total number of grains is simply 264 - 1.

The Common Lisp Implementation (Optimized)

This mathematical insight allows us to write a much faster function that performs a single calculation, regardless of the number of squares.


(defun total-optimized ()
  "Calculates total grains using the geometric series formula for O(1) efficiency."
  (- (expt 2 64) 1))

Code Walkthrough

  1. (defun total-optimized ()): We define our new, optimized function.
  2. (- (expt 2 64) 1): This is the entire logic.
    • (expt 2 64) calculates 2 to the power of 64.
    • The outer (- ... 1) function takes the result of the exponentiation and subtracts 1 from it.

Comparing the Approaches

Let's visualize the computational difference. The iterative approach performs 64 calculations, while the formulaic approach performs just one.

  Iterative Approach (O(n))          vs.          Direct Formula (O(1))
  ─────────────────────────                       ───────────────────────

    ● Start                                           ● Start
    │                                                 │
    ▼                                                 ▼
  ┌───────────┐                                     ┌──────────────────┐
  │ n = 1     │                                     │ Calculate 2^64   │
  │ total = 0 │                                     └─────────┬────────┘
  └─────┬─────┘                                               │
        │                                                     ▼
    ◆ n <= 64? ── Yes ───┐                            ┌──────────────────┐
    │      │             │                            │ Subtract 1       │
    │      No            │                            └─────────┬────────┘
    │      │             │                                      │
    ▼      ↓             ▼                                      ▼
  ┌───────┐      ┌─────────────────────┐                      ┌─────────┐
  │ Return│      │ total += square(n)  │                      │ Return  │
  │ total │      │ n++                 │                      │ result  │
  └───────┘      └─────────────────────┘                      └─────────┘
                       │      ▲
                       └──────┘

The table below summarizes the trade-offs.

Aspect Iterative Summation (loop) Direct Formula ((expt 2 64) - 1)
Performance Good. Proportional to the number of squares (O(n)). For 64 squares, it's instantaneous on modern hardware. Excellent. Constant time complexity (O(1)). The calculation time is the same for 64 squares or a million squares.
Readability Very high. The code clearly expresses the process of summing up each square's value. High, but requires understanding the underlying mathematical formula for a geometric series.
Extensibility More flexible. If the rule changed (e.g., "triple the grains on even squares"), the loop body could be easily modified. Less flexible. It's hard-coded to solve this specific geometric progression. A rule change would require deriving a new formula.
When to Use When the process is more important than the final result, or when the rules of iteration are complex and don't fit a simple formula. When computational efficiency is paramount and a known mathematical shortcut exists. Ideal for performance-critical code.

Where This Concept Applies in the Real World

The Grains problem is more than an academic exercise; it's a powerful illustration of exponential growth, a concept that appears everywhere.

  • Finance: Compound interest is a perfect example. Money in a savings account grows exponentially, which is why starting to save early makes a monumental difference over time.
  • Computer Science: Algorithm complexity. An algorithm with O(2n) complexity becomes impractical very quickly. A task that takes a second for n=20 could take centuries for n=60. Recognizing this pattern is crucial for writing scalable software.
  • Biology: Population growth and the spread of viruses often follow an exponential curve in their early stages, which is why early intervention is so critical during an epidemic.
  • Technology: Moore's Law, which observed that the number of transistors on a microchip doubled approximately every two years, was a long-running example of exponential growth in computing power.

Understanding this concept helps you make better long-term decisions, whether you're analyzing an investment, designing an algorithm, or simply appreciating how small, consistent changes can lead to massive outcomes. To explore more foundational concepts, check out our complete Common Lisp language guide.

Frequently Asked Questions (FAQ)

Why does the formula for a single square use n-1?

The sequence starts on square 1, not square 0. For the first square (n=1), we need 1 grain. The formula 2(n-1) gives us 2(1-1) = 20, and any number raised to the power of 0 is 1. This correctly seeds our sequence. If we used 2n, the first square would have 2 grains, which is incorrect according to the problem statement.

How can Common Lisp handle a number as large as the total grains?

Common Lisp has built-in support for arbitrary-precision integers, often called "bignums". Unlike languages that use fixed-size integers (like a 64-bit long), which would overflow and produce an incorrect result, Common Lisp automatically allocates more memory for a number as it grows. The total number of grains, 18,446,744,073,709,551,615, is handled without any special libraries or data types. This is a significant advantage for mathematical and scientific computing.

What is the purpose of defpackage and in-package?

They are Common Lisp's namespacing system. defpackage creates a new namespace to hold a set of related functions, variables, and other symbols. This prevents name collisions. For example, you could have a function named total in your grains package and another function named total in an accounting package without them interfering. in-package sets the current namespace, so any new definitions are placed inside it.

Is the loop macro considered good practice in Common Lisp?

Absolutely. While some functional programming purists might prefer recursive solutions, the loop macro is highly idiomatic, powerful, and often more readable and efficient in Common Lisp. Its declarative syntax (e.g., summing, collecting, for) allows developers to express complex iterations clearly. It is compiled down to highly efficient machine code and is a standard tool in any professional Lisp programmer's toolkit.

Why is the direct formula (expt 2 64) - 1 so much more efficient?

It relates to computational complexity. The iterative solution has a time complexity of O(n), where 'n' is the number of squares. It must perform 64 separate additions and exponentiations. The direct formula has a time complexity of O(1), or constant time. It performs only one exponentiation and one subtraction, regardless of whether there are 64 or 64 million squares. For small numbers like 64, the difference is negligible, but for larger inputs, the O(1) solution is exponentially faster.

Could this problem be solved recursively?

Yes, it could. A recursive solution for the total might look something like this: (defun total-recursive (n) (if (= n 1) 1 (+ (square n) (total-recursive (1- n))))). However, this is generally less efficient in Common Lisp than the loop macro due to function call overhead. While it's a good academic exercise, the iterative or direct formula approaches are preferred in practice for this specific problem.

Conclusion: More Than Just Grains of Wheat

The Grains problem, as explored in the kodikra.com curriculum, serves as a perfect microcosm of computational problem-solving. We began with a simple story, translated it into a mathematical formula, and implemented it using the elegant and powerful features of Common Lisp. We saw how the language's built-in bignum support removes barriers, and how its expressive syntax allows for clear, readable solutions.

More importantly, we contrasted two valid approaches—iterative summation and a direct mathematical formula—revealing a crucial lesson in software engineering: understanding the problem deeply can often lead to a more efficient solution by leveraging mathematics. The staggering final number serves as a permanent, visceral reminder of the power of exponential growth, a pattern that shapes our world from finance to technology.

Disclaimer: The code and explanations in this article are based on modern Common Lisp standards and are compatible with implementations like Steel Bank Common Lisp (SBCL). The core concepts are stable and future-proof.

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

Post a Comment