Ten Little Algorithms, Part 8: Miller-Rabin Primality Test (and Living with Uncertainty)
Part 8 of the Ten Little Algorithms series: A look at the Miller-Rabin primality test, along with Pollard's rho algorithm for factoring, and some perspectives on very low levels of uncertainty.
Monte Carlo Integration
Monte Carlo integration looks deceptively simple, estimate an area by throwing random points at it and counting hits. Jason Sachs uses that idea to approximate pi, compare error scaling, and then show why the same approach becomes far more useful in higher dimensions. He also demonstrates a stratified sampling trick that improves accuracy by spending samples where they matter most.
Breaking AES with an Oscilloscope
AES is a powerful encryption algorithm that protects some our most important secrets. But did you know that many devices are inadvertently leaking the value of their private key through their power pins?! Join me in this special preview of my upcoming workshop at the Embedded Systems Summit (14-16 October 2025 in San Jose, CA) as we explore the world of hardware security and discover just how easy it could be to break AES encryption with only an oscilloscope and some math.
Linear Feedback Shift Registers for the Uninitiated
Jason Sachs assembled an eighteen-part deep dive into linear feedback shift registers, connecting the simple shift-register circuit to finite-field algebra and practical tools. The series walks through primitive polynomials, Berlekamp-Massey state recovery, libgf2-based analysis, discrete-log methods, and real-world uses from PRNGs and Gold codes to Reed-Solomon and CRC reverse-engineering. It’s a single reference for engineers who want both theory and working code.
Getting Started With CUDA C on an Nvidia Jetson: Hello CUDA World!
In this blog post, I introduce CUDA, which is a framework designed to allow developers to take advantage of Nvidia's GPU hardware acceleration to efficiently implement certain type of applications. I demonstrate an implementation to perform vector addition using CUDA C and compare it against the traditional implementation in "regular" C.
Ten Little Algorithms, Part 7: Continued Fraction Approximation
In this article we explore the use of continued fractions to approximate any particular real number, with practical applications.
Remember Y2K?
There was fear that the turn of the century at the end of 1999 would cause problems with many embedded systems. There is evidence that the same issue may occur in 2038.
Elliptic Curve Cryptography - Multiple Signatures
Point pairings let you compress many independent elliptic-curve signatures into a single verification, reducing n checks to one. This post explains how each signer derives a coefficient from the ordered list of public keys, aggregates signatures on the base group and public keys on the extension group, and verifies everything with one pairing computation. It also flags practical cautions like key validation and agreed ordering.
Flood Fill, or: The Joy of Resource Constraints
When transferred from the PC world to a microcontroller, a famous, tried-and-true graphics algorithm is no longer viable. The challenge of creating an alternative under severe resource constraints is an intriguing puzzle, the kind that keeps embedded development fun and interesting.
Elliptic Curve Cryptography - Extension Fields
An introduction to the pairing of points on elliptic curves. Point pairing normally requires curves over an extension field because the structure of an elliptic curve has two independent sets of points if it is large enough. The rules of pairings are described in a general way to show they can be useful for verification purposes.
Tolerance Analysis
Jason Sachs walks through practical tolerance analysis by designing a 24V overvoltage detector from the ground up, combining resistor tolerances, temperature coefficients, reference and comparator errors, hysteresis, and dynamic RC behavior. He demonstrates worst-case stacking with real datasheet numbers, shows how solder and mechanical stress affect resistor choice, and sizes filtering so the comparator meets a microsecond-range trip requirement. The article is a hands-on guide full of worked examples and trade-offs for embedded hardware engineers.
Chebyshev Approximation and How It Can Help You Save Money, Win Friends, and Influence People
Are expensive math libraries or huge lookup tables eating CPU and flash on your microcontroller? In this practical guide Jason Sachs shows how Chebyshev polynomial approximation (with range reduction, splitting, and small interpolated tables) can give near-minimax accuracy while using far less code and runtime. The post compares Taylor series, plain and interpolated tables, and explains how to fit empirical sensor data and evaluate coefficients efficiently.
Ten Little Algorithms, Part 2: The Single-Pole Low-Pass Filter
Jason Sachs shows how a single-pole IIR low-pass filter, implementable in one line y += alpha * (x - y), tames noise in embedded signals without floating point. The post explains how to compute alpha from tau and delta-t, practical tradeoffs like phase lag and oversampling, and fixed-point pitfalls including how many extra state bits you need to avoid quantization. Short, practical, and code-ready.
Ten Little Algorithms, Part 8: Miller-Rabin Primality Test (and Living with Uncertainty)
Part 8 of the Ten Little Algorithms series: A look at the Miller-Rabin primality test, along with Pollard's rho algorithm for factoring, and some perspectives on very low levels of uncertainty.
Return of the Delta-Sigma Modulators, Part 1: Modulation
Jason Sachs returns to delta-sigma modulators with a hands-on, code-first treatment that focuses on the DAC side of things. Part 1 walks through first- and second-order kernels, linearized analysis, spectra, and practical coefficient choices while illustrating results with Python simulations. Expect clear rules of thumb for A, R, and B, a derivation of noise shaping behavior, and a useful error bound for RC filtering.
Elliptic Curve Cryptography - Basic Math
An introduction to the math of elliptic curves for cryptography. Covers the basic equations of points on an elliptic curve and the concept of point addition as well as multiplication.
Understanding and Preventing Overflow (I Had Too Much to Add Last Night)
Integer overflow is stealthier than you think, and in embedded systems it can break control loops or corrupt data. Jason Sachs walks through the usual culprits, including addition, subtraction, multiplication, shifting and Q15 fixed-point traps, plus C-specific pitfalls such as undefined signed overflow and INT_MIN edge cases. He then lays out practical defenses: prefer fixed-width types, widen and saturate intermediates, enable wraparound where appropriate, and reason about modular congruence for compound arithmetic.
PID Without a PhD
You do not need control theory to implement useful PID loops in embedded projects. Tim Wescott walks through simple, ready-to-use C code, clear explanations of P, I and D terms, and a practical tuning recipe you can apply to motors, precision actuators, and heaters. The article highlights anti-windup, sampling-rate guidance, and when to call in a control expert.
Second-Order Systems, Part I: Boing!!
Jason Sachs takes the spring 'boing' of a doorstop into the math of second-order systems, using the series LRC circuit as a concrete example. He shows two standard transfer-function forms, explains why ωn only scales time while ζ sets the response shape, and derives pole locations plus an exact overshoot formula that helps tune embedded-system responses.
Ten Little Algorithms, Part 3: Welford's Method (and Friends)
Jason Sachs takes a practical look at Welford's method, a numerically stable online algorithm for computing mean and sample variance without storing large batches. He demonstrates Python implementations, shows why the naive sum and sum-of-squares approach suffers catastrophic cancellation, and why Welford is a better fit for memory- and CPU-constrained embedded systems. Jason then turns Welford into simple filters for tracking time-varying noise and discusses heuristic fixes and tradeoffs.
Chebyshev Approximation and How It Can Help You Save Money, Win Friends, and Influence People
Are expensive math libraries or huge lookup tables eating CPU and flash on your microcontroller? In this practical guide Jason Sachs shows how Chebyshev polynomial approximation (with range reduction, splitting, and small interpolated tables) can give near-minimax accuracy while using far less code and runtime. The post compares Taylor series, plain and interpolated tables, and explains how to fit empirical sensor data and evaluate coefficients efficiently.
Understanding and Preventing Overflow (I Had Too Much to Add Last Night)
Integer overflow is stealthier than you think, and in embedded systems it can break control loops or corrupt data. Jason Sachs walks through the usual culprits, including addition, subtraction, multiplication, shifting and Q15 fixed-point traps, plus C-specific pitfalls such as undefined signed overflow and INT_MIN edge cases. He then lays out practical defenses: prefer fixed-width types, widen and saturate intermediates, enable wraparound where appropriate, and reason about modular congruence for compound arithmetic.
Ten Little Algorithms, Part 2: The Single-Pole Low-Pass Filter
Jason Sachs shows how a single-pole IIR low-pass filter, implementable in one line y += alpha * (x - y), tames noise in embedded signals without floating point. The post explains how to compute alpha from tau and delta-t, practical tradeoffs like phase lag and oversampling, and fixed-point pitfalls including how many extra state bits you need to avoid quantization. Short, practical, and code-ready.
Help, My Serial Data Has Been Framed: How To Handle Packets When All You Have Are Streams
Framing byte streams is easier to get wrong than you think, and a bad scheme can leave your embedded device acting on the wrong packet. Jason Sachs walks through common plaintext and binary framing approaches, explains why CRCs alone can still permit false resynchronization, and demonstrates COBS as a simple, low-overhead byte-stuffing method that prevents delimiter collisions and guarantees resynchronization.
How to Build a Fixed-Point PI Controller That Just Works: Part I
Jason Sachs digs into the implementation choices that make a fixed-point PI controller reliable in real embedded systems. He focuses on practical fixes rather than tuning: prefer scale-then-integrate, fold the timestep into the integral gain, and apply anti-windup so saturations and sensor noise do not break the loop. Part I covers discrete-time pitfalls and sets up fixed-point scaling issues for Part II.
Ten Little Algorithms, Part 3: Welford's Method (and Friends)
Jason Sachs takes a practical look at Welford's method, a numerically stable online algorithm for computing mean and sample variance without storing large batches. He demonstrates Python implementations, shows why the naive sum and sum-of-squares approach suffers catastrophic cancellation, and why Welford is a better fit for memory- and CPU-constrained embedded systems. Jason then turns Welford into simple filters for tracking time-varying noise and discusses heuristic fixes and tradeoffs.
How to Estimate Encoder Velocity Without Making Stupid Mistakes: Part II (Tracking Loops and PLLs)
Jason Sachs explains why simple differentiation of encoder counts often fails and how tracking loops and PLLs give more robust velocity estimates. Using a pendulum thought experiment and Python examples, he shows how a PI-based tracking loop reduces noise and eliminates steady-state ramp error, and why vector PLLs with quadrature mixing avoid cycle slips and atan2 unwrap pitfalls in noisy or analog sensing.
Ten Little Algorithms, Part 1: Russian Peasant Multiplication
Jason Sachs revisits a centuries-old multiplication trick and shows why it still matters. He lays out Russian Peasant Multiplication with simple Python code, then reveals how the same shift-and-add pattern maps to GF(2) polynomial arithmetic and to exponentiation by squaring. The post mixes historical context with practical bitwise techniques that are useful for embedded and low-level math work.
PID Without a PhD
You do not need control theory to implement useful PID loops in embedded projects. Tim Wescott walks through simple, ready-to-use C code, clear explanations of P, I and D terms, and a practical tuning recipe you can apply to motors, precision actuators, and heaters. The article highlights anti-windup, sampling-rate guidance, and when to call in a control expert.
Round Round Get Around: Why Fixed-Point Right-Shifts Are Just Fine
Jason Sachs explains why, in most embedded systems, simple bitwise right-shifts are an acceptable way to do fixed-point division rather than paying the runtime cost to round. He shows the cheap trick of adding 2^(N-1) to implement round-to-nearest, explains unbiased "round-to-even" issues, and compares arithmetic error to much larger ADC and sensor errors. The takeaway: save cycles unless your algorithm or inputs require extra precision.
