Note G: The First Computer Program i

Note G Calculator

Description: Interactive calculator for Bernoulli numbers using both Ada Lovelace's original 1843 algorithm and modern recursive formula.

How-to: Select algorithm mode (Modern or Historical), enter a value n (0-110), and click Calculate to see exact fractional results.

Historical Bug: In Historical mode, enable the Operation 13 bug to see Ada's original error from her published diagram.

Performance: Lower values (0-20) are instant. Higher values (40+) may take longer due to exact fraction arithmetic.

Who Was Ada Lovelace?

Augusta Ada King, Countess of Lovelace (1815–1852), was an English mathematician and writer who worked with Charles Babbage on his Analytical Engine. The daughter of poet Lord Byron, Ada possessed an exceptional gift for mathematics and logical reasoning.

While translating an Italian article about Babbage's machine, she added extensive notes of her own — labeled A through G. Note G contained a complete algorithm for computing Bernoulli numbers, making it the first published algorithm intended to be processed by a machine.

Why Bernoulli Numbers?

Ada chose Bernoulli numbers to demonstrate the Analytical Engine's capabilities because:

• Complex Recursion: They require storing and referencing previous computed values
• Fractional Arithmetic: Operations must preserve exact ratios, not just decimals
• Memory Management: The algorithm showcased the Engine's "store" (memory) and "mill" (processor)
• Mathematical Significance: Used in number theory, calculus, and various mathematical applications

Understanding Bernoulli Numbers

Bernoulli numbers are a sequence of rational numbers with deep connections to number theory and analysis. They appear in formulas for sums of powers, Taylor series, and the Riemann zeta function.

The Recursive Formula

The standard Bernoulli recurrence relation is:

Where:

• Bₙ is the nth Bernoulli number
• C(n+1,k) is the binomial coefficient "(n+1) choose k"
• Σ represents summation over all k from 0 to n-1
• The divisor (n+1) applies to the entire sum

Base Cases

• B₀ = 1
• B₁ = -1/2 (Note: Ada used +1/2, but modern mathematics uses -1/2)
• All odd Bernoulli numbers (except B₁) equal zero

Known Values i

Bernoulli Number Reference

B₀ = 1: Starting value by definition.

B₁: Modern convention uses -1/2, Ada used +1/2. Both are valid depending on the definition used.

Even indices: Non-zero fractions that grow in complexity (B₂, B₄, B₆, B₈...).

Odd indices (shaded): All odd-indexed Bernoulli numbers except B₁ equal zero. This is a fundamental mathematical property!

Pattern: Notice alternating signs and how numerators grow much faster than denominators.

Ada's Note G: The Operation-Based Algorithm i

Historical Algorithm

Low-level approach: Sequential operations on named variables (V₁, V₂, etc.), simulating the Analytical Engine's Store and Mill.

Store: Memory columns holding variables.

Mill: Processor performing arithmetic.

Operations: Each step (Op.1, Op.2, etc.) manipulates specific variables, like assembly language for a mechanical computer.

B₁ = +1/2: Ada used the historical mathematical convention of her era.

Ada Lovelace's Note G is fundamentally different from modern programming—it's not written as a high-level formula, but as sequential operations for a machine that manipulates physical variables. Think of it as assembly language for a mechanical computer.

The Analytical Engine's Architecture

Babbage's Analytical Engine had two key components:

• The Store: Memory columns holding variables (V₁, V₂, V₃, etc.)
• The Mill: The processor performing arithmetic operations

Ada's Algorithm Structure

Step 1: Initialize Store Variables

Step 2: Compute Key Ratio

The first three operations compute (n-1)/(n+1):

Step 3: Initial Accumulation

Operations 4-6 begin combining with B₀ and B₁:

Step 4: Loop Over Bernoulli Terms

Operations 7-13 repeat in a loop, processing each previous Bernoulli number with appropriate scaling factors. This is where the control flow emerges—Ada specified:

• Loop condition: If V₃ > 0, return to Operation 4
• Loop update: V₃ = V₃ - V₂ (decrement by 2)
• Termination: When V₃ = 0, proceed to final step

Step 5: Final Computation

The Historical B₇ Bug

Why This Matters

• First Program: This is the first algorithm designed for a computer
• Variables & Memory: Ada defined how to store and retrieve values
• Control Flow: She specified loops and conditional halts
• Operations: Each step maps to a machine instruction
• Debugging Reality: Even the first program had a bug!

Modern Algorithm: How It Works i

Modern Algorithm

High-level approach: Uses standard recursive formula Bₙ = -1/(n+1) × Σ(k=0 to n-1) [C(n+1,k) × Bₖ]

B₁ = -1/2: Modern mathematical convention.

Advantages: Concise, mathematically elegant, easier to understand and verify.

Comparison: This is what modern programmers would write, versus Ada's machine-level operations.

The modern approach uses a high-level mathematical formula rather than low-level operations:

The Recursive Formula

Algorithm Steps

1. Initialize: B₀ = 1, B₁ = -1/2 (modern convention)
2. For each n ≥ 2:
   • Initialize sum = 0
   • For k from 0 to n-1:
   • Compute binomial coefficient C(n+1, k)
   • Multiply by Bₖ
   • Add to sum
   • Bₙ = -sum / (n+1)
3. Simplify: Reduce fraction using GCD

Key Differences from Ada's Algorithm

Aspect	Ada's Note G	Modern
Approach	Sequential operations (assembly-like)	Mathematical formula (high-level)
B₁ value	+1/2 (historical convention)	-1/2 (modern convention)
Variables	Named registers (V₁-V₇)	Array indexing (B[k])
Abstraction	Low-level machine operations	High-level algorithm

Exact Fraction Arithmetic

Both algorithms preserve precision using exact rational arithmetic:

• Addition: a/b + c/d = (ad + bc) / (bd)
• Multiplication: a/b × c/d = (ac) / (bd)
• Division: a/b ÷ c/d = (ad) / (bc)
• Simplification: Reduce by GCD(numerator, denominator)

Legacy & Impact

Ada Lovelace's Note G represents far more than a mathematical exercise. She envisioned possibilities for computing that wouldn't be realized for over a century:

• Programming Concepts: Variables, loops, conditionals, and subroutines
• Beyond Calculation: She theorized machines could manipulate symbols and create music
• Debugging: She anticipated and described how errors could occur and be corrected
• Algorithm Design: Systematic problem-solving through step-by-step instructions

Today, Ada Lovelace Day (second Tuesday of October) celebrates women in STEM fields. Her vision and intellect continue to inspire programmers, mathematicians, and engineers worldwide.

A Letter to Charles Babbage

On August 14, 1843, shortly after completing her translation and notes on the Analytical Engine, Ada wrote this passionate letter to Charles Babbage:

This letter captures Ada's extraordinary confidence in her own abilities and her deep commitment to realizing the potential of the Analytical Engine. Her prophecy that her brain was "something more than merely mortal" proved prescient — her contributions to computing would not be fully appreciated until more than a century after her death.