Day 4 — Exponents, Logarithms & Gate I
Day 4 — Exponents, Logarithms & Gate I
Day 8 — Exponents & logarithms
Stage I · concept day
Goal: Prove and apply exponent laws for integer exponents; work with roots; define logarithms; use change of base; connect \(\log_2\) to bits and information; solve simple exponential equations.
Why this matters
Complexity is full of \(n^2\), \(2^n\), and \(\log n\). Bit length of an integer \(n\) is about \(\lfloor\log_2 n\rfloor+1\). Cryptography and hashing talk about “bits of security.” Exponent and log laws are algebraic muscle for Stage II growth and Stage VIII asymptotics.
Theory
Integer exponents
For \(a\neq 0\) and \(n\in\mathbb{Z}_{\ge 0}\): \[a^0=1,\qquad a^{n+1}=a^n\cdot a.\] For \(n>0\), \(a^{-n}=\frac{1}{a^n}\) (when working in \(\mathbb{Q}\) or \(\mathbb{R}\)).
\(0^n=0\) for \(n>0\); \(0^0\) left undefined.
Exponent laws (with proofs for integer exponents)
Assume \(a,b\neq 0\) and \(m,n\in\mathbb{Z}\) (with denominators defined).
Law 1. \(a^m a^n=a^{m+n}\).
Proof idea (nonnegative \(m,n\)). Fix \(m\); induct on \(n\). Base \(n=0\): \(a^m\cdot 1=a^m=a^{m+0}\). Inductive: \(a^m a^{n+1}=a^m a^n a=a^{m+n}a=a^{m+n+1}\). Extend to negatives using \(a^{-k}=1/a^k\). \(\square\)
Law 2. \((a^m)^n=a^{mn}\).
Proof idea. \((a^m)^n=a^m\cdot a^m\cdots a^m\) (\(n\) times) \(=a^{m+\cdots+m}=a^{mn}\) for \(n>0\); similar care for signs. \(\square\)
Law 3. \((ab)^n=a^n b^n\).
Proof idea. Induct on \(n\ge 0\): \((ab)^{n+1}=(ab)^n(ab)=a^n b^n a b=a^{n+1}b^{n+1}\). \(\square\)
Law 4. \(\frac{a^m}{a^n}=a^{m-n}\).
From Law 1: \(a^m=a^{m-n}a^n\).
Non-laws (pitfalls): \((a+b)^n\neq a^n+b^n\) in general; \(a^{b^c}\neq (a^b)^c\) in general.
Roots
For \(a\ge 0\) and integer \(k\ge 2\), \(\sqrt[k]{a}=a^{1/k}\) is the nonnegative \(x\) with \(x^k=a\) (principal root).
\(\sqrt{a^2}=|a|\) for real \(a\).
For odd \(k\), real \(k\)-th roots of negatives exist: \(\sqrt[3]{-8}=-2\).
Laws (principal roots, careful domains): \[\sqrt[k]{ab}=\sqrt[k]{a}\sqrt[k]{b}\quad(a,b\ge 0),\qquad \bigl(\sqrt[k]{a}\bigr)^m=\sqrt[k]{a^m}.\]
Logarithms
For base \(b>0\), \(b\neq 1\), and \(x>0\): \[\log_b x = y \quad\Longleftrightarrow\quad b^y=x.\]
Special bases: \(\log_{10}\) (common), \(\ln=\log_e\) (natural), \(\log_2\) (binary, CS).
Domain: argument \(x>0\); base \(b>0\), \(b\neq 1\).
Log laws
For valid \(x,y>0\) and allowed bases:
- \(\log_b(xy)=\log_b x+\log_b y\)
- \(\log_b(x/y)=\log_b x-\log_b y\)
- \(\log_b(x^r)=r\log_b x\)
- \(\log_b b=1\), \(\log_b 1=0\)
- \(b^{\log_b x}=x\), \(\log_b(b^y)=y\)
Proof of (1). Let \(\log_b x=m\), \(\log_b y=n\), so \(b^m=x\), \(b^n=y\). Then \(xy=b^m b^n=b^{m+n}\), hence \(\log_b(xy)=m+n\). \(\square\)
Proof of (3). \(x^r=(b^{\log_b x})^r=b^{r\log_b x}\). \(\square\)
Change of base
\[\log_b x=\frac{\log_k x}{\log_k b}\] for any valid base \(k\).
Proof. Let \(y=\log_b x\), so \(b^y=x\). Take \(\log_k\): \(y\log_k b=\log_k x\). \(\square\)
Useful: \(\log_b a=1/\log_a b\).
\(\log_2\) and bits / information
- Number of bits needed to represent integers \(0..N-1\) is \(\lceil\log_2 N\rceil\) for \(N\ge 1\) (with \(N=1\) meaning \(1\) value needs \(0\) or \(1\) bits depending on convention—usually \(\lceil\log_2 N\rceil\) for \(N\ge 2\)).
- Bit length of positive integer \(n\): \(\lfloor\log_2 n\rfloor+1\).
- Each fair binary question halves the search space → information scale is \(\log_2\) of number of alternatives.
Solving simple exponential equations
If \(b^u=b^v\) and \(b>0\), \(b\neq 1\), then \(u=v\).
If \(b^x=c\) with \(c>0\), then \(x=\log_b c\).
Rewrite same bases: \(4^x=(2^2)^x=2^{2x}\).
Example: \(2^{x}=32\Rightarrow x=5\).
\(9^x=27\): \((3^2)^x=3^{2x}\), \(27=3^3\), so \(2x=3\), \(x=\frac{3}{2}\).
Worked examples
Example 1 — Product law
\(2^5\cdot 2^3=2^8=256\). Not \(2^{15}\).
Example 2 — Power of power
\((2^5)^3=2^{15}=32768\).
\(2^{(5^3)}=2^{125}\) enormous—parentheses matter.
Example 3 — Negative exponents
\(3^{-2}=\frac{1}{9}\). \(2^{-3}\cdot 2^{5}=2^{2}=4\).
Example 4 — Root
\(\sqrt{50}=\sqrt{25\cdot 2}=5\sqrt{2}\). \(\sqrt[3]{-27}=-3\).
Example 5 — Log definition
\(\log_2 32=5\) because \(2^5=32\).
\(\log_5 1=0\). \(\log_7 7=1\).
Example 6 — Log product
\(\log_2(8\cdot 4)=\log_2 8+\log_2 4=3+2=5=\log_2 32\).
Example 7 — Change of base
\(\log_8 2=\frac{\log_2 2}{\log_2 8}=\frac{1}{3}\). Check: \(8^{1/3}=2\).
Example 8 — Bits for IDs
Values \(0..999\): need \(\lceil\log_2 1000\rceil=\lceil 9.96\rceil=10\) bits.
Example 9 — Bit length
\(n=1000\): \(\lfloor\log_2 1000\rfloor+1=\lfloor 9.96\rfloor+1=10\) bits for binary representation of \(1000\).
Example 10 — Solve
\(3^{2x}=81=3^4\Rightarrow 2x=4\Rightarrow x=2\).
\(2^{x+1}=2^{3x-5}\Rightarrow x+1=3x-5\Rightarrow 6=2x\Rightarrow x=3\).
Example 11 — Different bases
\(4^{x}=8^{x-1}\): $ (22)x=(23){x-1}2x=3x-3x=3$.
Example 12 — Log equation
\(\log_2(x-1)=3\Rightarrow x-1=8\Rightarrow x=9\) (check domain \(x>1\)).
Example 13 — Information
Dictionary of \(2^{20}\) words: about \(20\) fair yes/no questions in binary search idealization.
Example 14 — Identity
\(\log_b(b^k)=k\); \(b^{\log_b 5}=5\).
Exercises
Easy
- Simplify \(5^2\cdot 5^4\) and \((5^2)^4\).
- Evaluate \(2^{-4}\), \(10^{0}\), \(7^{1}\).
- Find \(\log_2 64\), \(\log_3 81\), \(\log_{10} 1000\).
- Simplify \(\log_5(25\cdot 125)\).
- Solve \(2^x=128\).
Medium
- Prove \(a^m a^n=a^{m+n}\) for nonnegative integers by induction on \(n\).
- Simplify \(\frac{a^{6}b^{-2}}{a^{2}b^{3}}\) for \(a,b\neq 0\).
- Express \(\log_9 27\) as a rational number.
- Use change of base to write \(\log_6 10\) in terms of \(\ln\) or \(\log_{10}\).
- How many bits to distinguish \(5000\) user IDs (\(0..4999\))?
- Solve \(9^{x}=27^{x-1}\).
- Solve \(\log_3(2x+1)=2\).
- Simplify \(\sqrt{18}+\sqrt{8}\) if possible.
Hard / proof
- Prove \(\log_b(xy)=\log_b x+\log_b y\) from the definition.
- Prove the change-of-base formula.
- Prove \((ab)^n=a^n b^n\) for \(n\in\mathbb{Z}_{\ge 0}\) by induction.
- Show \(\log_b a\cdot\log_a c=\log_b c\) (chain rule for logs).
- If \(2^{x}=5\), express \(4^{x}\) and \(2^{x+3}\) without solving for \(x\) first.
- Domain: for which real \(x\) is \(\log_2(x^2-1)\) defined?
- Disprove \((a+b)^2=a^2+b^2\) with a counterexample; expand correctly.
Challenge / CS-flavored
- Password space: \(62\) character alphabet, length \(8\): express size as \(62^8\); estimate \(\log_2(62^8)=8\log_2 62\).
- Why is binary search \(O(\log n)\) related to \(\log_2 n\) halvings?
- Floating point idea: numbers near \(2^{e}\) — connect exponent field to powers of two (preview Day 9).
- Solve \(2^{2x}-2^{x}-2=0\) with \(y=2^{x}\).
- Compare growth: for large \(n\), is \(n^{100}\) or \(2^{n}\) larger? (qualitative; Stage VIII formalizes)
Exponential and log graphs (qualitative)
For \(b>1\): \(y=b^{x}\) passes through \((0,1)\), increases, asymptotic to positive \(x\)-axis as \(x\to-\infty\).
\(y=\log_b x\) passes through \((1,0)\), increases slowly, domain \(x>0\), inverse graph reflected across \(y=x\).
Change-of-base computations
\(\log_2 10=\frac{\ln 10}{\ln 2}\approx\frac{2.302}{0.693}\approx 3.32\).
Thus \(10^{d}\approx 2^{3.32 d}\)—bits vs decimal digits: about \(3.32\) bits per decimal digit.
Solving strategies checklist
- Same base → equate exponents.
- Write both sides as powers of a common base.
- Take \(\log\) of both sides (arguments positive).
- Substitution \(u=b^{x}\) for equations in \(b^{x}\) and \(b^{2x}\).
- Check domain after solving log equations.
Growth comparisons (pre-asymptotics)
For large \(n\): \(2^{n}\) grows faster than \(n^{100}\); \(\log n\) grows slower than any positive power \(n^{\varepsilon}\). Tables for small \(n\) can mislead—always check large \(n\).
Extra exercises
- Prove \(\log_b(x/y)=\log_b x-\log_b y\).
- Solve \(5^{2x}-5^{x}-6=0\).
- Express \(\log_6 72\) as \(a+b\log_6 2\) or similar with integers \(a,b\).
- How many bits to store an integer up to \(10^{18}\) (unsigned)?
- Show \(\log_2(6^{n})=n\log_2 6\) and estimate using \(\log_2 6=1+\log_2 3\).
CS connection
\(\log_2 n\) counts halvings and tree height for balanced binary trees. Bit complexity of \(n\) is \(\Theta(\log n)\). Exponentiation \(a^n\) by squaring uses \(O(\log n)\) multiplications. Exponential equations model doubling processes (Day 20). Never confuse \(2^{n^2}\) with \((2^n)^2=2^{2n}\).
Common pitfalls
| Pitfall | What to do instead |
|---|---|
| \(a^m a^n=a^{mn}\) | Sum exponents for product of powers |
| \((a^m)^n=a^{m+n}\) | Multiply exponents |
| \(\log(x+y)=\log x+\log y\) | Product inside log, not sum |
| Logs of nonpositives | Domain \(x>0\) |
| Base \(1\) or negative | Base \(b>0\), \(b\neq 1\) |
| Forgetting \(\sqrt{x^2}=|x|\) | Absolute value |
| Bits for \(0..2^k-1\) off-by-one | Exactly \(k\) bits for \(2^k\) values |
Fully worked extra examples
E15 — Log equation domain.
\(\log_2(x-1)+\log_2(x+1)=3\Rightarrow\log_2((x-1)(x+1))=3\Rightarrow x^{2}-1=8\Rightarrow x^{2}=9\Rightarrow x=\pm 3\). Domain \(x>1\), so \(x=3\) only.
E16 — Bits vs values.
\(k\) bits distinguish \(2^{k}\) patterns. For \(N\) values, need \(\lceil\log_2 N\rceil\) bits. Off-by-one: \(0..2^{k}-1\) uses \(k\) bits exactly.
E17 — Change of base chain.
\(\log_2 3\cdot\log_3 5\cdot\log_5 2=1\) by telescoping change-of-base (each \(\frac{\ln a}{\ln b}\) multiplies to \(1\)).
E18 — Exponential inequality preview.
For \(b>1\), \(b^{x}>b^{y}\Leftrightarrow x>y\). Used when comparing growth without solving equality.
End-of-day synthesis problems
S1. Prove \(a^{m}a^{n}=a^{m+n}\) for \(m,n\ge 0\) by induction on \(n\).
S2. Simplify \(\dfrac{(2^{3})^{4}\cdot 2^{-5}}{4^{2}}\) fully to a power of \(2\).
S3. Evaluate \(\log_2 80\) using \(\log_2 5\) left symbolic: \(4+\log_2 5\).
S4. Change of base: compute \(\log_9 27\) exactly.
S5. Bits for \(0..10^{6}-1\); bit length of \(10^{6}\).
S6. Solve \(5^{x+1}=25^{x-1}\).
S7. Solve \(\log_2(x-1)+\log_2(x+1)=3\) with domain check.
S8. Password space \(26^{8}\): express \(\log_2(26^{8})\) as \(8\log_2 26\).
Checkpoint
- State and prove (sketch) main exponent laws
- Define \(\log_b x\) and invert with \(b^y\)
- Apply product/power/change-of-base laws
- Compute bit counts via \(\lceil\log_2 N\rceil\)
- Solve \(b^x=c\) and same-base exponential equations
- Write S1 proof cleanly
Write two takeaways in your own words.
Deep dive — exponent laws, logs, bits
D1 — Induction writeup for \(a^m a^n=a^{m+n}\) (\(n\ge 0\)).
Fix \(m\ge 0\), induct on \(n\). Base \(n=0\): \(a^m\cdot a^0=a^m\cdot 1=a^m=a^{m+0}\).
Assume for \(n\): \(a^m a^n=a^{m+n}\). Then \(a^m a^{n+1}=a^m a^n a=a^{m+n}a=a^{m+n+1}\).
Negatives: reduce using \(a^{-k}=1/a^k\) and Law 4 once nonnegative cases are solid.
D2 — Change of base chain telescopes.
\(\log_2 3\cdot\log_3 5\cdot\log_5 2=\frac{\ln 3}{\ln 2}\cdot\frac{\ln 5}{\ln 3}\cdot\frac{\ln 2}{\ln 5}=1\).
Useful check when converting bases repeatedly.
D3 — Solve with substitution.
\(2^{2x}-2^{x}-2=0\). Let \(u=2^{x}>0\). Then \(u^2-u-2=0\), \((u-2)(u+1)=0\), \(u=2\) (discard \(-1\)). So \(2^{x}=2\), \(x=1\).
D4 — Bits and off-by-one.
Values \(0..2^{k}-1\): exactly \(k\) bits.
Values \(0..N-1\): \(\lceil\log_2 N\rceil\) bits for \(N\ge 2\).
Bit length of integer \(n>0\): \(\lfloor\log_2 n\rfloor+1\) (e.g. \(n=1000\) needs \(10\) bits).
D5 — Same-base exponential equation.
\(9^{x}=27^{x-1}\): \((3^2)^{x}=(3^3)^{x-1}\), \(2x=3x-3\), \(x=3\).
Check: \(9^3=729\), \(27^{2}=729\).
D6 — Log domain checklist.
\(\log_2(x^2-1)\) needs \(x^2-1>0\), i.e. \(x<-1\) or \(x>1\).
After solving \(\log_2(x-1)+\log_2(x+1)=3\), only candidates with both factors positive (or careful product domain) survive—here \(x>1\), so \(x=3\) only from \(\pm 3\).
Extra practice set
- Prove \(\log_b(x/y)=\log_b x-\log_b y\) from definitions.
- Simplify \(\dfrac{(2^{3})^{4}\cdot 2^{-5}}{4^{2}}\) to a power of \(2\).
- How many bits to store unsigned integers up to \(10^{9}\)?
- Solve \(5^{2x}-5^{x}-6=0\) with \(u=5^{x}\).
- Express \(\log_2(6^{n})\) as \(n(1+\log_2 3)\).
Tomorrow
Day 9 — Error, rounding & floating-point idea. Absolute/relative error, rounding vs truncation, catastrophic cancellation, machine epsilon idea, error propagation lite.
Day 9 — Error, rounding & floating-point idea
Stage I · concept day
Goal: Define absolute and relative error; distinguish rounding vs truncation; exhibit catastrophic cancellation; model floating-point as binary scientific notation with machine epsilon idea (not a full IEEE deep dive); reason about simple error propagation.
Why this matters
Every sensor, every float, every rounded display lies a little. Algorithms that are correct in exact \(\mathbb{R}\) can fail in floating-point (or succeed with care). Relative error is how you say “accurate to \(0.1\%\).” Cancellation bugs look like “random” wrong digits.
Theory
True value, approximation, error
Let \(x\) be a true value and \(\hat{x}\) an approximation.
Absolute error: \[E_{\mathrm{abs}}=|\hat{x}-x|.\]
Relative error (for \(x\neq 0\)): \[E_{\mathrm{rel}}=\frac{|\hat{x}-x|}{|x|}.\]
Percent error: \(100\cdot E_{\mathrm{rel}}\%\).
Relative error is scale-free: being off by \(0.1\) matters differently near \(1\) vs near \(1000\).
Rounding vs truncation
Representations use finitely many digits.
Truncation (chopping): drop extra digits.
\(\pi\approx 3.14159\ldots\) truncated to \(4\) decimals: \(3.1415\).
Rounding (half-up common school rule): look at the next digit; if \(\ge 5\), round away from zero in the last kept place (variants exist: banker’s rounding / round-to-even in IEEE).
\(\pi\) rounded to \(4\) decimals: \(3.1416\).
Rounding error bound (decimal, \(k\) places after point): absolute error \(\le \frac{1}{2}\cdot 10^{-k}\) under standard round-to-nearest.
Sources of error
- Measurement noise
- Representation (finite digits / bits)
- Truncation of series / algorithms (math model cut off)
- Propagation through arithmetic
Catastrophic cancellation
Subtracting two nearly equal quantities loses leading significant digits.
Example. In \(6\)-digit decimal arithmetic, let \[x=1.00000,\quad y=1.00001\quad\text{(true)},\] but suppose we only store \(x'=1.00000\), \(y'=1.00000\) after rounding coarse measurements—difference \(0\) vs true \(10^{-5}\).
Classic: compute \(1-\cos\theta\) for tiny \(\theta\) in floating-point loses digits; mathematically equivalent \(2\sin^2(\theta/2)\) is stabler (identity reminder, not a coding lab).
Algebraic example. \((1+x)^2-1=2x+x^2\). For tiny \(x\), left side cancels; right side is better.
Floating-point model (binary scientific)
A simplified floating-point number looks like
\[\pm\, (1.b_1 b_2\ldots b_{p-1})_2 \times 2^{e},\]
with a fixed precision \(p\) (significand bits including the leading \(1\) for normals) and exponent \(e\) in a finite range \(e_{\min}..e_{\max}\).
(This is the idea of binary floating point; IEEE 754 adds subnormals, NaN, \(\pm\infty\), rounding modes—acknowledge, do not memorise the whole standard today.)
Machine epsilon (idea): \(\varepsilon_{\mathrm{mach}}\) is roughly the gap between \(1\) and the next representable number above \(1\). Relative spacing near \(1\) is order \(\varepsilon_{\mathrm{mach}}\).
For a \(p\)-bit significand (binary), \(\varepsilon_{\mathrm{mach}}\sim 2^{1-p}\) (order of magnitude).
Consequence: relative representation error for “typical” numbers is on the order of machine epsilon (when not underflowing/overflowing).
Decimal analogue: with \(d\) significant digits, relative spacing \(\sim 10^{1-d}\).
Propagation of error (lite)
Suppose \(x\) and \(y\) have absolute errors \(\delta_x,\delta_y\) (bounds).
Sum: \(|(x+\delta_x)+(y+\delta_y)-(x+y)|\le |\delta_x|+|\delta_y|\) — absolute errors add (triangle inequality).
Product (sketch): \((x+\delta_x)(y+\delta_y)=xy+x\delta_y+y\delta_x+\delta_x\delta_y\).
Relative error approximately \(\frac{|\delta_x|}{|x|}+\frac{|\delta_y|}{|y|}\) when second-order term neglected and \(x,y\neq 0\).
Division: similar approximate addition of relative errors.
Multiplication by constant \(c\): absolute error scales by \(|c|\); relative error unchanged.
Conditioning (intuition only)
A problem is ill-conditioned if small input changes cause large output changes (e.g. subtracting nearly equal numbers). Even exact arithmetic on slightly wrong inputs fails; floating-point makes it worse.
Worked examples
Example 1 — Absolute and relative
True \(x=200\), approximation \(\hat{x}=201\).
\(E_{\mathrm{abs}}=1\), \(E_{\mathrm{rel}}=1/200=0.005=0.5\%\).
True \(x=2\), \(\hat{x}=3\): same absolute error \(1\), relative \(50\%\).
Example 2 — Rounding vs truncation
\(x=\frac{2}{3}=0.6666\ldots\)
Truncate to \(3\) d.p.: \(0.666\). Absolute error \(\approx 0.000666\ldots\)
Round to \(3\) d.p.: \(0.667\). Absolute error \(\approx 0.000333\ldots\)
Example 3 — Percent error
Measure \(9.8\) for true \(9.81\): \(E_{\mathrm{rel}}=0.01/9.81\approx 0.102\%\).
Example 4 — Cancellation
Exact: \((1+10^{-8})-1=10^{-8}\).
In a decimal system with \(7\) significant digits, \(1+10^{-8}\) may store as \(1.000000\), difference \(0\).
Example 5 — Algebraic rewrite
Evaluate \(f(x)=\sqrt{x+1}-\sqrt{x}\) for large \(x\). Rationalize: \[f(x)=\frac{1}{\sqrt{x+1}+\sqrt{x}}.\] Right form avoids subtracting close square roots.
Example 6 — Sum error bound
If each of \(100\) terms has absolute error \(\le 10^{-6}\), sum absolute error \(\le 100\cdot 10^{-6}=10^{-4}\) (worst case; random errors may partially cancel—not guaranteed).
Example 7 — Relative product
\(x=2.0\) with \(1\%\) relative error, \(y=5.0\) with \(2\%\) relative error: product relative error \(\approx 3\%\) rough bound.
Example 8 — Machine epsilon idea
If \(\varepsilon=2^{-52}\approx 2.22\times 10^{-16}\) (IEEE double-ish order), then \(1+\varepsilon/2\) may equal \(1\) in floating-point, while \(1+\varepsilon>1\).
Example 9 — Decimal fp model
\(3\)-digit decimal floating point: numbers like \(d.dd\times 10^{e}\).
\(1.00\times 10^{0}\) next number \(1.01\times 10^{0}\); relative gap \(0.01\).
Example 10 — Underflow / overflow idea
Too small \(\to 0\) (underflow); too large \(\to\infty\) flag (overflow). Not the same as rounding error in the normal range.
Example 11 — Rounding money
\(\$1/3\) three ways: \(0.33+0.33+0.34\) strategies matter; floating binary money is a design smell—prefer integer cents.
Example 12 — Forward error
Computed \(\hat{y}\) vs true \(y=f(x)\): \(|\hat{y}-y|\) is forward absolute error.
Example 13 — Ill-conditioned subtraction
\(f(x,y)=x-y\) with \(x\approx y\): relative error in output can be huge even if \(x,y\) accurate relatively.
Example 14 — Bound for round-to-nearest
Rounded to integer: absolute error \(\le 1/2\). Rounded to \(1\) decimal: \(\le 0.05\).
Exercises
Easy
- \(x=50\), \(\hat{x}=49\): absolute and relative error.
- Round \(2.71828\) to \(3\) significant figures; to \(2\) decimal places.
- Truncate \(2.71828\) to \(2\) decimal places.
- Which is more accurate relatively: \(1000\pm 1\) or \(10\pm 0.05\)?
- Define machine epsilon in one sentence.
Medium
- True value \(1/3\). Approximations \(0.33\) and \(0.333\): compare absolute and relative errors.
- Explain catastrophic cancellation with a numeric decimal example of your own (state precision).
- Rationalize \(\sqrt{x+1}-\sqrt{x}\) as in Example 5; evaluate both forms at \(x=10^{4}\) by hand with \(6\) sig figs if possible.
- If absolute errors add for a sum of \(n\) terms each \(\le\varepsilon\), state the bound.
- Approximate relative error of a product given relative errors \(r_1,r_2\).
- In \(4\)-digit decimal floating point, represent \(12.345\) and \(0.0012345\) (normalized).
- Why is relative error undefined or unhelpful at true value \(0\)? What do people use instead?
- Compute percent error: claimed \(256\) MB, true \(256\times 10^{6}\) bytes vs \(256\times 2^{20}\) bytes — different definitions (rough percent).
Hard
- Prove \(|\hat{x}-x|\le\varepsilon\Rightarrow\) relative error \(\le\varepsilon/|x|\) for \(x\neq 0\).
- Show that if \(\hat{x}=x(1+\delta)\) with \(|\delta|\) small, then relative error is \(|\delta|\).
- Explain why \((1+x)^2-1\) is unstable for tiny \(x\) but \(2x+x^2\) is better.
- Bound absolute error when rounding a real to \(k\) decimal places (round-to-nearest).
- Give an example where absolute error is small but relative error is large, and vice versa.
- Propagation: if \(\hat{\theta}=\theta+\delta\), estimate absolute error in \(\sin\hat{\theta}\) using \(|\sin'|\le 1\) (mean value idea: change \(\le|\delta|\)).
- Discuss: is \(0.1+0.2=0.3\) exact in binary floating point? Why related to Day 3 terminating decimals?
Challenge / CS-flavored
- Why store currency as integer minor units instead of binary float?
- Summing \(1.0\) a million times vs summing many tiny values first—order can matter (qualitative associativity failure).
- “Double has about \(15\)–\(16\) decimal digits” — connect to \(\log_{10}(2^{53})\).
- Conditioning: solving \(x+y=2\), \(x+1.0001 y=2\) vs a well-separated system—what happens to solution if RHS perturbs slightly? (qualitative \(2\times 2\) feel; Day 14)
- Report an approximation of \(\sqrt{2}\) with absolute error \(<10^{-3}\); prove your bound by squaring.
Forward vs backward error (names)
- Forward error: distance between computed output and true output for the same input.
- Backward error: how little must you perturb the input for the computed output to be exact for the perturbed problem. Stable algorithms often have small backward error even if the problem is sensitive (ill-conditioned).
Rounding modes (IEEE awareness)
Round to nearest (ties to even), toward \(0\), toward \(+\infty\), toward \(-\infty\). School “half up” is one of several policies. Exact ties are rare in binary but defined.
Decimal floating mental model
\(t\) significant digits: represent numbers \(\pm m\times 10^{e}\) with integer \(m\) having at most \(t\) digits. Relative spacing \(\approx 10^{1-t}\). Mirrors binary with \(2\) instead of \(10\).
Propagation table (summary)
| Operation | Absolute error (bound idea) | Relative error (approx) |
|---|---|---|
| \(x\pm y\) | add abs errors | can explode if cancellation |
| \(xy\) | — | add rel errors |
| \(x/y\) | — | add rel errors |
| \(c x\) | \(|c|\) scales abs | rel unchanged |
Extra exercises
- True \(e\approx 2.71828\), use \(2.72\): abs and rel error.
- Show that if two numbers agree in the first \(k\) significant decimal digits, relative error is on the order \(10^{-k}\) (heuristic).
- Explain why summing many positive floats from smallest to largest can reduce error vs largest-first (qualitative).
- Condition of \(f(x)=\sqrt{x}\) near \(0\) vs near \(1\) (derivative intuition: \(f'=\frac{1}{2\sqrt{x}}\) blows up near \(0\)).
- Rewrite \(1-\sqrt{1-x}\) for small \(x\) by rationalizing to avoid cancellation.
CS connection
IEEE 754 float/double, GPU half-precision, and fixed-point DSP all trade range, precision, and speed. Numerical libraries rewrite formulas to avoid cancellation. Testing uses absolute tolerances and relative tolerances (atol, rtol). Hashing and crypto want exact integers, not floats. Logging “error bars” is relative-error thinking.
Common pitfalls
| Pitfall | What to do instead |
|---|---|
| Only quoting absolute error | Also report relative when scale varies |
| Trusting all decimal digits of a float print | Know precision limits |
| Subtracting nearly equal floats | Rewrite algebraically when possible |
| Assuming \(+\) is associative in fp | Order can change results |
| Using binary float for money | Integer cents / decimal types |
| Confusing truncation of series with chopping digits | Name the source of error |
| Machine epsilon as “smallest positive float” | It’s relative spacing near \(1\), not underflow threshold |
End-of-day synthesis problems
S1. True value \(\sqrt{2}\approx 1.41421356\). Approx \(1.414\): abs, rel, percent error.
S2. In \(6\) significant digit decimal arithmetic, explain failure of \((1+10^{-7})-1\).
S3. Rationalize \(\sqrt{x+1}-\sqrt{x}\); compare stability narrative for large \(x\).
S4. Bound absolute error of sum of \(50\) terms each rounded to \(10^{-4}\) abs error.
S5. Define machine epsilon; distinguish from underflow threshold.
S6. Product relative error estimate: \(2\%\) and \(3\%\) inputs → about \(5\%\) product.
S7. Why \(0.1\) is problematic in binary floating point (link Day 3).
S8. Round \(9.995\) to \(3\) significant figures; to \(2\) decimal places.
Checkpoint
- Compute absolute, relative, and percent error
- Round vs truncate a decimal expansion
- Give a catastrophic cancellation example
- Describe floating-point as \(\pm m\times 2^{e}\) with finite \(m\)
- State machine epsilon as an idea
- Bound sum absolute errors; approximate product relative errors
- Explain S2 and S5 in one sentence each
Write two takeaways in your own words.
Deep dive — error, cancellation, floating-point idea
D1 — Absolute vs relative side by side.
True \(x=200\), \(\hat x=201\): \(E_{\mathrm{abs}}=1\), \(E_{\mathrm{rel}}=0.005\).
True \(x=2\), \(\hat x=3\): same absolute error \(1\), relative \(0.5\).
Always ask “error relative to what scale?” before comparing approximations of different magnitudes.
D2 — Catastrophic cancellation in decimal \(t\)-digit arithmetic.
With \(6\) significant digits, \(1.00000\) and \(1.00001\) may both round to \(1.00000\) if the sixth digit cannot hold the distinction—difference becomes \(0\) instead of \(10^{-5}\).
Algebraic rewrite \((1+x)^2-1\to 2x+x^2\) keeps the small \(x\) visible.
D3 — Rationalize for stability.
\(f(x)=\sqrt{x+1}-\sqrt{x}=\dfrac{1}{\sqrt{x+1}+\sqrt{x}}\).
For large \(x\), left subtracts nearly equal roots; right is a single well-scaled quotient.
D4 — Propagation table in action.
Two factors each with \(2\%\) relative error: product relative error \(\approx 4\%\) (first-order).
Sum of \(50\) terms each with abs error \(\le 10^{-4}\): worst-case abs bound \(5\cdot 10^{-3}\) (errors need not cancel).
D5 — Machine epsilon vs underflow.
\(\varepsilon_{\mathrm{mach}}\): relative spacing near \(1\) (next number after \(1\) is about \(1+\varepsilon\)).
Underflow threshold: smallest positive normal magnitude—far smaller than \(\varepsilon\) as an absolute number near zero. Do not confuse the two.
D6 — Binary \(0.1\) link to Day 3.
Decimal \(0.1=\frac{1}{10}\) has denominator prime factor \(5\); in binary only primes \(2\) terminate. So \(0.1\) is repeating in binary—hence classic 0.1+0.2≠0.3 stories in floating-point.
Extra practice set
- True \(\sqrt{2}\approx 1.41421356\), approx \(1.41\): abs, rel, percent error.
- Bound abs error rounding to \(3\) decimal places (round-to-nearest).
- Rewrite \(1-\sqrt{1-x}\) for small \(x\) by rationalizing.
- Why currency as integer cents beats binary float: give a two-sentence argument.
- If \(\hat x=x(1+\delta)\), show relative error equals \(|\delta|\).
Synthesis checklist (error day)
Syn-A. Compute abs/rel/percent for one approximation; state the true base.
Syn-B. Give one catastrophic cancellation numeric story at fixed digit precision.
Syn-C. Rationalize one difference of square roots (or \(1-\sqrt{1-x}\)).
Syn-D. Bound a sum of \(n\) absolute errors; approximate a product’s relative error.
Syn-E. Define machine epsilon in one sentence and contrast it with underflow.
Syn-F. Link non-terminating binary decimals (Day 3 primes other than \(2\)) to float surprises.
Work Syn-A through Syn-D closed book before claiming the day done.
Tomorrow
Day 10 — Gate I. Mixed portfolio exam covering Days 1–9: integers through error analysis, with timed-feel sections and answer keys for half the items.
Day 10 — Gate I
Stage I · gate day
Goal: Demonstrate fluent number sense across Days 1–9 without notes: integers and precedence, fractions, decimals/percent/sci, primes/gcd/lcm, div/mod, binary/hex, two’s complement, exponents/logs, and error.
Why this matters
Gates exist for retention, not theater. Stage II algebra assumes you can evaluate, convert, reduce, and estimate without re-deriving grade-school rules mid-proof. Treat this as a diagnostic: misses become a short repair list, not a moral failure.
Theory
What Gate I owns
| Days | Must be automatic |
|---|---|
| 1 | Precedence, associativity, signs, parity proofs, \(|a+b|\le|a|+|b|\) |
| 2 | \(\mathbb{Q}\) ops, equality \(ad=bc\), reduce, complex fractions |
| 3 | Fraction/decimal/percent, scientific notation, compound \(\%\) |
| 4 | Primes, gcd/lcm, FTA use, Euclid infinite primes |
| 5 | Division algorithm, floor/ceiling, signed mod conventions |
| 6 | Base \(2\)/\(16\) conversions, nibbles, Horner |
| 7 | Binary add, two’s complement range & negation, overflow idea |
| 8 | Exponent/log laws, \(\log_2\) bit counts |
| 9 | Absolute vs relative error, cancellation awareness |
How to sit the gate
- Closed book first pass (timer optional: \(90\)–\(120\) minutes).
- Mark unsure items; do not peek yet.
- Check answers; log each miss: symptom → correct idea → one similar redo.
- Repair day: only the weak topics, then retest those items cold within a week.
Definitions to write from memory (warm-up)
Before problems, write on blank paper:
- Division algorithm statement
- \(\gcd(a,b)\cdot\operatorname{lcm}(a,b)=|ab|\)
- Two’s complement range for width \(n\)
- \(\log_b x = y \Leftrightarrow b^y=x\)
- Absolute and relative error formulas
- Triangle inequality for \(|\cdot|\)
- Even/odd definitions
If you cannot write them, review the matching day before speed work.
Mixed strategies
- Simplify fractions before multiplying.
- For mods, reduce intermediates; state remainder convention.
- For bases, prefer nibble groups over giant decimal detours when going binary↔︎hex.
- For signed bits, state width first.
- For error, always ask “relative to what?”
- For parity, write \(2k\) / \(2k+1\), not examples alone.
Section map (timed-feel)
| Section | Focus | Suggested time |
|---|---|---|
| A | Arithmetic, fractions, decimals, percent | \(25\) min |
| B | Primes, gcd/lcm, div/mod, floor | \(25\) min |
| C | Bases, binary, two’s complement, bits | \(25\) min |
| D | Exp/logs, error; short proofs | \(30\)–\(40\) min |
Worked examples (calibration)
Example 1 — Arithmetic & fractions
Evaluate \(\dfrac{3}{4}\div\dfrac{9}{10}-\dfrac{1}{6}\) and reduce.
\(\dfrac{3}{4}\cdot\dfrac{10}{9}=\dfrac{30}{36}=\dfrac{5}{6}\), then \(\dfrac{5}{6}-\dfrac{1}{6}=\dfrac{4}{6}=\dfrac{2}{3}\).
Example 2 — gcd/mod
\(\gcd(252,90)\) by Euclid: \(252=2\cdot 90+72\), \(90=1\cdot 72+18\), \(72=4\cdot 18+0\) → \(18\).
\(100\bmod 7=2\); \(-100\) as \(7q+r\) with \(r\ge 0\) → \(r=5\).
Example 3 — Bases & two’s complement
\((2A)_{16}=(101010)_2=42\).
\(8\)-bit two’s complement of \(-5\): start from \(5=00000101\), invert \(11111010\), add \(1\) → \(11111011\).
Example 4 — Logs & bits
\(\log_2 64=6\); values \(0..63\) need \(6\) bits; values \(0..64\) need \(7\) bits.
\(\log_2(2^3\cdot 2^5)=\log_2(2^8)=8\).
Example 5 — Error
Approximate \(\pi\approx 22/7\). Absolute error \(|22/7-\pi|\approx 0.00126\); relative \(\approx 0.0004\).
Example 6 — Parity proof
Sum of two odds is even: \((2k+1)+(2\ell+1)=2(k+\ell+1)\).
Example 7 — Compound percent
\(200\times 1.1\times 0.9=198\).
Example 8 — Scientific notation
\((3\times 10^{-2})(4\times 10^{5})=1.2\times 10^{4}\).
Exercises — Section A (Arithmetic, \(\mathbb{Q}\), decimals)
Answer key sketches provided for starred items.
A1.* Evaluate \(8-3\times 2+12\div 4\) and \((8-3)\times(2+12)\div 4\).
A2. Evaluate \(-3^{2}\), \((-3)^{2}\), and \(-(-3)^{2}\).
A3.* Prove: product of two odd integers is odd.
A4. Compute \(\dfrac{5}{12}+\dfrac{7}{18}\) as a reduced fraction.
A5.* Simplify \(\dfrac{\frac{2}{3}-\frac{1}{4}}{\frac{5}{6}}\).
A6. Convert \(0.\overline{12}\) to a reduced fraction.
A7. A price goes \(80\to 100\to 80\). Percent change each step? Final vs original?
A8.* Write \(0.00045\) and \(450000\) in scientific notation; compute their product in scientific notation.
A9. Does \(\dfrac{7}{28}\) terminate as a decimal? Justify with the \(2\)–\(5\) criterion after reducing.
A10. Verify \(|{-6}+4|\le|{-6}|+|4|\) and compute the slack.
Exercises — Section B (Primes, gcd, div/mod)
B1.* Factor \(840\) into primes; count positive divisors.
B2. Compute \(\gcd(180,48)\) and \(\operatorname{lcm}(180,48)\); verify \(\gcd\cdot\operatorname{lcm}=|ab|\).
B3. State Euclid’s infinite primes proof in \(\le 6\) sentences.
B4.* Find \(q,r\) for \(a=-45\), \(d=7\) with \(0\le r<7\).
B5. Evaluate \(\lfloor -17/5\rfloor\), \(\lceil -17/5\rceil\), \(\lfloor 17/5\rfloor\).
B6. How many pages of size \(12\) for \(100\) items? Items on last page?
B7.* Compute \(17\bmod 5\) and explain what Python vs C might do for \((-17)\%5\).
B8. Prove: \(n\) and \(n+1\) are coprime.
B9. \(\operatorname{lcm}(12,18,30)\) via prime maxima.
B10. List residue classes of \(0,1,2,3,4\) as canonical remainders mod \(5\); which class contains \(47\)?
Exercises — Section C (Bases, binary, two’s complement)
C1.* Convert \((1101011)_2\) to decimal and to hex.
C2. Convert \(200_{10}\) to binary and hex.
C3. Convert (3F2)\(_{16}\) to binary by nibbles.
C4.* Write \(8\)-bit two’s complement for \(-20\) and for \(20\).
C5. State the two’s complement range for \(n=8\) and for \(n=16\).
C6. Add the \(8\)-bit patterns for \(100\) and \(50\); interpret as signed; did overflow occur?
C7.* Compute \(25\;\&\;13\), \(25\|13\), \(25\hat{}13\).
C8. What is \(11\ll 2\) and \(40\gg 2\) (nonnegative logical)?
C9. Why is negating 10000000 in \(8\)-bit two’s complement special?
C10. Horner-evaluate (2B)\(_{16}\).
Exercises — Section D (Exp/logs, error, short proofs)
D1.* Simplify \(2^{5}\cdot 2^{-2}\) and \((2^{5})^{2}\); solve \(2^{x}=64\).
D2. Evaluate \(\log_2 32\), \(\log_5 125\), and \(\log_9 27\).
D3. How many bits to represent IDs \(0..999\)?
D4.* Prove \(\log_b(xy)=\log_b x+\log_b y\) from definitions.
D5. True \(x=2.5\), approximation \(2.4\): absolute and relative error.
D6. Explain catastrophic cancellation with a one-line numeric story at \(6\)-digit precision.
D7.* Prove the triangle inequality \(|a+b|\le|a|+|b|\) for integers (or reals).
D8. Change of base: write \(\log_8 2\) using \(\log_2\).
D9. Machine epsilon: define in one sentence; why is it not “smallest positive float”?
D10. Prove: sum of an even and an odd is odd. (Full write-up.)
Answer key sketches (starred + half of unstarred)
A1. \(8-6+3=5\); \((5)\times(14)/4=70/4=17.5\) or \(\frac{35}{2}\).
A3. \((2k+1)(2\ell+1)=4k\ell+2k+2\ell+1=2(\cdots)+1\).
A5. Num \(\frac{8-3}{12}=\frac{5}{12}\); divide by \(\frac{5}{6}\): \(\frac{5}{12}\cdot\frac{6}{5}=\frac{1}{2}\).
A8. \(4.5\times 10^{-4}\), \(4.5\times 10^{5}\), product \(2.025\times 10^{2}\).
B1. \(840=2^3\cdot 3\cdot 5\cdot 7\); divisors \((3+1)(1+1)^3=32\).
B4. \(-45=7(-7)+4\) because \(7(-7)=-49\), \(r=4\).
B7. \(17\bmod 5=2\); Python-like floored \((-17)\%5=3\); C-like toward-zero remainder \(-2\).
C1. \(64+32+8+2+1=107\); hex 6B.
C4. \(20=(00010100)_2\); \(-20\) invert 11101011 add \(1\) → 11101100.
C7. \(25=(11001)_2\), \(13=(01101)_2\); AND 01001 \(=9\); OR 11101 \(=29\); XOR 10100 \(=20\).
D1. \(2^{3}=8\); \(2^{10}=1024\); \(x=6\).
D4. \(b^{m}=x\), \(b^{n}=y\) \(\Rightarrow\) \(xy=b^{m+n}\).
D7. From \(-|a|\le a\le|a|\) and same for \(b\), add; deduce bound on \(|a+b|\).
Additional half-key (selected):
A6. \(0.\overline{12}=\frac{12}{99}=\frac{4}{33}\).
A7. \(+25\%\), then \(-20\%\); product of factors \(1.25\times 0.8=1\), back to \(80\).
B2. \(\gcd=12\), \(\operatorname{lcm}=720\), \(12\cdot 720=8640=180\cdot 48\).
B5. \(\lfloor -3.4\rfloor=-4\), \(\lceil -3.4\rceil=-3\), \(\lfloor 3.4\rfloor=3\).
C5. \(-128..127\); \(-32768..32767\).
C6. \(150>127\): signed overflow; bit pattern of \(150\) as unsigned has MSB \(1\).
D2. \(5\), \(3\), \(\frac{3}{2}\).
D3. \(\lceil\log_2 1000\rceil=10\).
D5. abs \(0.1\), rel \(0.1/2.5=0.04\).
D8. \(\frac{\log_2 2}{\log_2 8}=\frac{1}{3}\).
Optional rapid-fire (untimed polish)
RF1. \(|{-3}|+{-3^{2}}+(-3)^{2}=?\)
RF2. \(\gcd(84,30)\) and \(\operatorname{lcm}(84,30)\).
RF3. \((-17)\bmod 5\) (math remainder \(\ge 0\)).
RF4. (F0)\(_{16}\) in binary.
RF5. \(8\)-bit two’s complement range and pattern for \(-1\).
RF6. \(\log_2(1/8)\) and \(\lceil\log_2 100\rceil\).
RF7. Relative error of \(99\) approximating \(100\).
RF8. Is subtraction associative? One counterexample.
RF9. \(\frac{2}{3}\div\frac{4}{9}\).
RF10. \(2^{10}\) vs \(10^{3}\) order comparison.
RF answers: \(1+(-9)+9=1\); \(6\) and \(420\); \(3\); 11110000; \(-128..127\), 11111111; \(-3\) and \(7\); \(0.01\); no, e.g. \((5-3)-1\neq 5-(3-1)\); \(\frac{2}{3}\cdot\frac{9}{4}=\frac{3}{2}\); \(1024>1000\).
Repair schedule template
| Weak day | Symptom | Redo (closed book) | Date done |
|---|---|---|---|
| 5 problems + 1 proof | |||
Time-box strategy
- Skip and star hard proofs on first pass; return if time.
- Arithmetic mistakes: re-evaluate with a second method (e.g. fraction and decimal).
- Base conversion: prefer binary↔︎hex shortcuts.
- Never spend \(>8\) minutes on one item in timed mode.
Self-score rubric
| Score band | Meaning |
|---|---|
| \(\ge 85\%\) | Stage II ready; spot-repair only |
| \(70\)–\(84\%\) | Repair weak days \(1\)–\(2\) sessions each |
| \(50\)–\(69\%\) | Re-work failed sections with notes, then retest |
| \(<50\%\) | Restart Stage I with emphasis on A/B foundations |
Count a multi-part item wrong if any critical subpart fails. Proofs: full credit for correct structure even if arithmetic side-check slips.
CS connection
Gate I is the numeric literacy layer under parsing, hashing, bitwise flags, complexity logs, and floating-point skepticism. Stage II will still use every skill here inside algebra.
Common pitfalls (exam mode)
| Pitfall | What to do instead |
|---|---|
| Rushing precedence | Rewrite in steps |
| Wrong signed remainder | State convention explicitly |
| Hex without padding nibbles | Pad left to \(4k\) bits |
| Relative error with wrong base | Divide by true \(|x|\) |
| Proof by single example | Use definitions |
| Forgetting overflow on signed add | Check range \(-2^{n-1}..2^{n-1}-1\) |
Checkpoint
- Warm-up definitions written closed-book
- Sections A–D attempted under time
- Starred answers checked; miss log started
- Repair plan dated within one week
- One parity proof and one \(\log\) or triangle proof written cleanly
Write two takeaways and your three weakest topics.
Deep dive — mixed Gate I drills with sketches
G1 — Fraction + percent + sci in one chain.
Compute \(\dfrac{3}{8}\) of \(2.4\times 10^{3}\), then express the result as a percent of \(10^{3}\).
\(\frac{3}{8}\cdot 2.4\times 10^{3}=0.9\times 10^{3}=9.0\times 10^{2}\).
As percent of \(10^{3}\): \(\frac{900}{1000}=0.9=90\%\).
G2 — gcd, mod, floor together.
\(\gcd(252,90)=18\). Math remainder \((-45)\bmod 7=4\) because \(-45=7(-7)+4\).
\(\lfloor -17/5\rfloor=-4\), \(\lceil -17/5\rceil=-3\).
G3 — Bases + two’s complement.
\((1101011)_2=107=(6B)_{16}\).
\(8\)-bit \(-20\): \(20=(00010100)_2\), invert 11101011, +1 → 11101100.
Range \(n=8\): \(-128..127\); pattern for \(-1\) is 11111111.
G4 — Exp/log + bits.
\(\log_2 32=5\); \(\log_9 27=\frac{3}{2}\); bits for IDs \(0..999\): \(\lceil\log_2 1000\rceil=10\).
\(\log_b(xy)=\log_b x+\log_b y\) via \(b^{m+n}=b^m b^n\).
G5 — Error + triangle inequality.
Approx \(2.4\) for true \(2.5\): abs \(0.1\), rel \(0.04\).
\(|a+b|\le|a|+|b|\) from \(-|a|\le a\le|a|\) and same for \(b\).
G6 — Parity proof template (must-pass).
Odd \(\times\) odd: \((2k+1)(2\ell+1)=4k\ell+2k+2\ell+1=2(\cdots)+1\).
Even + odd: \(2k+(2\ell+1)=2(k+\ell)+1\) odd.
Extra rapid-fire (second pass)
RF11. \(\frac{5}{6}-\frac{1}{4}\) reduced.
RF12. \(\operatorname{lcm}(12,18,30)\) via max exponents.
RF13. (F0)\(_{16}\) binary; \(8\)-bit meaning as unsigned.
RF14. \(2^{x}=64\); \(\log_2(1/8)\).
RF15. Relative error of \(99\) approximating \(100\); machine epsilon in one sentence.
RF answers (11–15): \(\frac{10-3}{12}=\frac{7}{12}\); \(2^2\cdot 3^2\cdot 5=180\); 11110000 \(=240\); \(x=6\), \(-3\); \(0.01\); gap between \(1\) and next representable above \(1\).
Timed second-pass strategy
- Re-do only starred misses cold.
- Write one full parity proof and one log law proof without notes.
- Convert one hex↔︎binary pair and one signed \(8\)-bit value under \(2\) minutes.
- Update the repair table with dates—Gate I is diagnostic, not a trophy.
Tomorrow
Day 11 — Variables & expressions. Atoms vs expressions, evaluation, like terms, algebraic identities preview, free vs bound analogy—algebra begins in earnest (Stage II).