Multiplicação e Ponto Flutuante
Vídeo da aula estará disponível em breve
Algoritmo de Multiplicação: Shift-and-Add
A multiplicação binária funciona exatamente como a multiplicação "na mão" que aprendemos no ensino fundamental — mas em base 2 é ainda mais simples, porque cada dígito do multiplicador é 0 ou 1.
Multiplicação Binária — Exemplo Manual
# Multiplicar 0110 (6) × 0101 (5)
0110 (multiplicando = 6)
× 0101 (multiplicador = 5)
──────
0110 (0110 × 1, deslocado 0 posições)
0000 (0110 × 0, deslocado 1 posição)
0110 (0110 × 1, deslocado 2 posições)
0000 (0110 × 0, deslocado 3 posições)
────────
0011110 (= 30 = 6 × 5 ✓)
Regra: para cada bit do multiplicador:
Se bit = 1 → soma o multiplicando (deslocado) ao produto
Se bit = 0 → soma 0 (não faz nada)
Desloca o multiplicando 1 posição à esquerda
N bits × N bits → resultado de até 2N bits
(32 × 32 → 64 bits, por isso MIPS usa HI:LO)Algoritmo Otimizado — Shift-and-Add
# Versão otimizada (usada no hardware real):
# Em vez de deslocar o multiplicando para a esquerda,
# desloca o PRODUTO para a direita.
Inicialização:
Produto[63:0] = 0
Produto[31:0] = Multiplicador (reusa a metade inferior!)
Multiplicando = valor original
Repetir 32 vezes:
1. Se Produto[0] == 1:
Produto[63:32] += Multiplicando
2. Shift right Produto inteiro (64 bits) por 1
Exemplo (4 bits): 6 × 5
Multiplicando = 0110
Iter Produto (8 bits) Ação
──── ──────────────── ─────────────────────────
init 0000 0101 Produto[3:0] = multiplicador (5)
1 0011 0010 bit0=1, soma: 0110+0000=0110, shift: 0011 0010
2 0001 1001 bit0=0, não soma, shift: 0001 1001
3 0100 1100 bit0=1, soma: 0001+0110=0111, shift: 0011 1100
Correção: 0001 1001 → bit0=1, soma nos upper:
0001+0110=0111 → 0111 1001, shift: 0011 1100
4 0001 1110 bit0=0, shift: 0001 1110 = 30 ✓
Custo: 32 ciclos de clock para uma multiplicação
(multiplicadores modernos usam array de somadores
para fazer tudo em 1-3 ciclos)Algoritmo de Divisão
A divisão binária segue o mesmo princípio da divisão longa: tentar subtrair o divisor do dividendo, registrando 1 no quociente se a subtração é possível, 0 se não é.
Divisão Binária — Restoring Division
# Dividir 7 (0111) por 2 (0010)
# Esperado: quociente = 3, resto = 1
Algoritmo (Restoring Division):
Inicialização:
Remainder[63:32] = 0
Remainder[31:0] = Dividendo (0111)
Divisor = 0010
Repetir 32 vezes:
1. Shift left Remainder por 1
2. Remainder[63:32] -= Divisor
3. Se resultado < 0:
Remainder[63:32] += Divisor (restaura)
Shift left quociente, Q[0] = 0
Senão:
Shift left quociente, Q[0] = 1
Resultado:
Quociente nos bits inferiores
Resto nos bits superiores
No MIPS:
div $s1, $s2 # LO = $s1 / $s2, HI = $s1 % $s2
mflo $t0 # quociente
mfhi $t1 # resto
Divisão é MUITO mais lenta que multiplicação:
~32-40 ciclos vs ~3-5 ciclos para multiplicaçãoIEEE 754: Ponto Flutuante
Inteiros são insuficientes para representar o mundo real: temperaturas, distâncias, probabilidades, coordenadas. Para isso, usamos ponto flutuante — o equivalente binário da notação científica.
IEEE 754 — Formato
Notação científica decimal: -6.022 × 10²³
Notação científica binária: -1.1001 × 2⁴
IEEE 754 armazena três componentes:
Single precision (float, 32 bits):
┌───┬──────────┬───────────────────────┐
│ S │ Expoente │ Mantissa │
│1b │ 8 bits │ 23 bits │
└───┴──────────┴───────────────────────┘
Double precision (double, 64 bits):
┌───┬───────────┬──────────────────────────────────────────┐
│ S │ Expoente │ Mantissa │
│1b │ 11 bits │ 52 bits │
└───┴───────────┴──────────────────────────────────────────┘
Componentes:
S (sinal): 0 = positivo, 1 = negativo
Expoente: em formato "biased" (com viés)
bias = 127 (float) ou 1023 (double)
expoente_real = expoente_armazenado - bias
Mantissa: parte fracionária (o "1." é implícito!)
valor = 1.mantissa × 2^(expoente-bias)
Fórmula:
(-1)^S × (1 + Mantissa) × 2^(Expoente - Bias)Exemplo — Codificar -12.625 em IEEE 754 (float)
Passo 1: Converter para binário
12 = 1100₂
0.625: 0.625 × 2 = 1.25 → 1
0.25 × 2 = 0.5 → 0
0.5 × 2 = 1.0 → 1
0.625 = 0.101₂
12.625 = 1100.101₂
Passo 2: Normalizar (formato 1.xxx × 2^n)
1100.101 = 1.100101 × 2³
Passo 3: Extrair componentes
S = 1 (negativo)
Expoente real = 3 → armazenado = 3 + 127 = 130 = 10000010₂
Mantissa = 10010100000000000000000 (23 bits, sem o "1." implícito)
Resultado (32 bits):
1 10000010 10010100000000000000000
S Expoente Mantissa
Hex: 0xC14A0000
Verificação:
(-1)¹ × (1 + 0.5 + 0.03125 + 0.015625) × 2^(130-127)
= -1 × 1.578125 × 8
= -12.625 ✓Valores Especiais do IEEE 754
Valores Especiais IEEE 754
Expoente Mantissa Valor Exemplo de uso
────────── ────────── ──────────────── ──────────────────
0 0 ±0 Zero positivo e negativo
(+0 == -0 é verdade!)
0 ≠ 0 Denormalizado Números muito próximos
(subnormal) de zero. Valor:
(-1)^S × 0.mantissa × 2^(-126)
Preenche o "gap" entre 0 e
o menor normal.
1-254 qualquer Normal Números "normais".
(float) Maioria dos valores.
255 0 ±Infinito (±∞) 1.0 / 0.0 = +∞
-1.0 / 0.0 = -∞
255 ≠ 0 NaN 0.0 / 0.0 = NaN
(Not a Number) ∞ - ∞ = NaN
sqrt(-1) = NaN
NaN ≠ NaN (NaN não é
igual a nada, nem a si!)
Intervalos (float, 32 bits):
Menor positivo normal: ~1.18 × 10⁻³⁸
Menor positivo subnormal: ~1.40 × 10⁻⁴⁵
Maior finito: ~3.40 × 10³⁸
Precisão: ~7 dígitos decimais
Intervalos (double, 64 bits):
Menor positivo normal: ~2.23 × 10⁻³⁰⁸
Maior finito: ~1.80 × 10³⁰⁸
Precisão: ~15-16 dígitos decimaisErros de Arredondamento
O fato mais importante sobre ponto flutuante: a maioria dos números reais não pode ser representada exatamente. Assim como 1/3 = 0.333... é infinito em decimal, 0.1 é infinito em binário.
Erros de Ponto Flutuante — Demonstração
# Por que 0.1 + 0.2 ≠ 0.3?
# 0.1 em binário:
# 0.1 × 2 = 0.2 → 0
# 0.2 × 2 = 0.4 → 0
# 0.4 × 2 = 0.8 → 0
# 0.8 × 2 = 1.6 → 1
# 0.6 × 2 = 1.2 → 1
# 0.2 × 2 = 0.4 → 0 ← repete!
# 0.1₁₀ = 0.000110011001100110011...₂ (infinito!)
# Com 23 bits de mantissa (float), 0.1 é arredondado:
# Armazenado: 0.100000001490116119384765625
# Erro: ~1.5 × 10⁻⁸
# Em Python/C/Java/JavaScript:
# 0.1 + 0.2 = 0.30000000000000004
# 0.1 + 0.2 == 0.3 → False!
# ═══ Consequências práticas ═══
# 1. NUNCA compare floats com ==
# Errado: if (x == 0.3) ...
# Certo: if (abs(x - 0.3) < epsilon) ...
# 2. Associatividade pode falhar:
# (a + b) + c ≠ a + (b + c) em ponto flutuante!
# Exemplo: (1e20 + -1e20) + 1.0 = 1.0
# 1e20 + (-1e20 + 1.0) = 0.0 (1.0 é absorvido!)
# 3. Cancelamento catastrófico:
# Subtrair dois números quase iguais amplifica o erro.
# Ex: 1.0000001 - 1.0000000 = 0.0000001
# Se cada um tem erro na 7ª casa, o resultado tem
# ZERO dígitos significativos corretos.
# Modos de arredondamento IEEE 754:
# Round to nearest, ties to even (default)
# Round toward +∞
# Round toward -∞
# Round toward 0 (truncate)
Dinheiro nunca em float!
Valores monetários devem ser representados em inteiros (centavos) ou usando tipos decimais de precisão arbitrária. Usar float para dinheiro causa erros de arredondamento que acumulam silenciosamente. O bug clássico: somar 10 mil transações de R$0.10 e obter R$999.97 em vez de R$1000.00.
Instruções de Ponto Flutuante no MIPS
Assembly MIPS — Ponto Flutuante
# MIPS tem um coprocessador separado para FP (Coprocessor 1)
# com 32 registradores de 32 bits: $f0-$f31
# Para double: pares de registradores ($f0/$f1, $f2/$f3, etc.)
# Instruções single precision (float):
add.s $f2, $f4, $f6 # $f2 = $f4 + $f6 (float)
sub.s $f2, $f4, $f6 # $f2 = $f4 - $f6
mul.s $f2, $f4, $f6 # $f2 = $f4 × $f6
div.s $f2, $f4, $f6 # $f2 = $f4 / $f6
# Instruções double precision:
add.d $f2, $f4, $f6 # $f2 = $f4 + $f6 (double)
sub.d $f2, $f4, $f6
mul.d $f2, $f4, $f6
div.d $f2, $f4, $f6
# Load/Store FP:
lwc1 $f2, 0($s1) # Carrega float da memória
swc1 $f2, 0($s1) # Armazena float na memória
ldc1 $f2, 0($s1) # Carrega double (2 words)
sdc1 $f2, 0($s1) # Armazena double
# Comparação e branch FP:
c.eq.s $f2, $f4 # Seta flag se $f2 == $f4
c.lt.s $f2, $f4 # Seta flag se $f2 < $f4
bc1t Label # Branch if FP flag true
bc1f Label # Branch if FP flag false
# Conversão:
cvt.s.w $f2, $f4 # int → float
cvt.d.s $f2, $f4 # float → double
cvt.w.s $f2, $f4 # float → int (trunca)No harness.os
Ponto flutuante nos ensina que toda representação tem limites de precisão — o harness.os enfrenta o mesmo desafio ao representar conhecimento: decisões são "arredondadas" para as categorias disponíveis.
Mapeamento: Ponto Flutuante → harness.os
Conceito FP Equivalente no harness.os
────────────────────────────── ────────────────────────────────────
Precisão finita (23/52 bits) Toda decisão logada perde nuance.
"rationale" é uma aproximação do
raciocínio real, assim como 0.1
em float é aproximação de 1/10.
Arredondamento Categorização: ao classificar
knowledge como "build" ou "product",
estamos arredondando — algumas
peças de conhecimento são ambas.
NaN (Not a Number) Estado indefinido: quando uma sessão
falha sem end_session, o estado
é "NaN" — nem completo nem falho.
±Infinito Contexto ilimitado: a ilusão de que
podemos carregar "tudo". Na prática,
a context window é finita como float.
0.1 + 0.2 ≠ 0.3 Composição não é transitiva: se A
implica B e B implica C, o contexto
acumulado pode divergir da conclusão
direta A→C (por perda de nuance
intermediária).
Epsilon comparison Tolerance: ao comparar estados de
projeto, usar "close enough" em vez
de igualdade exata. "80% dos testes
passam" ≈ "pronto para review".Homework
- Multiplique 1101 (13) por 1010 (10) usando o algoritmo shift-and-add manual. Mostre cada iteração com o estado do produto parcial.
- Converta o número decimal -6.75 para IEEE 754 single precision (32 bits). Mostre cada passo: conversão para binário, normalização, extração de S/Expoente/Mantissa.
- Explique por que
NaN != NaNretorna verdadeiro no IEEE 754. Qual é a motivação dessa decisão de design? - Em Python ou C, demonstre o problema da associatividade: encontre valores de a, b e c onde
(a + b) + cproduz resultado diferente dea + (b + c). - Por que MIPS usa um coprocessador separado para ponto flutuante em vez de integrar as operações na ULA principal?
Resumo
- Multiplicação binária: shift-and-add; N bits x N bits = 2N bits de resultado (HI:LO no MIPS)
- Divisão: restoring division, muito mais lenta que multiplicação (~32 ciclos vs ~3-5)
- IEEE 754: sinal (1 bit) + expoente com bias (8/11 bits) + mantissa com "1." implícito (23/52 bits)
- Valores especiais: +0/-0, denormalizados, infinito, NaN
- Erros de arredondamento: 0.1 + 0.2 != 0.3; nunca compare floats com ==; nunca use float para dinheiro
- MIPS FP: coprocessador 1 com registradores $f0-$f31; instruções .s (single) e .d (double)
Verifique seu entendimento
No formato IEEE 754 single precision, quantos bits são usados para a mantissa e qual é o bias do expoente?