Exercício 26.6. Implemente no Julia o algoritmo de multiplicação rápida de inteiros. Cada inteiro será representado por um vetor contendo inteiros entre 0 e 999.999.

Passo 1

O enunciado pede para implementarmos em Julia o algoritmo de multiplicação rápida de inteiros (Karatsuba), representando cada inteiro como um vetor de “dígitos” base BASE=10^6. Vamos precisar:
  • Função de normalização de vetores (tratar carry e remover zeros à esquerda).
  • Operações básicas de soma e subtração de vetores.
  • Multiplicação ingênua para casos pequenos.
  • Dividir recursivamente (Karatsuba) para vetores grandes e recombinar resultados.

Passo 2

Definimos a função normalize! que ajusta carries em cada posição do vetor e remove zeros iniciais:
const BASE \(= 10^6\)

function normalize!(v::Vector{Int})
    carry \(= 0\)
    for i in \(1\):length(v)
        v[i] \(+=\) carry
        carry \(=\) div(v[i], BASE)
        v[i] %= BASE
    end
    while carry > \(0\)
        push!(v, carry % BASE)
        carry \(=\) div(carry, BASE)
    end
    while length(v) > \(1\) && v[end] == 0
        pop!(v)
    end
    return v
end

Passo 3

Implementamos soma e subtração de vetores, alinhando comprimentos por padding:
function pad!(v::Vector{Int}, n)
    while length(v) < n
        push!(v, \(0\))
    end
end

function add(x::Vector{Int}, y::Vector{Int})
    n \(=\) max(length(x), length(y))
    rx, ry \(=\) copy(x), copy(y)
    pad!(rx, n); pad!(ry, n)
    res \(=\) [rx[i] + ry[i] for i in \(1\):n]
    return normalize!(res)
end

function sub(x::Vector{Int}, y::Vector{Int})
    n \(=\) max(length(x), length(y))
    rx, ry \(=\) copy(x), copy(y)
    pad!(rx, n); pad!(ry, n)
    res \(=\) [rx[i] - ry[i] for i in \(1\):n]
    for i in \(1\):n
        if res[i] < \(0\)
            res[i] \(+=\) BASE
            res[i + 1] \(-=\) 1
        end
    end
    return normalize!(res)
end

Passo 4

Para vetores pequenos (tamanho até um limiar), usamos multiplicação ingênua :
function naive_mul(x::Vector{Int}, y::Vector{Int})
    n, m \(=\) length(x), length(y)
    res \(=\) zeros(Int, \(n + m\))
    for i in \(1\):n, j in \(1\):m
        res[i + j - 1] \(+=\) x[i] * y[j]
    end
    return normalize!(res)
end

Passo 5

Implementamos Karatsuba de forma recursiva. Se o tamanho for pequeno, chamamos naive_mul, senão dividimos cada vetor em duas metades, computamos , e , e recombinamos:
function karatsuba(x::Vector{Int}, y::Vector{Int})
    n \(=\) max(length(x), length(y))
    if n \(<= 32\)
        return naive_mul(x, y)
    end
    m \(=\) div(n + 1, 2)
    x_low = x[1:min(m, end)];  x_high = m + 1 <= length(x) ? x[m + 1:end] : [0]
    y_low = y[1:min(m, end)];  y_high = m + 1 <= length(y) ? y[m + 1:end] : [0]

    z0 = karatsuba(x_low, y_low)
    z2 = karatsuba(x_high, y_high)
    z1 = karatsuba(add(x_low, x_high), add(y_low, y_high))
    z1 = sub(sub(z1, z0), z2)

    res \(=\) zeros(Int, length(z0) + 2 * m + length(z2))
    for i in \(1\):length(z0)   res[i]       \(+=\) z0[i]   end
    for i in \(1\):length(z1)   res[i + m]     \(+=\) z1[i]   end
    for i in \(1\):length(z2)   res[i + 2 * m]   \(+=\) z2[i]   end
    return normalize!(res)
end

Passo 6

Função principal multiply(a,b) que expõe a API ao usuário:
function multiply(a::Vector{Int}, b::Vector{Int})
    return karatsuba(a, b)
end

Resposta

const BASE \(= 10^6\)

function normalize!(v::Vector{Int})
    carry \(= 0\)
    for i in \(1\):length(v)
        v[i] \(+=\) carry
        carry \(=\) div(v[i], BASE)
        v[i] %= BASE
    end
    while carry > \(0\)
        push!(v, carry % BASE)
        carry \(=\) div(carry, BASE)
    end
    while length(v) > \(1\) && v[end] == 0
        pop!(v)
    end
    return v
end

function pad!(v::Vector{Int}, n)
    while length(v) < n
        push!(v, \(0\))
    end
end

function add(x::Vector{Int}, y::Vector{Int})
    n \(=\) max(length(x), length(y))
    rx, ry \(=\) copy(x), copy(y)
    pad!(rx, n); pad!(ry, n)
    res \(=\) [rx[i] + ry[i] for i in \(1\):n]
    return normalize!(res)
end

function sub(x::Vector{Int}, y::Vector{Int})
    n \(=\) max(length(x), length(y))
    rx, ry \(=\) copy(x), copy(y)
    pad!(rx, n); pad!(ry, n)
    res \(=\) [rx[i] - ry[i] for i in \(1\):n]
    for i in \(1\):n
        if res[i] < \(0\)
            res[i] \(+=\) BASE
            res[i + 1] \(-=\) 1
        end
    end
    return normalize!(res)
end

function naive_mul(x::Vector{Int}, y::Vector{Int})
    n, m \(=\) length(x), length(y)
    res \(=\) zeros(Int, \(n + m\))
    for i in \(1\):n, j in \(1\):m
        res[i + j - 1] \(+=\) x[i] * y[j]
    end
    return normalize!(res)
end

function karatsuba(x::Vector{Int}, y::Vector{Int})
    n \(=\) max(length(x), length(y))
    if n \(<= 32\)
        return naive_mul(x, y)
    end
    m \(=\) div(n + 1, 2)
    x_low = x[1:min(m, end)];  x_high = m + 1 <= length(x) ? x[m + 1:end] : [0]
    y_low = y[1:min(m, end)];  y_high = m + 1 <= length(y) ? y[m + 1:end] : [0]

    z0 = karatsuba(x_low, y_low)
    z2 = karatsuba(x_high, y_high)
    z1 = karatsuba(add(x_low, x_high), add(y_low, y_high))
    z1 = sub(sub(z1, z0), z2)

    res \(=\) zeros(Int, length(z0) + 2 * m + length(z2))
    for i in \(1\):length(z0)   res[i]       \(+=\) z0[i]   end
    for i in \(1\):length(z1)   res[i + m]     \(+=\) z1[i]   end
    for i in \(1\):length(z2)   res[i + 2 * m]   \(+=\) z2[i]   end
    return normalize!(res)
end

function multiply(a::Vector{Int}, b::Vector{Int})
    return karatsuba(a, b)
end
# Exemplo de uso
a \(=\) [\(123456\), \(789012\)]       # representa \(789012\)*BASE \(+ 123456\)
b \(=\) [\(654321\), \(987654\)]
r \(=\) multiply(a, b)
println(r)  # vetor de "dígitos" base \(10^6\) do produto

Exercícios de Livros Relacionados