Sesión 55: Aritmética Numérica de Alto Rendimiento: Criba de Eratóstenes, Kth Multiple (CTCI 17.9) y Exponenciación Rápida#

Navegación rápida:

• ← Sesión 54: Algoritmo de Kadane: Máxima Submatriz 2D y Variantes Circulares
• Sesión 56: LFU Cache (Least Frequently Used) y Graduación de Maestría Staff →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 65-80 minutos.
• Código fuente compilado y probado: practica-rust/dia_55.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

En esta sesión estudiamos los algoritmos numéricos y de teoría de números esenciales para sistemas de alto rendimiento, criptografía moderna y generación ordenada de múltiplos primos sin duplicados. Consulta el Glosario Maestro y la Guía de Diagramas.

Criba de Eratóstenes (Sieve of Eratosthenes / LeetCode 204)#

• (a) En palabras simples (intuición): Imagina que tienes una cuadrícula con todos los números del 2 al 100. Miras el 2 (es primo) y tachas todos sus múltiplos pares: 4, 6, 8, 10... Luego vas al siguiente número sin tachar, que es el 3, y tachas todos sus múltiplos: 6, 9, 12, 15... Al terminar de tachar hasta la raíz cuadrada de 100 (√(100) = 10), todos los números que sobrevivieron sin tachar son pura y exclusivamente números primos.
• (b) Definición técnica paso a paso: Algoritmo para generar todos los números primos estrictamente menores que N en tiempo O(N log log N).
• Vector booleano is_prime de tamaño N, inicializado en true (con 0 y 1 en false).
• Para cada primo p ≤ √(N):
• Si is_prime[p] == true, se tachan todos sus múltiplos arrancando en p²: p², p² + p, p² + 2p, … < N.
• Los múltiplos menores a p² (como 2p, 3p, …) ya fueron tachados por primos menores.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa sobre Vec<bool>, o un BitVector compacto para consumir solo N / 8 bytes en memoria.
• (d) Error típico de Junior: Arrancar el bucle interno de tachado en 2p en lugar de p², repitiendo trabajo redundante ya ejecutado por múltiplos anteriores.

Kth Multiple / Ugly Numbers II (CTCI 17.9 & LeetCode 264)#

• (a) En palabras simples (intuición): Imagina una fábrica que produce galletas usando solo 3 ingredientes mágicos (números 3, 5 y 7). La primera galleta es el número 1. Para hacer la siguiente galleta más pequeña posible, tienes tres hornos trabajando a la vez: el horno 3, el horno 5 y el horno 7. Cada horno mira la lista de galletas ya horneadas y propone una nueva multiplicando por su factor. Eliges siempre la galleta más pequeña propuesta. Si dos hornos proponen la misma galleta (por ejemplo, 3 × 5 = 15 y 5 × 3 = 15), horneas un solo 15 y avanzas los relojes de ambos hornos para no duplicar galletas.
• (b) Definición técnica paso a paso: Algoritmo de punteros múltiples sincronizados en tiempo O(K) y espacio O(K).
• Arreglo multiples de tamaño K, iniciando con multiples[0] = 1.
• Un puntero de índice para cada factor primo: p3 = 0, p5 = 0, p7 = 0.
• En cada paso i ∈ [1, K - 1]:
  next_val = min(3 × multiples[p3], ; 5 × multiples[p5], ; 7 × multiples[p7])
  multiples[i] = next_val
• Se incrementan todos los punteros cuyo producto iguale a next_val: si 3 × multiples[p3] == next_val ⟹ p3 += 1. Esto elimina duplicados en tiempo constante O(1).
• (c) Cómo funciona en Rust (memoria y tipos): Vector continuo multiples: Vec<u64> en el Heap con aritmética en registros. Se usa u64 para prevenir desbordamientos en valores de K grandes.
• (d) Error típico de Junior: Usar un if / else if al avanzar los punteros; si un número es múltiplo de dos factores a la vez (como 15), solo avanzarías un puntero y el otro generaría un 15 duplicado en el paso siguiente.

Exponenciación Rápida Binaria (Binary Exponentiation / LeetCode 50)#

• (a) En palabras simples (intuición): Si quieres calcular 2¹⁰⁰⁰, en lugar de multiplicar el 2 mil veces en una fila interminable (O(N)), aprovechas que 2¹⁰⁰⁰ = (2²)⁵⁰⁰ = 4⁵⁰⁰. Elevas la base al cuadrado en cada paso y divides el exponente entre dos. Solo necesitas unas 10 multiplicaciones (log₂ 1000 ≈ 10) para llegar al resultado.
• (b) Definición técnica paso a paso: Algoritmo para computar x^n en tiempo O(log |n|) y espacio O(1). Se basa en la descomposición binaria del exponente:

• Si el bit menos significativo del exponente es 1 (exp & 1 == 1), acumulamos la base actual: result *= current_base.
• En cada iteración, la base se eleva al cuadrado: current_base *= current_base.
• El exponente se desplaza a la derecha: exp >>= 1.
• (c) Cómo funciona en Rust (memoria y tipos): Manejo cuidadoso de potencias negativas: si n < 0, se calcula con el exponente absoluto |n| y se retorna 1.0 / result. Para evitar overflow cuando n = i32::MIN (-2147483648), se debe convertir a i64 antes de aplicar .abs().
• (d) Error típico de Junior: Escribir n.abs() directamente en i32; en Rust i32::MIN.abs() causa pánico por overflow porque +2147483648 no cabe en un i32.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Matemática de la Criba: ¿Por qué Iniciar en p² y Terminar en √(N)?#

1. ¿Por qué el bucle exterior solo llega hasta √(N)? - Supongamos que un número compuesto C < N se descompone en dos factores: C = a × b. - Es imposible que ambos factores sean estrictamente mayores que √(N), porque si a > √(N) y b > √(N), su producto sería a × b > √(N) × √(N) = N, contradiciendo que C < N. - Por tanto, al menos uno de los factores debe ser ≤ √(N). Al tachar todos los múltiplos de los primos hasta √(N), queda garantizado que todos los números compuestos menores que N fueron tachados.
2. ¿Por qué el bucle interior de tachado arranca en p²? - Tomemos el primo p = 7. - Sus múltiplos son: 2 × 7, 3 × 7, 4 × 7, 5 × 7, 6 × 7, 7 × 7… - 2 × 7 = 14 ya fue tachado cuando procesamos el primo $2$. - 3 × 7 = 21 ya fue tachado cuando procesamos el primo $3$. - 4 × 7 = 28 ya fue tachado por el primo $2$. - 5 × 7 = 35 ya fue tachado por el primo $5$. - 6 × 7 = 42 ya fue tachado por el primo $2$. - El primer múltiplo de 7 que jamás ha sido tachado por ningún primo anterior es exactamente:
   7 × 7 = 49 = p²
   - Iniciar en p² ahorra millones de operaciones redundantes en memoria.

Deducción de Kth Multiple (CTCI 17.9): La Garantía de Orden Monótono#

¿Por qué los tres punteros garantizan generar la secuencia en orden estrictamente creciente sin ordenar?

Sea la secuencia ordenada de múltiplos: A = [m₀, m₁, m₂, …]. Cada número válido en la secuencia (excepto el 1 inicial) debe ser de la forma 3 × m_a, 5 × m_b, o 7 × m_c, donde m_a, m_b, m_c son números válidos que aparecieron antes en la secuencia.

• En cualquier paso, p₃ es el índice del número más pequeño de la secuencia que aún no ha sido multiplicado por 3.
• Análogamente, p₅ y p₇ son los índices de los números más pequeños que aún no han sido multiplicados por 5 y 7.
• El siguiente número más pequeño posible en todo el universo de números válidos es indiscutiblemente:

• Al elegir este mínimo y avanzar los punteros correspondientes, se preserva el invariante de que todos los candidatos menores ya fueron emitidos. La secuencia se genera en estricto orden monótono creciente en tiempo O(1) por número emitido.

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama de Generación de Múltiplos con 3 Punteros#

Consulta el diagrama vectorial:

flowchart TD
    STATE["Secuencia actual: [ 1, 3, 5, 7, 9 ]<br/>p3 = 2 (val 5), p5 = 1 (val 3), p7 = 1 (val 3)"] --> CALC["Calcular candidatos:<br/>c3 = 3 * 5 = 15<br/>c5 = 5 * 3 = 15<br/>c7 = 7 * 3 = 21"]
    CALC --> MIN["next_val = min(15, 15, 21) = 15"]
    MIN --> APPEND["multiples.push(15)"]
    APPEND --> ADVANCE["Avanzar punteros con valor 15:<br/>c3 == 15 -> p3 += 1 (p3 = 3)<br/>c5 == 15 -> p5 += 1 (p5 = 2)<br/>(Ambos avanzan: ¡CERO DUPLICADOS!)"]

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Ejecución de binary_pow(2.0, 10):

STACK:
[ current_base: 2.0, exp: 10 (0b1010), result: 1.0 ]

ITERACIÓN 1:
exp = 10 (0b1010). exp & 1 == 0 (último bit es 0).
result permanece: 1.0.
current_base *= current_base -> 2.0 * 2.0 = 4.0.
exp >>= 1 -> exp = 5 (0b0101).

ITERACIÓN 2:
exp = 5 (0b0101). exp & 1 == 1 (último bit es 1).
result *= current_base -> 1.0 * 4.0 = 4.0.
current_base *= current_base -> 4.0 * 4.0 = 16.0.
exp >>= 1 -> exp = 2 (0b0010).

ITERACIÓN 3:
exp = 2 (0b0010). exp & 1 == 0.
result permanece: 4.0.
current_base *= current_base -> 16.0 * 16.0 = 256.0.
exp >>= 1 -> exp = 1 (0b0001).

ITERACIÓN 4:
exp = 1 (0b0001). exp & 1 == 1.
result *= current_base -> 4.0 * 256.0 = 1024.0.
current_base *= current_base -> 65536.0.
exp >>= 1 -> exp = 0.

TERMINACIÓN: exp == 0.
Retorno: 1024.0.
Tiempo: 4 iteraciones (log2 10). Memoria: 0 bytes en Heap.

4. Las 3 Trampas Clásicas en Entrevistas y Cómo Evitarlas#

Trampa 1: Desbordamiento en i32::MIN.abs() en Binary Exponentiation#

• El error: Escribir let mut exp = n.abs(); cuando n = -2147483648.
• Por qué falla: El rango de i32 va de -2³¹ a 2³¹ - 1. El valor positivo +2147483648 no existe en i32. En Rust en modo debug, n.abs() causa un pánico por overflow.
• La solución: Convertir el entero a 64 bits antes de aplicar el valor absoluto:

  let mut exp = (n as i64).abs();

Trampa 2: Duplicados en Kth Multiple al Usar Min-Heap#

• El error: Usar una cola de prioridad (BinaryHeap) e insertar 3x, 5x, 7x sin deduplicación.
• Por qué falla: El número 15 se insertará dos veces (3 × 5 y 5 × 3), el 35 dos veces, el 105 seis veces. El Heap se satura con millones de duplicados y reporta respuestas falsas.
• La solución: Utilizar el enfoque de 3 punteros sincronizados que incrementa simultáneamente todos los punteros coincidentes en O(1) sin almacenar duplicados.

Trampa 3: Desbordamiento en Exponenciación Modular al Multiplicar#

• El error: Escribir res = (res * base) % modulus cuando res y base son u64.
• Por qué falla: Si res = 3 \times 10^9 y base = 3 \times 10^9, el producto es 9 × 10¹⁸, el cual roza o supera el límite de u64::MAX (≈ 1.84 × 10¹⁹), causando desbordamiento silencioso o pánico.
• La solución: En Rust, promover los operandos temporales a enteros de 128 bits u128 antes de multiplicar:

  res = ((res as u128 * base as u128) % modulus as u128) as u64;

5. Implementación Canónica en Rust y Comparativa con Python#

Implementación en Rust (practica-rust/dia_55.rs)#

/// Criba de Eratóstenes en O(N log log N).
pub fn sieve_of_eratosthenes(n: usize) -> Vec<usize> {
    if n <= 2 {
        return Vec::new();
    }

    let mut is_prime = vec![true; n];
    is_prime[0] = false;
    is_prime[1] = false;

    let limit = (n as f64).sqrt() as usize;
    for p in 2..=limit {
        if is_prime[p] {
            let mut multiple = p * p;
            while multiple < n {
                is_prime[multiple] = false;
                multiple += p;
            }
        }
    }

    is_prime
        .into_iter()
        .enumerate()
        .filter_map(|(idx, prime)| if prime { Some(idx) } else { None })
        .collect()
}

/// CTCI 17.9: Kth Multiple con punteros múltiples O(K).
pub fn get_kth_multiple_ctci(k: usize, factors: &[u64]) -> u64 {
    if k == 0 {
        return 0;
    }
    if k == 1 {
        return 1;
    }

    let f_len = factors.len();
    let mut multiples = vec![1u64; k];
    let mut pointers = vec![0usize; f_len];

    for i in 1..k {
        let mut next_val = u64::MAX;
        for f in 0..f_len {
            let candidate = factors[f] * multiples[pointers[f]];
            if candidate < next_val {
                next_val = candidate;
            }
        }

        multiples[i] = next_val;

        // Avanzar todos los punteros coincidentes para eliminar duplicados
        for f in 0..f_len {
            if factors[f] * multiples[pointers[f]] == next_val {
                pointers[f] += 1;
            }
        }
    }

    multiples[k - 1]
}

/// LeetCode 50: Binary Exponentiation Pow(x, n) en O(log |n|).
pub fn binary_pow(x: f64, n: i32) -> f64 {
    if n == 0 || (x - 1.0).abs() < 1e-12 {
        return 1.0;
    }
    if x.abs() < 1e-12 {
        return 0.0;
    }

    let mut exp = (n as i64).abs();
    let mut result = 1.0;
    let mut current_base = x;

    while exp > 0 {
        if exp & 1 == 1 {
            result *= current_base;
        }
        current_base *= current_base;
        exp >>= 1;
    }

    if n < 0 {
        1.0 / result
    } else {
        result
    }
}

Implementación de Referencia en Python (practica/dia_55_high_performance_arithmetic.py)#

from typing import List, Tuple


def get_kth_multiple_ctci(k: int, factors: Tuple[int, ...] = (3, 5, 7)) -> int:
    """CTCI 17.9: Kth Multiple con punteros múltiples O(K)."""
    if k <= 1:
        return 1

    multiples = [1] * k
    pointers = [0] * len(factors)

    for i in range(1, k):
        candidates = [factors[f] * multiples[pointers[f]] for f in range(len(factors))]
        next_val = min(candidates)
        multiples[i] = next_val

        for f in range(len(factors)):
            if candidates[f] == next_val:
                pointers[f] += 1

    return multiples[k - 1]


def binary_pow(x: float, n: int) -> float:
    """LeetCode 50: Pow(x, n) en O(log |n|)."""
    exp = abs(n)
    result = 1.0
    current_base = x

    while exp > 0:
        if exp & 1:
            result *= current_base
        current_base *= current_base
        exp >>= 1

    return result if n >= 0 else 1.0 / result

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Ejercicios de Práctica Independiente y Casos Límite#

1. Paso Límite 1: Primo Límite Inferior (N = 2): - Para n = 2, comprueba que sieve_of_eratosthenes(2) retorne un vector vacío, ya que se buscan primos estrictamente menores que 2.
2. Paso Límite 2: Potencia Cero de Cero (0⁰): - Analiza por qué en computación y en LeetCode 50 binary_pow(0.0, 0) se define convencionalmente como 1.0.
3. Paso Límite 3: Test de Primalidad Miller-Rabin: - Investiga cómo la exponenciación modular rápida modular_pow es el núcleo computacional del test de primalidad probabilístico de Miller-Rabin para verificar si un número de 100 dígitos es primo en milisegundos.

Navegación final:

• ← Sesión 54: Algoritmo de Kadane: Máxima Submatriz 2D y Variantes Circulares
• Sesión 56: LFU Cache (Least Frequently Used) y Graduación de Maestría Staff →
• Glosario Maestro
• Guía de Diagramas de Arquitectura