Math with Rust

About three years ago, I decided to inaugurate a new challenge in my life: pursuing a Bachelor’s degree in Computational Applied Mathematics. This marked my return to the academic world 15 years after my first college experience.

I found myself in a highly rigorous program at a demanding institution. To make things even more complicated, the class schedules were far from ideal for a software developer working a standard 8-hour commercial shift.

Yet, in a way, it has been deeply rewarding. It opened up a vast horizon of possibilities for both my professional and academic career — in fact, I hope to begin my Master’s degree soon.

During this return to academia, I gave much more focus to mathematics than to programming. I dove deep into algorithms — numerical approximation algorithms, linear programming, a myriad of ways to interact with graphs, and highly useful algorithms for calculus and parallel processing. The list is immense, and I am already looking forward to understanding genetic algorithms in the near future.

Along the way, I realized how certain mathematical algorithms are invaluable across an enormous scope of problems. I classified them, developed implementations for them, and now I want to share a bit of each with you. Over this series, I will demonstrate their implementations in Rust and highlight interesting use cases for each.

Get Serodio.dev’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

In my classification, I organized these algorithms into 7 distinct modules. In this introductory article, I will keep things more abstract, bringing in some theory and describing what each group is typically used for. This will lay the groundwork for upcoming articles where we will dive into the Rust code for each specific module.

🚀 Module 1: Algebraic Foundations and Divide and Conquer

The focus of this initial module is to show how naive $O(n)$ approaches can be elegantly transformed into $O(\log n)$ operations using the Divide and Conquer paradigm.

• Fast Exponentiation: x^n = (x^(n/2))². The purest example of Divide and Conquer, turning linear multiplication into logarithmic steps. It is heavily utilized in modern cryptography.
• Bisection Method / Continuous Binary Search: A method for finding roots of continuous functions (e.g., calculating √x or log_b(x)) by repeatedly halving the search interval. Crucial for numerical analysis and physics simulations.
• Arithmetic and Geometric Progressions (AP & GP): Formulas like S_n = n(a₁ + aₙ) / 2. Eliminates heavy O(n) loops with O(1) direct mathematics. Widely used in financial modeling and algorithm complexity analysis.
• Logarithms: log_b(x) and ln(x). Essential for data scaling, modeling continuous growth, and understanding the theoretical limits of data structures.

🧠 Module 2: Array Optimization and Linear State

A smooth transition into Basic Dynamic Programming and continuous data processing.

• Kadane’s Algorithm: Finds the maximum contiguous subarray sum (max(sum(A[i...j]))) in strictly O(n) time using cumulative state. Widely applied in financial data analysis to pinpoint peak profit periods.
• Prefix Sums: P[i] = P[i-1] + A[i]. Allows systems to answer multiple range-sum queries in O(1) time after a single O(n) preprocessing step. Essential in image processing and 2D grid analytics.
• Computational Divisibility Criteria: Fast checks without repeatedly invoking the expensive modulo operator (e.g., digit sums). Useful in parsing and large-scale data validation.

🔢 Module 3: Computational Number Theory

Focused on manipulating integers with extreme efficiency and batch processing, leveraging greedy approaches and sieves.

• Modular Arithmetic: The definitive method for preventing integer overflow in programming. Its distributive properties are foundational for hashing and competitive programming.
• Greatest Common Divisor (Euclidean Algorithm): A brilliant example of fast, tail-optimized recursion. Used heavily in fraction simplification and cryptography.
• Least Common Multiple (LCM): LCM(a, b) = |a * b| / GCD(a, b). Vital for scheduling problems and synchronizing periodic events.
• Sieve of Eratosthenes: Generates prime numbers in O(N log(log N)) time. The absolute backbone of prime generation for factorization engines.
• Integer Factorization (Optimized Trial Division): Factoring numbers up to √N using primes generated by the Sieve. Used in cryptography breaking analysis.

🛡️ Module 4: Advanced Number Theory

The math behind RSA and digital security. This module is ideal for highly technical, cryptography-focused architectures.

• Extended Euclidean Algorithm: a*x + b*y = GCD(a, b). The algorithm that runs "in reverse" to find Bézout coefficients.
• Modular Multiplicative Inverse: Essential for safely performing division within modular arithmetic environments.
• Fermat’s Little Theorem: a^(p-1) ≡ 1 (mod p). Used to find modular inverses incredibly fast when the modulo is a prime number.
• Euler’s Totient Function: φ(n). Counts the integers up to n that are relatively prime to n. This is the mathematical core of RSA encryption.
• Miller-Rabin Primality Test: A powerful probabilistic algorithm. One of the best practical applications of Fast Exponentiation and Number Theory working together to check massive primes in milliseconds.

🔄 Module 5: Sequences, Decision Trees, and Memoization

The “heart” of the series: where pure mathematics meets the physical time and space limitations of the CPU.

• Fibonacci Sequence: Moving from a naive O(2^n) recursion that chokes the CPU, to O(n) via Memoization (Top-Down) and Tabulation (Bottom-Up).
• Collatz Conjecture: Using Hash Maps and Dictionaries to memoize previously computed paths, saving recursive jumps in chaotic sequences.
• Tower of Hanoi: Leveraging recursion to manage identical sub-problems, teaching us how to standardize state-tree management.
• Matrix Exponentiation: The masterclass technique for calculating the n-th term of linear recurrences (like Fibonacci) in an incredible O(log n) time, brilliantly merging Divide and Conquer with Linear Algebra.

🎲 Module 6: Computational Combinatorics and Inclusion-Exclusion

How to calculate massive possibilities in a feasible timeframe while safely applying bounds.

• Factorials & Fundamental Counting Principle: Precomputing factorials for rapid combination queries in probability algorithms.
• Newton’s Binomial & Permutations with Repetition: Calculating anagrams and polynomial coefficients efficiently.
• Pascal’s Triangle: Dynamic Programming matrix construction C(n, k) = C(n-1, k-1) + C(n-1, k).
• Derangements (Subfactorials): The number of permutations where no element is in its original position. A classic example of DP modeling: D_n = (n-1) * (D_n-1 + D_n-2).
• Catalan Numbers: Applied to data structures (e.g., calculating exactly how many different binary search trees can be formed with n nodes).
• Principle of Inclusion-Exclusion: Calculating complex intersection areas in Venn diagrams and combinatorial sets.

📐 Module 7: Discrete Geometry and Set Theory

Visual processing, geometric bounds, and lightning-fast bitwise operations.

• Pick’s Theorem: Area = i + (b/2) - 1. Beautiful algebra applied to 2D grids to find polygon areas using strictly integer points.
• Shoelace Formula (Gauss’s Area Formula): The perfect companion to Pick. Calculates the area of any polygon using the coordinates of its vertices. Computationally excellent because it relies solely on cross-multiplications and additions within a 2D array.
• Boolean Algebra & Bitwise Operations: Using binary representation (&, |, ^, ~) to simulate Set Union, Intersection, and Difference at bare-metal speeds.
• Pólya Enumeration Theorem / Burnside’s Lemma: Counting graphs and geometric shapes while properly mathematically accounting for symmetries (rotations and reflections).

Final Thoughts

In the next steps of this series, I will bring the complete Rust implementation for each group. I will also provide the link to my GitHub repository where I keep all these algorithms thoroughly tested — feel free to explore it.

As an additional thought: I always looked at software engineering and wondered if it was really what I wanted to do for the rest of my life. I genuinely love programming, and I love technology, but at a knowledge level, it always seemed like a very small universe.

As soon as I started programming mathematically, I realized something profound: there is nothing in programming that exists outside of mathematics. Programming is, at its core, a subset belonging to a much larger mathematical set — and that larger set still has so much left to teach me.