Project 3: Polynomial Root Finder

A tool that finds all roots (real and complex) of any polynomial, visualizing them on the complex plane.

Quick Reference

Attribute	Value
Difficulty	Level 2: Intermediate (The Developer)
Main Programming Language	Python
Alternative Programming Languages	C, Julia, Rust
Coolness Level	Level 3: Genuinely Clever
Business Potential	1. The “Resume Gold” (Educational/Personal Brand)
Knowledge Area	Numerical Methods / Algebra
Software or Tool	Root Finder
Main Book	“Algorithms” by Sedgewick & Wayne

---

1. Learning Objectives

By completing this project, you will:

1. Translate math definitions into deterministic implementation steps.
2. Build validation checks that make correctness observable.
3. Diagnose numerical, logical, and data-shape failures early.
4. Explain tradeoffs in interviews using evidence from your own build.

---

2. All Theory Needed (Per-Concept Breakdown)

This project applies the following theory clusters:

• Symbolic-to-numeric translation (expressions, data shapes, invariants)
• Stability constraints (precision, scaling, stopping criteria)
• Optimization or inference logic (depending on project objective)
• Evaluation discipline (error analysis, test coverage, reproducibility)

Concept A: Mathematical Representation Discipline

Fundamentals A math expression is not executable until you define representation, ordering, and domain constraints. The same equation can be represented as a token stream, tree, matrix pipeline, or probability graph. Choosing representation determines what bugs you can catch early.

Deep Dive into the concept Most project failures begin before algorithm selection: they start with ambiguous representation. If your parser cannot distinguish unary minus from subtraction, your calculator fails. If your matrix dimensions are implicit rather than validated, your linear algebra pipeline fails silently. If your probabilistic assumptions (independence, stationarity, or class priors) are not explicit, your inference can look accurate on one split and collapse on another. The core implementation move is to treat representation as a contract. Define each object with shape, domain, and semantic intent. Then enforce invariants at boundaries: input parser, preprocessing, training loop, evaluation stage. This makes debugging local instead of global.

How this fits this project You will encode each operation with explicit contracts and invariant checks.

Definitions & key terms

• Invariant: Property that must hold before and after each operation.
• Shape contract: Expected dimensional structure of vectors/matrices/tensors.
• Domain constraint: Allowed value range (for example log input > 0).

Mental model diagram

User Input -> Representation Layer -> Validated Operation -> Observable Output
              (tokens/shapes)        (invariants pass)       (tests/plots/logs)

How it works

1. Parse/ingest data into typed structures.
2. Validate shape/domain invariants.
3. Execute operation.
4. Compare observed output with expected behavior.
5. Record failure signature if mismatch appears.

Minimal concrete example

PSEUDOCODE
read expression
tokenize with precedence rules
if token sequence invalid -> return syntax error
evaluate tree
if domain violation -> return bounded diagnostic
print value and confidence check

Common misconceptions

• “If it runs once, representation is correct.” -> false.
• “Type checks are enough without shape checks.” -> false.

Check-your-understanding questions

1. Which invariant catches division-by-zero earliest?
2. Why does shape validation belong at boundaries rather than only in core logic?
3. Predict failure if tokenization ignores unary minus.

Check-your-understanding answers

1. Domain check on denominator before operation execution.
2. Boundary validation keeps errors local and diagnostic.
3. Expressions like -2^2 get misinterpreted and produce wrong precedence behavior.

Real-world applications Feature preprocessing, model-serving input validation, and experiment-tracking schema enforcement.

Where you’ll apply it This project and every downstream project in the sprint.

References

• CSAPP (Bryant & O’Hallaron), floating-point chapter
• Math for Programmers (Paul Orland), representation-oriented chapters

Key insight Correct representation reduces the complexity of every later decision.

Summary Stable ML math implementations start with explicit contracts, not implicit assumptions.

Homework/Exercises

1. Write five invariants for your project.
2. Build a failing test input for each invariant.

Solutions

1. Include at least one shape, one domain, one convergence, one reproducibility, and one output-range invariant.
2. Each failing input should trigger exactly one diagnostic to keep root-cause analysis clean.

---

3. Build Blueprint

1. Scope the smallest end-to-end slice that produces visible output.
2. Add deterministic tests and edge-case probes.
3. Layer complexity only after baseline behavior is stable.
4. Add metrics logging before optimization.
5. Run failure drills: perturb inputs, scale values, and check stability.

---

4. Real-World Outcome (Target)

$ python roots.py "x^3 - 1"
Roots of x³ - 1:
  x₁ = 1.000 + 0.000i  (real)
  x₂ = -0.500 + 0.866i (complex)
  x₃ = -0.500 - 0.866i (complex conjugate)

[Shows complex plane with three roots equally spaced on unit circle]

$ python roots.py "x^2 + 1"
Roots of x² + 1:
  x₁ = 0.000 + 1.000i
  x₂ = 0.000 - 1.000i
[No real roots - parabola never crosses x-axis]

Implementation Hints: Newton-Raphson: start with a guess x₀, then iterate x_{n+1} = x_n - f(x_n)/f'(x_n). For polynomials, the derivative is easy: derivative of axⁿ is n·axⁿ⁻¹. Use multiple random starting points to find all roots.

Complex arithmetic: (a+bi)(c+di) = (ac-bd) + (ad+bc)i. Implementing this yourself builds deep intuition for complex numbers.

Learning milestones:

1. Real roots found accurately → You understand zero-finding
2. Complex roots visualized on the plane → You understand complex numbers geometrically
3. Connection to polynomial factoring is clear → You understand algebraic structure

---

5. Core Design Notes from Main Guide

Core Question

“Why do we need numbers that don’t exist on the number line?”

When you solve x^2 + 1 = 0, you get x = sqrt(-1), which is impossible if you only know about real numbers. But mathematicians invented complex numbers (a + bi, where i = sqrt(-1)) and discovered something magical: every polynomial has roots if you allow complex numbers. This is the Fundamental Theorem of Algebra. Why should you care? Because complex numbers appear everywhere in machine learning: Fourier transforms (used in signal processing, CNNs), eigenvalue decomposition (PCA, stability analysis), and more. By building a root finder that handles complex numbers, you’re preparing yourself for the mathematics that underlies modern ML.

Concepts You Must Understand First

Stop and research these before coding:

1. Complex Numbers and the Complex Plane
   • What is i = sqrt(-1) and why did mathematicians “invent” it?
   • How do you add, subtract, multiply, and divide complex numbers?
   • What is the geometric interpretation of complex multiplication?
   • Book Reference: “Math for Programmers” Chapter 9 - Paul Orland
2. Polynomial Fundamentals
   • What is the degree of a polynomial and why does it matter?
   • What does the Fundamental Theorem of Algebra say?
   • How are roots related to factors? If r is a root, then (x - r) is a factor.
   • Book Reference: “Introduction to Algorithms” Chapter 30 - CLRS
3. Newton-Raphson Method for Root Finding
   • What is the iteration formula: x_{n+1} = x_n - f(x_n) / f’(x_n)?
   • Why does it work (think: tangent line intersection)?
   • When does Newton-Raphson fail or converge to the wrong root?
   • Book Reference: “Algorithms” Section 4.2 - Sedgewick & Wayne
4. Polynomial Derivatives
   • How do you compute the derivative of a polynomial?
   • Why is the derivative of ax^n equal to nax^(n-1)?
   • How do you implement this algorithmically?
   • Book Reference: “Calculus” Chapter 3 - James Stewart
5. Numerical Stability and Precision
   • Why do floating-point errors accumulate in iterative methods?
   • What is a “tolerance” and how do you know when to stop iterating?
   • How do you handle polynomials with very large or very small coefficients?
   • Book Reference: “Computer Systems: A Programmer’s Perspective” Chapter 2.4 - Bryant & O’Hallaron

Questions to Guide Your Design

Before implementing, think through these:

1. How will you represent polynomials? As a list of coefficients? As a dictionary?
2. How will you represent complex numbers? Use Python’s built-in complex type, or implement your own?
3. How will you evaluate a polynomial efficiently? (Hint: Horner’s method)
4. How will you compute the derivative of a polynomial?
5. How do you know when Newton-Raphson has converged?
6. How do you find ALL roots, not just one?

Thinking Exercise

Work through this by hand before coding:

Find all roots of p(x) = x^3 - 1.

Step 1: Factor if possible x^3 - 1 = (x - 1)(x^2 + x + 1) by the difference of cubes formula.

Step 2: Find real roots From (x - 1), we get x = 1.

Step 3: Find complex roots From x^2 + x + 1 = 0, use the quadratic formula: x = (-1 +/- sqrt(1 - 4)) / 2 = (-1 +/- sqrt(-3)) / 2 = -1/2 +/- i*sqrt(3)/2

So the three roots are: 1, -1/2 + isqrt(3)/2, -1/2 - isqrt(3)/2.

Step 4: Visualize On the complex plane, these three roots are equally spaced on the unit circle at angles 0, 120, and 240 degrees. This is the “3rd roots of unity” pattern!

Now verify: If your code finds three roots approximately at (1, 0), (-0.5, 0.866), (-0.5, -0.866), you know it’s working.

Interview Questions

1. “How does Newton-Raphson work for finding roots?”
   • Expected: Explain the geometric intuition (tangent line), the formula x_{n+1} = x_n - f(x_n)/f’(x_n), and convergence conditions.
2. “Why do you need complex numbers to find all roots of a polynomial?”
   • Expected: The Fundamental Theorem of Algebra guarantees n roots (counting multiplicity) for a degree-n polynomial, but some may be complex.
3. “How would you implement complex number multiplication from scratch?”
   • Expected: (a+bi)(c+di) = (ac-bd) + (ad+bc)i. Explain why the real part has a minus sign.
4. “What is Horner’s method and why is it better for polynomial evaluation?”
   • Expected: Instead of computing x^n separately, use p(x) = ((a_nx + a_{n-1})x + a_{n-2})*x + … This is O(n) instead of O(n^2).
5. “How do you find multiple roots, not just one?”
   • Expected: Use deflation (divide out found roots) or start with many random complex initial guesses. Muller’s method or Durand-Kerner find all roots simultaneously.
6. “What happens when Newton-Raphson starts at a bad initial guess?”
   • Expected: It may diverge, oscillate, or converge to a different root. Starting points near local extrema are particularly problematic.

Hints in Layers (Treat as pseudocode guidance)

Hint 1: Start with polynomial representation and evaluation Represent p(x) = 3x^2 + 2x - 5 as coefficients [3, 2, -5] (highest degree first) or [-5, 2, 3] (lowest degree first). Implement evaluation using Horner’s method.

Hint 2: Implement polynomial derivative If p(x) has coefficients [a_n, a_{n-1}, …, a_1, a_0], then p’(x) has coefficients [na_n, (n-1)a_{n-1}, …, 1*a_1].

Hint 3: Start Newton-Raphson with real numbers Get it working on polynomials with real roots first (like x^2 - 4). Then extend to complex starting points.

Hint 4: Use multiple starting points To find all roots, run Newton-Raphson from many random starting points (both real and complex). Cluster the results to identify distinct roots.

Hint 5: Implement deflation to find subsequent roots After finding root r, divide the polynomial by (x - r) using synthetic division. Then find roots of the quotient. This ensures you find all roots without re-discovering the same one.

Books That Will Help

Topic	Book	Chapter
Complex number arithmetic	“Math for Programmers”	Chapter 9 - Paul Orland
Newton-Raphson method	“Algorithms”	Section 4.2 - Sedgewick & Wayne
Polynomial arithmetic	“Introduction to Algorithms”	Chapter 30 - CLRS
Numerical precision	“Computer Systems: A Programmer’s Perspective”	Chapter 2.4 - Bryant & O’Hallaron
Horner’s method	“Numerical Recipes”	Chapter 5 - Press et al.
Fundamental Theorem of Algebra	“Complex Analysis”	Chapter 1 - Ahlfors
Polynomial root visualization	“Visual Complex Analysis”	Chapter 1 - Tristan Needham

---

Part 2: Linear Algebra

Linear algebra is the backbone of machine learning. Every neural network, every dimensionality reduction, every image transformation uses matrices.

---

---

6. Validation, Pitfalls, and Completion

Common Pitfalls and Debugging

Problem 1: “Outputs drift after a few iterations”

• Why: Hidden numerical instability (unscaled features, aggressive step size, or repeated subtraction of nearly equal values).
• Fix: Normalize inputs, reduce step size, and track relative error rather than only absolute error.
• Quick test: Run the same task with two scales of input (for example x and 10x) and compare normalized error curves.

Problem 2: “Results are inconsistent across runs”

• Why: Random seeds, data split randomness, or non-deterministic ordering are uncontrolled.
• Fix: Set seeds, log configuration, and store split indices and hyperparameters with each run.
• Quick test: Re-run three times with the same seed and confirm metrics remain inside a tight tolerance band.

Problem 3: “The project works on the demo case but fails on edge cases”

• Why: Tests only cover happy-path inputs.
• Fix: Add adversarial inputs (empty values, extreme ranges, near-singular matrices, rare classes).
• Quick test: Build an edge-case test matrix and ensure every scenario reports expected behavior.

Definition of Done

• Core functionality works on reference inputs
• Edge cases are tested and documented
• Results are reproducible (seeded and versioned configuration)
• Performance or convergence behavior is measured and explained
• A short retrospective explains what failed first and how you fixed it

---

7. Extension Ideas

1. Add a stress-test mode with adversarial inputs.
2. Add a short benchmark report (runtime + memory + error trend).
3. Add a reproducibility bundle (seed, config, and fixed test corpus).

8. Why This Project Matters

Polynomials are everywhere in ML (Taylor expansions, characteristic equations of matrices). Understanding roots means understanding where functions hit zero—the foundation of optimization. Complex numbers appear in Fourier transforms and eigenvalue decomposition.

This project is valuable because it creates observable evidence of mathematical reasoning under real implementation constraints.