Rational Numbers in Cairo: Complete Solution & Deep Dive Guide
From Zero to Hero: Building Rational Numbers in Cairo
Master rational number implementation in Cairo by creating a custom struct with a numerator and denominator. This guide covers core operations like addition, subtraction, multiplication, and division, emphasizing simplification using the Greatest Common Divisor (GCD) for robust, provable arithmetic on Starknet.
Have you ever been blindsided by a floating-point error? That frustrating moment when you discover that in most programming languages, 0.1 + 0.2 doesn't precisely equal 0.3. These tiny inaccuracies can cascade into significant bugs, especially in financial applications or scientific simulations where precision is non-negotiable. In the world of blockchains and zero-knowledge proofs, such ambiguity is unacceptable.
This is where the mathematical concept of rational numbers comes to the rescue. By representing numbers as a precise fraction of two integers, we eliminate rounding errors entirely. This guide will walk you through building a robust Rational number type from scratch in Cairo, a language designed for provable computation. You'll learn not just the code, but the fundamental principles that make this approach essential for developing secure and deterministic applications on Starknet.
What Are Rational Numbers?
At its core, a rational number is any number that can be expressed as a fraction or quotient a/b of two integers. Here, a is the numerator, and b is the denominator. There's one critical rule: the denominator b cannot be zero, as division by zero is mathematically undefined.
For example, 1/2, -3/4, and 5/1 (which is just 5) are all rational numbers. This structure allows us to represent values with perfect precision. The number 0.5 is stored not as a binary approximation, but as the exact integer pair (1, 2). This is a game-changer compared to floating-point types (like f64 in Rust), which often store approximations for fractional values.
In Cairo, we can model this concept elegantly using a struct. A struct is a custom data type that lets you group together related values into a meaningful package. For our rational number, we'll create a Rational struct containing two fields: a numerator and a denominator, both of which will be integers (i128 to handle negative values and a wide range).
// In Cairo, we define a custom type using the `struct` keyword.
// We derive some useful traits for debugging and memory management.
#[derive(Copy, Drop, Debug, PartialEq)]
struct Rational {
numerator: i128,
denominator: i128,
}
This simple declaration is the foundation upon which we will build all our arithmetic logic. By encapsulating the numerator and denominator, we create a new, powerful type that brings mathematical purity to our code.
Why Do You Need Rational Numbers in Cairo?
The "why" is arguably the most important question. While Cairo's native felt252 is powerful for field arithmetic, it doesn't natively handle fractional computation. One might be tempted to use fixed-point arithmetic (scaling integers by a large factor like 10^18), which is common in Solidity. However, rational numbers offer distinct advantages, especially in the context of ZK-proofs and Starknet.
-
Absolute Precision: This is the primary benefit. In decentralized finance (DeFi), a tiny rounding error in an interest calculation, when compounded over thousands of transactions, can lead to significant financial discrepancies and exploits. Rational numbers ensure that
1/3is always exactly1/3, not0.333333333...truncated. - Determinism and Provability: Starknet relies on provable computation. Every calculation must be deterministic—producing the exact same output for the same input, every single time. Floating-point arithmetic is notoriously non-deterministic across different hardware architectures. Rational number arithmetic, being based on integer operations, is perfectly deterministic and thus ideal for ZK-proofs.
-
Clarity and Readability: Representing a financial value like "one-quarter of a token" as
Rational { numerator: 1, denominator: 4 }is more explicit and less error-prone than managing a scaled integer and remembering the scaling factor. It makes the code's intent clearer. - Avoiding Overflow with Intermediate Calculations: When performing a chain of multiplications and divisions, using rational numbers can help manage intermediate results. You can perform all multiplications on the numerators and denominators first, and only perform the final division at the very end, reducing the risk of premature truncation or loss of precision.
In essence, using rational numbers in Cairo isn't just a technical choice; it's a commitment to mathematical correctness and security, which are paramount in the blockchain space.
How to Implement Rational Numbers in Cairo
Now we get to the practical implementation. We'll build our Rational number type step-by-step, from creation to arithmetic operations. This process follows a structured approach from the kodikra learning path, ensuring a solid understanding of each component.
Step 1: Setting Up Your Scarb Project
First, ensure you have the Cairo toolchain installed. Then, create a new project using Scarb, the Cairo package manager.
scarb new rational_numbers
cd rational_numbers
This command creates a new library project. All our code will go into the src/lib.cairo file.
Step 2: Defining the `Rational` Struct and Constructor
As shown before, we define our struct. But a struct alone isn't enough; we need a safe way to create instances of it. We'll create an implementation block impl Rational and add a constructor function, typically named new.
This constructor must enforce the golden rule: the denominator cannot be zero. We use Cairo's assert function to enforce this condition. If the assertion fails, the program will panic and revert, preventing the creation of an invalid state.
#[derive(Copy, Drop, Debug, PartialEq)]
struct Rational {
numerator: i128,
denominator: i128,
}
impl RationalImpl of Rational {
// Constructor function to create a new Rational number.
fn new(numerator: i128, denominator: i128) -> Rational {
// Critical check: The denominator must not be zero.
assert(denominator != 0, 'Denominator cannot be zero');
// Create and return an instance of the struct.
Rational { numerator, denominator }
}
}
Step 3: The Key to Simplicity - The Greatest Common Divisor (GCD)
A rational number like 2/4 is mathematically identical to 1/2. To keep our numbers in their simplest, most canonical form, we should always simplify them. This prevents the numerator and denominator from growing unnecessarily large and makes equality checks straightforward (e.g., checking if 2/4 == 1/2).
The method for simplification is to divide both the numerator and denominator by their Greatest Common Divisor (GCD). We'll implement the classic Euclidean algorithm to find the GCD. We'll add this as a private helper function within our implementation.
// Inside the `impl RationalImpl of Rational` block:
// Private helper function to compute the Greatest Common Divisor.
// Uses the Euclidean algorithm.
fn gcd(mut a: i128, mut b: i128) -> i128 {
// Ensure we work with positive numbers for the algorithm.
if a < 0 {
a = -a;
}
if b < 0 {
b = -b;
}
while b != 0 {
let temp = b;
b = a % b;
a = temp;
}
a
}
Now, we can create an enhanced constructor, `new_simplified`, that automatically creates the rational number in its simplest form.
// Inside the `impl RationalImpl of Rational` block:
fn new_simplified(numerator: i128, denominator: i128) -> Rational {
assert(denominator != 0, 'Denominator cannot be zero');
// Handle the sign. The sign should be carried by the numerator.
// If denominator is negative, flip the signs of both.
let mut num = numerator;
let mut den = denominator;
if den < 0 {
num = -num;
den = -den;
}
// Find the common divisor.
let common_divisor = Self::gcd(num, den);
// Simplify and return the new Rational number.
Rational {
numerator: num / common_divisor,
denominator: den / common_divisor,
}
}
This flow demonstrates a robust way to create rational numbers, ensuring validity and canonical form from the start.
● Start
│
▼
┌───────────────────┐
│ fn new_simplified │
│ (num, den) │
└─────────┬─────────┘
│
▼
◆ den == 0 ? ◆
╱ ╲
Yes (Panic) No
│ │
💥 ▼
[Revert] ┌────────────────┐
│ Normalize Sign │
│ den must be > 0│
└────────┬───────┘
│
▼
┌───────────┐
│ Calculate │
│ gcd(num, den) │
└─────┬─────┘
│
▼
┌───────────┐
│ Simplify: │
│ num /= gcd│
│ den /= gcd│
└─────┬─────┘
│
▼
┌───────────┐
│ Return │
│ Rational │
└───────────┘
│
▼
● End
Step 4: Implementing Arithmetic Traits
To make our Rational type useful, we need to teach it how to perform basic arithmetic like addition, subtraction, multiplication, and division. In Cairo, we do this by implementing standard operator traits from the core library, such as Add, Sub, Mul, and Div. This allows us to use familiar operators like +, -, *, and / directly on our Rational objects.
Addition (`+`)
The formula for adding two fractions a/b + c/d is (ad + bc) / bd. We implement the Add trait to reflect this logic.
use core::ops::Add;
impl AddRational of Add<Rational> {
fn add(self: Rational, rhs: Rational) -> Rational {
let new_numerator = self.numerator * rhs.denominator + rhs.numerator * self.denominator;
let new_denominator = self.denominator * rhs.denominator;
// Always return the simplified form.
RationalImpl::new_simplified(new_numerator, new_denominator)
}
}
Subtraction (`-`)
The formula for subtracting a/b - c/d is (ad - bc) / bd.
use core::ops::Sub;
impl SubRational of Sub<Rational> {
fn sub(self: Rational, rhs: Rational) -> Rational {
let new_numerator = self.numerator * rhs.denominator - rhs.numerator * self.denominator;
let new_denominator = self.denominator * rhs.denominator;
RationalImpl::new_simplified(new_numerator, new_denominator)
}
}
Multiplication (`*`)
Multiplication is simpler: (a/b) * (c/d) = ac / bd.
use core::ops::Mul;
impl MulRational of Mul<Rational> {
fn mul(self: Rational, rhs: Rational) -> Rational {
let new_numerator = self.numerator * rhs.numerator;
let new_denominator = self.denominator * rhs.denominator;
RationalImpl::new_simplified(new_numerator, new_denominator)
}
}
Division (`/`)
Division involves inverting the second fraction and multiplying: (a/b) / (c/d) = (a/b) * (d/c) = ad / bc. We must also add a check to prevent division by a rational number that is zero (i.e., its numerator is zero).
use core::ops::Div;
impl DivRational of Div<Rational> {
fn div(self: Rational, rhs: Rational) -> Rational {
// A rational number is zero if its numerator is zero.
assert(rhs.numerator != 0, 'Division by zero');
let new_numerator = self.numerator * rhs.denominator;
let new_denominator = self.denominator * rhs.numerator;
RationalImpl::new_simplified(new_numerator, new_denominator)
}
}
This diagram illustrates the logic for adding two rational numbers, which is the most complex of the basic operations.
● Start: Add Rational A (n1/d1) and B (n2/d2)
│
├───── A: Rational {n1, d1}
│
└───── B: Rational {n2, d2}
│
▼
┌──────────────────────────┐
│ Calculate New Numerator │
│ num = (n1 * d2) + (n2 * d1) │
└────────────┬─────────────┘
│
▼
┌──────────────────────────┐
│ Calculate New Denominator│
│ den = d1 * d2 │
└────────────┬─────────────┘
│
▼
┌──────────────────────────┐
│ Call `new_simplified` │
│ with (num, den) │
└────────────┬─────────────┘
│
├─ 1. Normalize Sign
│
├─ 2. Calculate GCD
│
└─ 3. Simplify
│
▼
● End: Resulting Simplified Rational
Full Solution Code
Here is the complete, well-commented code for src/lib.cairo. This solution combines all the concepts discussed above into a reusable and robust module. It is based on the problem-solving patterns taught in the exclusive kodikra.com Cairo curriculum.
use core::ops::{Add, Sub, Mul, Div};
/// A struct representing a rational number with a numerator and a denominator.
///
/// We derive several traits for convenience:
/// - `Copy`: Allows instances to be copied by value.
/// - `Drop`: Allows instances to be automatically deallocated.
/// - `Debug`: Allows for easy printing during debugging.
/// - `PartialEq`: Allows for direct comparison with `==`.
#[derive(Copy, Drop, Debug, PartialEq)]
struct Rational {
numerator: i128,
denominator: i128,
}
impl RationalImpl of Rational {
/// Creates a new Rational number.
///
/// # Arguments
/// * `numerator` - The numerator of the rational number.
/// * `denominator` - The denominator of the rational number.
///
/// # Panics
/// Panics if the denominator is zero.
fn new(numerator: i128, denominator: i128) -> Rational {
assert(denominator != 0, 'Denominator cannot be zero');
Rational { numerator, denominator }
}
/// Creates a new Rational number in its simplest canonical form.
/// - The denominator is always positive.
/// - The fraction is reduced by the greatest common divisor.
fn new_simplified(numerator: i128, denominator: i128) -> Rational {
assert(denominator != 0, 'Denominator cannot be zero');
let mut num = numerator;
let mut den = denominator;
// Ensure the denominator is always positive for a canonical representation.
if den < 0 {
num = -num;
den = -den;
}
let common_divisor = Self::gcd(num, den);
Rational { numerator: num / common_divisor, denominator: den / common_divisor, }
}
/// Computes the greatest common divisor (GCD) of two numbers using the Euclidean algorithm.
/// This is a private helper function.
fn gcd(mut a: i128, mut b: i128) -> i128 {
// The algorithm works with absolute values.
if a < 0 {
a = -a;
}
if b < 0 {
b = -b;
}
while b != 0 {
let temp = b;
b = a % b;
a = temp;
}
a
}
}
/// Implementation of the Add trait for Rational numbers.
/// Formula: a/b + c/d = (ad + bc) / bd
impl AddRational of Add<Rational> {
fn add(self: Rational, rhs: Rational) -> Rational {
let new_numerator = self.numerator * rhs.denominator + rhs.numerator * self.denominator;
let new_denominator = self.denominator * rhs.denominator;
RationalImpl::new_simplified(new_numerator, new_denominator)
}
}
/// Implementation of the Sub trait for Rational numbers.
/// Formula: a/b - c/d = (ad - bc) / bd
impl SubRational of Sub<Rational> {
fn sub(self: Rational, rhs: Rational) -> Rational {
let new_numerator = self.numerator * rhs.denominator - rhs.numerator * self.denominator;
let new_denominator = self.denominator * rhs.denominator;
RationalImpl::new_simplified(new_numerator, new_denominator)
}
}
/// Implementation of the Mul trait for Rational numbers.
/// Formula: (a/b) * (c/d) = ac / bd
impl MulRational of Mul<Rational> {
fn mul(self: Rational, rhs: Rational) -> Rational {
let new_numerator = self.numerator * rhs.numerator;
let new_denominator = self.denominator * rhs.denominator;
RationalImpl::new_simplified(new_numerator, new_denominator)
}
}
/// Implementation of the Div trait for Rational numbers.
/// Formula: (a/b) / (c/d) = ad / bc
impl DivRational of Div<Rational> {
fn div(self: Rational, rhs: Rational) -> Rational {
assert(rhs.numerator != 0, 'Division by zero rational');
let new_numerator = self.numerator * rhs.denominator;
let new_denominator = self.denominator * rhs.numerator;
RationalImpl::new_simplified(new_numerator, new_denominator)
}
}
Pros and Cons of Using Rational Numbers
Like any technical solution, using a custom rational number type comes with trade-offs. It's crucial to understand them to decide when this approach is appropriate for your project.
| Pros | Cons |
|---|---|
| Perfect Precision: Eliminates floating-point rounding errors entirely, which is critical for financial and scientific applications. | Performance Overhead: Operations involve multiple integer multiplications and a GCD calculation, making them slower than native integer or felt arithmetic. |
| Deterministic: All calculations are based on integer arithmetic, guaranteeing the same result every time, which is essential for provable systems like Starknet. | Increased Memory Usage: A Rational number stores two i128 integers, consuming more memory than a single felt252 or fixed-point integer. |
Conceptual Clarity: The code's intent is very clear. A value of 1/3 is explicitly represented as such, improving maintainability and reducing bugs. |
Risk of Overflow: The numerator and denominator can grow very large during intermediate calculations, potentially exceeding the bounds of i128. This requires careful management. |
Composability: A well-designed Rational type can be easily composed and used in more complex mathematical libraries and protocols. |
Complexity: It adds a layer of abstraction. Developers need to understand how the type works internally, especially regarding simplification and potential panics. |
Frequently Asked Questions (FAQ)
1. What is the main advantage of rational numbers over fixed-point numbers?
The main advantage is dynamic precision. Fixed-point numbers have a fixed number of decimal places (e.g., 18 decimals in many ERC20 tokens). Rational numbers can represent any fraction exactly, like 1/3 or 1/7, which fixed-point numbers can only approximate. This prevents precision loss during chained calculations involving divisions.
2. Why is the `gcd` function so important?
The Greatest Common Divisor (GCD) is crucial for two reasons. First, it keeps rational numbers in their simplest, or "canonical," form (e.g., 2/4 becomes 1/2). This makes equality checks reliable. Second, it prevents the numerator and denominator from growing excessively large after a series of arithmetic operations, which helps mitigate the risk of integer overflow.
3. Can the numerator or denominator become too large?
Yes. This is a significant risk. If you multiply many rational numbers together, the numerator and denominator can grow exponentially and potentially overflow the i128 type. For applications requiring extremely large numbers, you might need to use a big integer library and integrate it into the Rational struct, though this comes with a greater performance cost.
4. How do you represent a whole number, like 5, as a Rational?
Any whole number n can be represented as a rational number by using 1 as the denominator. For example, the integer 5 would be created as Rational::new_simplified(5, 1).
5. Why did we choose `i128` instead of `felt252`?
We used i128 (a 128-bit signed integer) primarily because rational numbers need to handle negative values, and standard integer arithmetic (addition, subtraction, multiplication, division, modulo) is more direct and intuitive with integer types. While felt252 is the native field element in Cairo, its arithmetic is modular, which complicates the implementation of standard rational number behavior and the Euclidean algorithm for GCD.
6. Are there pre-built libraries for rational numbers in the Cairo ecosystem?
As the Cairo ecosystem matures, community-developed libraries (often called Scarb packages) are becoming more common. It is likely that a standard math library containing a robust rational number implementation will emerge. However, understanding how to build one from scratch, as covered in this kodikra module, provides deep insight into Cairo's type system, traits, and computational constraints.
Conclusion and Next Steps
You have successfully built a fully functional, precise, and deterministic Rational number type in Cairo. By moving beyond native types and implementing custom logic, you've unlocked a powerful tool for building applications where mathematical correctness is paramount. You've learned how to structure data with structs, encapsulate logic in impl blocks, and leverage the power of traits to integrate your custom type seamlessly with Cairo's core operators.
The principles of ensuring validity through assertions, maintaining a canonical form via simplification, and handling edge cases are fundamental to writing secure and robust smart contracts. This exercise is a significant step in your journey to mastering provable computation on Starknet.
To continue building on this foundation, explore how this Rational type can be used in more complex algorithms, such as those found in financial modeling, geometric calculations, or advanced DeFi protocols. Continue your journey on the kodikra learning path to tackle even more advanced challenges and solidify your expertise.
Technology Disclaimer: The code and concepts in this article are based on Cairo version 2.6.x and Scarb 0.8.x. The Cairo language is evolving, so syntax and library functions may change in future versions. Always consult the official documentation for the latest updates.
Published by Kodikra — Your trusted Cairo learning resource.
Post a Comment