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
. 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 ,
e
, e recombinamos:
naive_mul
, senão dividimos cada vetor em duas metades, computamos
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