Elements of Computations

There is no single “fastest” GCD — it depends on the inputs. The practical answer for machine-sized integers is Stein’s binary GCD (1961), which avoids the expensive division and uses only bit shifts, subtractions, and comparisons. For very large (big-integer) inputs, Lehmer’s / half-gcd algorithms are asymptotically faster.

Euclid’s algorithm (the lecture’s approach) is already optimal in the number of iterations: it takes $O(\log(\min(a,b)))$ steps, and the worst case is exactly consecutive Fibonacci numbers — the $F_{n-1}, F_n$ case analyzed in Exercise 2. Each step, however, performs a division, the slowest integer instruction the CPU decodes.

Binary GCD produces the same answer but never divides:

1. It strips out all common factors of 2,

2. strips the remaining factors of 2 from one operand, then

3. repeatedly replaces the larger of the two odd numbers with their difference.

Every operation is a cheap shift or subtract, which is why it is typically the fastest GCD in practice and what many libraries use.

long long gcd_binary(long long a, long long b) {
    if (a == 0) { return b; }
    if (b == 0) { return a; }
    int shift = 0;
    while (((a | b) & 1) == 0) { a >>= 1; b >>= 1; ++shift; } // common 2s
    while ((a & 1) == 0) { a >>= 1; }                          // 2s out of a
    do {
        while ((b & 1) == 0) { b >>= 1; }
        if (a > b) { long long t = a; a = b; b = t; }
        b -= a;
    } while (b != 0);
    return a << shift;
}

Design notes:

• No division at all — the correctness rests on the identity that $\gcd(2a, 2b) = 2\,\gcd(a,b)$ and $\gcd(2a, b) = \gcd(a, b)$ when $b$ is odd, so factors of 2 can be deferred and shifted back at the end.

• Same complexity class, smaller constant — still $O(\log(\min(a,b)))$ iterations, but each iteration is a cheap shift/subtract instead of a division, so the measured runtime is far lower (see the timing cell above).

• gcd_euclid is kept for comparison so you can see both return identical values on the Fibonacci worst case.

Computing $\sqrt{x}$ with only $+$, $-$, $\times$, $\div$ (and comparisons) is a classic. The lecture already met one such method in disguise — the fast inverse-square-root update rule $y \leftarrow y(1.5 - x y^2/2)$ is just Newton’s method applied to $f(y)=1/y^2 - x$. The three methods below are its companions; all three use nothing but the four basic operations.

1. Bisection (false position, “halve the bracket”). Keep a range $[lo,hi]$ with $lo^2 \le x \le hi^2$; put $mid=(lo+hi)/2$, and if $mid^2>x$ the root is in $[lo,mid]$, else in $[mid,hi]$. Repeat until the bracket is tiny. Uses only a multiply and a compare per step ($mid^2$ vs $x$) — no division. Converges linearly (one extra correct digit per step), so it is reliable but slow.

2. Newton–Raphson (the Babylonian / “heron” method). Solve $f(y)=y^2-x=0$; Newton’s step $y \leftarrow y - f/f'$ with $f'=2y$ is exactly

It needs a division and an average per step, and it converges quadratically: the error roughly squares each iteration, so 4–5 steps give full double precision from a crude start. This is the same update family as the lecture’s $y \leftarrow y(1.5 - xy^2/2)$, which is Newton on $1/y^2 = x$. In practice this is the family $\sqrt{x}$ hardware and libraries build on.

3. Digit-by-digit (“schoolbook” / long-division) extraction. The manual method: group the digits in pairs from the decimal point; at each step, with current answer $p$ and remainder $r$, find the largest digit $d$ such that $(20p+d) d \le r$. It is the square-root analogue of long division and uses no division at all in the digit search — only $+$, $-$, $\times$ and comparisons — which is exactly why it was the go-to method before scientific calculators.

The cell above runs all three on the lecture’s $x=10/3$ (plus a digit check on 1056) and prints Newton’s converging steps.

Design notes:

• Same answer, different speeds. Bisection and Newton both find $\sqrt{10/3} \approx 1.825741858350554$; Newton reaches full precision in ~5 iterations where bisection would need ~50. The digit method is exact for perfect squares and gives $\lfloor\sqrt{x}\rfloor$ otherwise.

• Newton is the bridge to the lecture. Its update $y \leftarrow y(1.5 - xy^2/2)$ for $1/\sqrt{x}$ is the same contraction, just targeting the reciprocal — which is why a good initial guess (the famous bit-trick) matters so much there.

• All arithmetic, no sqrt(). The whole point is these reproduce the result of the library call using only the basic operations the CPU is guaranteed to have.

First, a small correction to the question: the C++ standard never requires int to be 16 bits — it requires it to be at least 16 bits. It also only requires an ordering, not exact widths: sizeof(short) ≤ sizeof(int) ≤ sizeof(long), with short at least 16 bits, int at least 16 bits, and long at least 32 bits. Within those floors, the width of int is implementation-defined — the compiler picks it for the target machine. The cell above prints this machine’s actual widths (16/32/64/64 here) and checks the ordering.

So int is 32 bits on this machine for three reinforcing reasons:

1. int is meant to be the native word size. The whole design is that int is “the integer the hardware handles best.” On a 32-bit CPU (the x86 era) the natural word is 32 bits, so int is 32. On today’s 64-bit machines the hardware word is 64, but the int/long/pointer layout is frozen by the data model of the platform, not by the language:

   • ILP32 (32-bit systems): int = long = pointers = 32 bits.

   • LP64 (Linux/macOS x86-64, ARM64): long and pointers = 64, but int stays 32.

   • LLP64 (Windows x86-64): long long and pointers = 64, long stays 32, int stays 32. In every modern model int is 32; that’s why you see 32 even on 64-bit machines.

2. Backward compatibility. If int suddenly doubled to 64 bits, every loop counter, array index, and binary layout written for the 32-bit world would change size, break the ABI, and change how much memory programs use. Keeping int at 32 lets decades of code run unchanged — which is exactly the portability C and C++ were built to give.

3. The minimum exists for tiny machines. The “at least 16” floor is what lets the same source compile on 16-bit microcontrollers (where int is 16) and on big machines. On such embedded targets, int legitimately is 16 bits — the standard’s floor is met, nothing more. That’s precisely why the next cell recommends fixed-width types (int16_t, int32_t, int64_t from <cstdint>) when you actually need a guaranteed size across platforms.

In short: 32 bits is not something the standard demands — it’s the value the implementation chose because 32 is the native, historically-stable word size for int on every common platform, and it happens to sit comfortably above the standard’s 16-bit floor.

Design notes:

• The ordering is the real guarantee. short <= int <= long is what the standard actually pins down; the 16/32/64 numbers are lower bounds, and on real systems the types are typically exactly 16 / 32 / 32-or-64.

• Don’t write “32” where it matters — if code depends on the width, use int32_t (and friends); if it just needs “a normal integer,” int is the right, idiomatic choice.

None of the three, guaranteed. int one = one + 1; is undefined behavior — the one on the right-hand side is the same variable being declared, and it has no value yet when the initializer runs. You’re reading it before it’s initialized.

Why none of one+1, 1, or 0 is a correct answer:

• Not one+1 — there is no earlier one to add to; the name doesn’t refer to any existing object here.

• Not 0 by rule — it’s not “zero-initialized” like a static; an automatic variable with no initializer just holds indeterminate (garbage) bytes.

• Not 1 by rule either — on this machine, in this cell, the garbage happened to be 0, so 0 + 1 printed 1. That’s luck, not the language.

The cell above makes this concrete: g++ warns ‘one’ is used uninitialized (-Wuninitialized), and the printed value depends on whatever was already in that stack slot. A different compiler, optimization level, or a few instructions earlier could print anything — 1, -1, a huge number, etc. The only thing you can say is that the read is undefined behavior, so any value (or a crash) is “correct.”

That’s also why the note says auto would not work: auto one = one + 1; can’t deduce a type from an initializer that itself refers to the very variable being deduced.

Design notes:

• Point of declaration — a variable is only usable from after its full declaration is done; the initializer still belongs to the declaration, so one isn’t in scope with a value until the initializer is finished. Reading it there is illegal.

• The sibling cell int one(one+1); is the same trap written in function-style (direct) initialization — also undefined behavior, also flagged by -Wuninitialized.

There is no single “correct” rule for what $a/b$ should return when the result is not an integer — you must drop part of the fractional part, and there are two natural ways to do it. C++ and Python simply chose different ones, for different reasons.

Both languages agree on the identity $a = q\cdot b + r$ with $|r| < |b|$. What differs is which integer $q$ lands on, and the remainder $r$ is forced to follow:

• C++ truncates toward 0 (round $a/b$ down in magnitude). The remainder $r = a - qb$ then carries the sign of the dividend $a$ — so $-5/3 = -1$ and $-5 \% 3 = -2$.

• Python floors toward $-\infty$ (round $a/b$ down to the next smaller integer). The remainder then carries the sign of the divisor $b$ — so $-5//3 = -2$ and $-5 \% 3 = 1$.

Why they differ — the design motivation:

• C++ reflects the hardware. On the machines C++ targets, integer division is a single idiv instruction that truncates toward zero (it keeps the top word of the quotient). The language exposes that behavior directly, so a/b and a%b share the dividend’s sign and the two operations stay consistent with one instruction.

• Python prioritises mathematical and modular convenience. Floor division makes the remainder always non-negative when the divisor is positive ($0 \le a \% b < b$), which is exactly the textbook definition of a residue and what you want for indexing, wrapping, and modular arithmetic — e.g. $(-5) \% 3 = 1$ is the same residue class as 1, so $a \% b$ is ready to use as a 0-based index without a sign fix-up.

In short: C++ optimises for the machine (truncate, match idiv); Python optimises for the maths (floor, non-negative residues). The code cell above reproduces both rules with the same two-line identity and shows the results line up with the lecture’s 5/3, -5/3, 5/-3, -5/-3 examples.

Design notes:

• div_py is implemented on top of the C++ divide: take the truncating quotient, then step down once more if the remainder’s sign disagrees with the divisor’s — the floor is at most one unit away from the truncation.

• a == q*b + r is printed for both and is always 1 (true): both schemes are valid Euclidean divisions, they just split the quotient/remainder differently.

C++11 replaced the C-style cast with four named casts, each doing one thing with a compile-time check. The cell above exercises all of them (the lines are its real g++ output, not a sample).

• static_cast — the workhorse: reasonable value conversions (numeric, or up/down casts in a class hierarchy). int n = static_cast<int>('A'); → 65.

• const_cast — the only legal way to add or remove const/volatile. int* pc = const_cast<int*>(&cv); (forming the pointer is fine; writing through it is undefined behavior).

• reinterpret_cast — low-level re-interpretation between unrelated types, or pointer ↔ integer. Same bytes, new type. int64_t bits = reinterpret_cast<int64_t&>(dd); is the bit-trick behind the fast inverse square root from earlier.

• dynamic_cast — the safe down/cross-cast in a polymorphic hierarchy. It checks at runtime and returns nullptr on failure (throws bad_cast for references). dynamic_cast<D*>(&plain) → nullptr because a B is not really a D.

• C-style cast (int)'A' — the legacy kitchen sink: it silently picks whichever of the four above fits, with none of the type-safety checks. That is why the lecture prefers the named casts; a (T*) pointer-cast that static_cast would reject quietly becomes a reinterpret_cast in disguise.

The one-line mapping: static_cast = value/type you mean; const_cast = drop const; reinterpret_cast = same bits, new type; dynamic_cast = is this really a subclass?; (T)x = all of the above, unchecked.

Nothing is truncated by the C++ program — it writes all 26 bytes of the formatted string. The display is cut short because the string contains a NUL byte.

The cell above is executed in the cell just above — its hex dump is its real output, not a sample. Formatting static_cast<char>(0) inserts the NUL character (byte value 00) into the string, right after "The ASCII code of ":

The formatted string has 26 bytes:
54 68 65 20 41 53 43 49 49 20 63 6f 64 65 20 6f 66 20 00 20 69 73 20 30 2e 0a

That 00 at position 18 is the embedded NUL. The terminal / notebook display treats a NUL byte like the end of the text (it is how C-style strings are terminated), so the visible output stops after The ASCII code of — even though is 0. (bytes 69 73 20 30 2e 0a) was actually written to stdout after it. The same thing happens in the preceding lecture cell; it is not a bug in format.

Design notes:

• char is an integer type, so format("{}", c) accepts it and prints the character it denotes — including control characters such as NUL. For the value, format the character as an integer: (int)c0 (or static_cast<int>(c)).

• The string object itself is complete (26 bytes here); only its presentation is cut at the NUL. This is why static_cast<char>(128) “works” when used as an expression value (cell 8df9631f) but printing it behaves differently — the value is fine, displaying it is the issue.

Pass by constant reference declares a parameter as const T& — a read-only alias for the caller’s argument, not a copy. Why the const matters:

• Read-only inside the function. The function cannot modify the caller’s object, and the contract is visible in the signature.

• No copy. For a large object (e.g., const std::string&), binding a reference costs a handful of bytes as compared to copying the whole object. Pass by reference avoids the copy, and const adds the safety of guaranteeing no modification.

• Rvalues are admissible. A const T& parameter can bind to temporaries (as 123 did above), which is why library functions that only read their inputs declare them this way; a plain T& cannot bind to 123 at all.

C++ gives every expression one of three value categories: lvalue, prvalue, or xvalue. The fundamental split is lvalue vs. rvalue: an lvalue names a region of memory that persists — it has identity (you can take its address and use it again) — while an rvalue is a value to be consumed. Rvalue is the umbrella term for the other two: a prvalue is a pure value with no identity of its own, and an xvalue is an expiring object (it keeps identity but is explicitly marked movable).

value_categories.ipynb

Part A — the lvalue / rvalue split, computed by overload resolution. category is overloaded on T& versus T&&: an lvalue argument binds T& (which is preferred), but an rvalue argument can only bind T&&, so the T&& overload catches exactly the rvalues. The output confirms the usual rules:

• demo_a, s, and s[0] are lvalues — a variable and a subscript both name a region of memory.

• demo_a + 1, the temporary std::string("world"), and s.size() (returned by value) are rvalues.

• std::move(demo_a) and std::move(s) are rvalues — std::move moves nothing by itself; it only casts to an rvalue reference.

Part B — rvalues split into prvalue and xvalue. A single function parameter cannot tell these two apart (both bind T&&), so rvalue_kind inspects decltype instead: an xvalue still refers to an object, so decltype(std::move(demo_a)) is int&&, whereas a prvalue is a pure value, so decltype(demo_a + 1) is int. Hence std::move(demo_a) is an xvalue but demo_a + 1 and the new string are prvalues.

Part C — the ++ asymmetry the lecture alluded to. ++c returns a reference to c, so it is an lvalue; d++ returns a copy, so it is a prvalue. That is precisely why (++c) = 1 compiles while (d++) = 1 does not — the real compiler rejects the latter with lvalue required as left operand of assignment (see Exercise 13).

Part D — the payoff: an xvalue enables a move. Binding the lvalue p to a ValueCatDemo&& parameter via std::move(p) turns it into an xvalue, so the move constructor runs and p is drained; copying the lvalue q runs the copy constructor instead. Real output:

p (prvalue in)  / q (from xvalue) / r (from lvalue):
  move constructor (from n=3)
  copy constructor (from n=3)
p=0 q=3 r=3 (p was emptied by the move)

In one line: an lvalue is an addressable object, an xvalue is an expiring object (the one that can be moved), and a prvalue is a value with no identity of its own (a literal, a computed result, a by-value return). It is what lets the compiler choose between copying and moving, and lets references bind to temporaries — the same reason a const int& was able to bind the literal 123 in the previous cell.

The expression returns true, not false. This is an unsigned arithmetic trap. Let me read the surrounding cells for context.

Yes — intuitively it should be false ("Ava" is 3 chars, "Betty" is 5, so Ava is shorter). But in C++ it actually returns true. That mismatch is exactly the point of this cell (the markdown just above it calls this “a logical error” from misunderstanding the return type).

Why it’s true

std::strlen returns std::size_t, which is an unsigned integer. So the subtraction is done in unsigned arithmetic, and unsigned subtraction wraps around instead of going negative:

strlen("Ava") - strlen("Betty")
// 3 - 5 in size_t = 2^64 - 2 = 18446744073709551614

That huge positive number is, of course, > 0, so the whole expression is true.

I verified it by compiling:

strlen("Ava") = 3
strlen("Betty") = 5
diff = 18446744073709551614
diff > 0 ? 1            // true  <-- the buggy version
int version: 0          // false <-- if the operands were signed

The general trap

This is the classic unsigned wraparound bug. It shows up everywhere you compare two size_t values directly:

size_t a = 3, b = 5;
a - b > 0;   // true, but a < b!

How to write it correctly — compare the lengths directly, and never subtract two unsigned values expecting a negative:

strlen("Ava") > strlen("Betty");   // false, correct
// or, to express "Ava is shorter":
strlen("Ava") < strlen("Betty");   // true

So your instinct is right about the intended semantics — the lesson is that C++ won’t give you that signed result automatically; the size_t return type silently turns your a - b > 0 idiom into a tautology. Compare the operands, don’t subtract-then-compare.

First, a small correction: the length is recorded in the type only while the string is still an array. The literal "15" has type const char[3], and that 3 is known at compile time only. The moment the array is used as a pointer — which is what every string function actually receives — the type no longer records any length at all, and the null terminator is the only record of the length left at runtime. That is why it is needed.

Is the byte wasted? It is a constant one-byte overhead, and in exchange C gets a runtime string representation that is just a plain sequence of bytes: no header, no length field to keep in sync, no allocator, and the string can live in read-only program memory (which is exactly where literals do). The alternative design — storing the length alongside the characters, a length-prefixed string — is what std::string and most other languages’ string types use, and it can be more space-efficient. C deliberately traded that for a minimal, headerless representation in which any function can find the end of the string by scanning, with nothing to pass in besides the pointer.

strlen counts bytes, not symbols — that is exactly why it returned 3 for "思" even though it is a single symbol. To count the symbols of a variable-length encoding, scan the byte sequence and use the structure of that encoding:

count_symbols.ipynb

• UTF-8 ("思"): each symbol occupies 1–4 bytes. The first byte of a symbol is never a continuation byte (which has the bit pattern 0b10xxxxxx); all remaining bytes of the symbol are continuation bytes. So utf8_symbols counts the bytes c with (static_cast<unsigned char>(c) & 0xC0) != 0x80.

• UTF-16 (u"思"): each unit is a char16_t (2 bytes). Most symbols occupy one unit, but a symbol outside the basic multilingual plane — such as 😎 — occupies a surrogate pair: a high surrogate (0xD800–0xDBFF) immediately followed by a low surrogate. So utf16_symbols counts the units, skipping the second unit of each pair.

The code above was compiled and run with g++ (-std=c++23 -O2) — the four lines below are its real output, not a sample:

"15": bytes=2, symbols=2
"思": bytes=3, symbols=1
"😎": bytes=4, symbols=1
u"思😎": code units=3, symbols=2

The last line is the sharpest contrast: sizeof(u"思😎")/2 - 1 gives 3 (思 one unit + 😎 two units), while the number of symbols is 2 — the byte count with the terminator removed gets the answer wrong in both encodings for this string (7 vs 2 in UTF-8, 3 vs 2 in UTF-16), and only agrees by luck when every symbol is one byte (or one unit).