Chapter 23 — Integers

# --- Visualization: Two's complement overflow and Python's arbitrary integers ---
import numpy as np
import matplotlib.pyplot as plt
plt.style.use('seaborn-v0_8-whitegrid')

fig, axes = plt.subplots(1, 2, figsize=(13, 5))

# --- Plot 1: Two's complement wrapping (8-bit signed: -128 to 127) ---
ax = axes[0]
BITS = 8
# Simulate 8-bit signed integers
vals = np.arange(0, 256, dtype=np.int32)
twos_comp = vals.copy()
twos_comp[twos_comp >= 128] -= 256  # map [128,255] to [-128,-1]

ax.plot(vals, twos_comp, color='steelblue', linewidth=2)
ax.axhline(0, color='gray', linewidth=0.5)
ax.axvline(127, color='crimson', linestyle='--', linewidth=1, label='Max positive (127)')
ax.axvline(128, color='darkorange', linestyle='--', linewidth=1, label='Overflow → -128')
ax.set_xlabel('Bit pattern (unsigned interpretation)')
ax.set_ylabel('Signed value')
ax.set_title("8-bit Two's Complement: Overflow Wraps Around")
ax.legend(fontsize=8)

# --- Plot 2: Python's arbitrary-precision vs C-like int64 ---
ax = axes[1]
ns = range(0, 70)
python_vals = [2**n for n in ns]  # exact
int64_max = 2**63 - 1
# Simulate int64 overflow (just mark where it would overflow)
safe_ns = [n for n in ns if 2**n <= int64_max]
overflow_ns = [n for n in ns if 2**n > int64_max]

ax.semilogy(safe_ns, [2**n for n in safe_ns], 'o-', color='steelblue',
            label='Safe in int64', markersize=3)
if overflow_ns:
    ax.axvline(min(overflow_ns), color='crimson', linestyle='--', linewidth=1.5,
               label=f'int64 overflows at 2^{min(overflow_ns)}')
ax.set_xlabel('n')
ax.set_ylabel('2^n (log scale)')
ax.set_title('Python int: Arbitrary Precision\n(No Overflow — Ever)')
ax.legend(fontsize=8)

plt.tight_layout()
plt.show()

# --- Implementation: Division algorithm, GCD, two's complement ---

def division_algorithm(a, b):
    """
    Compute quotient q and remainder r such that a = q*b + r, 0 <= r < b.

    Args:
        a: int (dividend)
        b: int (divisor, must be positive)

    Returns:
        (q, r): tuple of ints
    """
    assert b > 0, "Divisor must be positive"
    q = a // b   # Python floor division
    r = a % b    # Python modulo (always non-negative when b > 0)
    assert a == q * b + r, "Division algorithm invariant violated"
    return q, r


def gcd_euclidean(a, b):
    """
    Greatest common divisor via the Euclidean algorithm.
    Based on: gcd(a, b) = gcd(b, a mod b), with gcd(a, 0) = a.

    Args:
        a, b: non-negative ints

    Returns:
        int: gcd(a, b)
    """
    while b:
        a, b = b, a % b
    return a


def to_twos_complement(n, bits=8):
    """
    Return two's complement bit representation of integer n in `bits` bits.

    Args:
        n: int in range [-2^(bits-1), 2^(bits-1) - 1]
        bits: int, word width

    Returns:
        str: binary string of length `bits`
    """
    if n < 0:
        n = (1 << bits) + n  # add 2^bits to negative number
    return format(n, f'0{bits}b')


# Tests
import math

print("Division algorithm:")
for a, b in [(17, 5), (-13, 5), (0, 7), (100, 3)]:
    q, r = division_algorithm(a, b)
    print(f"  {a} = {q} × {b} + {r}")

print("\nGCD (Euclidean):")
for a, b in [(48, 18), (100, 75), (17, 13), (2024, 1984)]:
    g = gcd_euclidean(a, b)
    assert g == math.gcd(a, b)
    print(f"  gcd({a}, {b}) = {g}  ✓")

print("\nTwo's complement (8-bit):")
for n in [0, 1, 127, -1, -128, -13]:
    print(f"  {n:5d} → {to_twos_complement(n)}")

print("\nPython arbitrary precision:")
big = 2 ** 1000
print(f"  2^1000 has {len(str(big))} decimal digits")

# --- Experiment 1: Python // vs C-style truncation for negative numbers ---
# Hypothesis: Python floor division and C truncation diverge exactly when a/b is negative
# Try changing: a and b

import math

print("Python // (floor division) vs C-style truncation:")
print(f"{'a':>6} {'b':>4}  {'Python a//b':>12}  {'C-style trunc(a/b)':>20}  {'Same?':>6}")
print('-' * 60)

test_pairs = [(7, 3), (-7, 3), (7, -3), (-7, -3),
              (10, 4), (-10, 4), (10, -4), (-10, -4)]

for a, b in test_pairs:
    python_result = a // b
    c_result = int(a / b)  # C-style truncation toward zero
    same = "✓" if python_result == c_result else "✗ DIFFER"
    print(f"{a:>6} {b:>4}  {python_result:>12}  {c_result:>20}  {same:>6}")

# --- Experiment 2: Euclidean algorithm step count ---
# Hypothesis: inputs near consecutive Fibonacci numbers require the most steps
# Try changing: N (search space)
import matplotlib.pyplot as plt
plt.style.use('seaborn-v0_8-whitegrid')

N = 50  # <-- modify this

def gcd_steps(a, b):
    """Count steps in Euclidean algorithm."""
    steps = 0
    while b:
        a, b = b, a % b
        steps += 1
    return steps

# Build heatmap of step counts
counts = np.zeros((N, N), dtype=int)
for a in range(1, N + 1):
    for b in range(1, N + 1):
        counts[a-1, b-1] = gcd_steps(a, b)

fig, ax = plt.subplots(figsize=(7, 6))
im = ax.imshow(counts, origin='lower', cmap='viridis',
               extent=[1, N, 1, N], aspect='auto')
plt.colorbar(im, ax=ax, label='Steps')
ax.set_xlabel('b')
ax.set_ylabel('a')
ax.set_title(f'Euclidean Algorithm Steps for a,b in [1,{N}]')
plt.tight_layout()
plt.show()

# --- Mini Project: RSA Key Generation (Simplified) ---
# Problem: RSA encryption's security rests entirely on integer arithmetic.
#          Even a toy version requires GCD, modular inverse, and prime testing.
# Task: Implement mini-RSA with small primes and encrypt/decrypt a message.

def is_prime(n):
    """Trial-division primality test."""
    if n < 2: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False
    return True

def mod_inverse(e, phi):
    """
    Compute the modular inverse of e mod phi (i.e., d such that e*d ≡ 1 mod phi).
    Uses extended Euclidean algorithm.

    Args:
        e: int
        phi: int

    Returns:
        int: d such that (e * d) % phi == 1
    """
    # TODO: implement using extended Euclidean algorithm
    pass

# Choose small primes
p, q = 61, 53  # In real RSA, these would be 2048-bit primes
assert is_prime(p) and is_prime(q)

n = p * q                    # modulus
phi = (p - 1) * (q - 1)      # Euler's totient
e = 17                        # public exponent (must be coprime to phi)

d = mod_inverse(e, phi)

if d is not None:
    # Encrypt: c = m^e mod n
    # Decrypt: m = c^d mod n
    message = 42
    ciphertext = pow(message, e, n)
    decrypted = pow(ciphertext, d, n)

    print(f"p={p}, q={q}, n={n}, φ(n)={phi}")
    print(f"Public key:  (e={e}, n={n})")
    print(f"Private key: (d={d}, n={n})")
    print(f"Message:     {message}")
    print(f"Ciphertext:  {ciphertext}")
    print(f"Decrypted:   {decrypted}")
    print(f"Round-trip:  {'✓' if decrypted == message else '✗'}")