2.1.4 Exercício Estendido: Aritmética de Intervalos

Alyssa P. Hacker está projetando um sistema para ajudar pessoas a resolver problemas de engenharia. Um recurso que ela quer fornecer em seu sistema é a capacidade de manipular quantidades inexatas (como parâmetros medidos de dispositivos físicos) com precisão conhecida, de modo que quando os cálculos são feitos com tais quantidades aproximadas, os resultados serão números de precisão conhecida.

Engenheiros elétricos usarão o sistema de Alyssa para calcular quantidades elétricas. Às vezes é necessário para eles calcular o valor de uma resistência equivalente paralela Rp de dois resistores R1 e R2 usando a fórmula:

R_{p} = \dfrac{1}{1/R_{1}+1/R_{2}}

Os valores de resistência geralmente são conhecidos apenas até alguma tolerância garantida pelo fabricante do resistor. Por exemplo, se você comprar um resistor rotulado "6.8 ohms com 10% de tolerância", você só pode ter certeza de que o resistor tem uma resistência entre 6.12 e 7.48 ohms. Assim, se você tiver um resistor de 6.8 ohms com 10% de tolerância em paralelo com um resistor de 4.7 ohms com 5% de tolerância, a resistência da combinação pode variar de cerca de 2.58 ohms (se os dois resistores estiverem nos limites inferiores) a cerca de 2.97 ohms (se os dois resistores estiverem nos limites superiores).

A ideia de Alyssa é implementar "aritmética de intervalos" como um conjunto de operações aritméticas para combinar "intervalos" (objetos que representam o intervalo de valores possíveis de uma quantidade inexata). O resultado de adicionar, subtrair, multiplicar ou dividir dois intervalos é em si um intervalo, representando o intervalo do resultado.

Alyssa postula a existência de um objeto abstrato chamado "intervalo" que tem dois pontos extremos: um limite inferior e um limite superior. Ela também presume que, dados os pontos extremos de um intervalo, ela pode construir o intervalo usando o construtor de dados make_interval. Alyssa primeiro escreve uma função para adicionar dois intervalos. Ela raciocina que o valor mínimo que a soma poderia ser é a soma dos dois limites inferiores e o valor máximo que poderia ser é a soma dos dois limites superiores:

Exemplo de Código

1function make_interval(x, y) {
2  return pair(x, y);
3}
4function lower_bound(i) {
5  return head(i);
6}
7function upper_bound(i) {
8  return tail(i);
9}
10
11function add_interval(x, y) {
12  return make_interval(lower_bound(x) + lower_bound(y),
13                       upper_bound(x) + upper_bound(y));
14}
15
16// Testando
17const i1 = make_interval(2, 4);
18const i2 = make_interval(1, 3);
19const i3 = add_interval(i1, i2);
20
21lower_bound(i3); // deve ser 3
22upper_bound(i3); // deve ser 7

function make_interval(x, y) {
  return pair(x, y);
}
function lower_bound(i) {
  return head(i);
}
function upper_bound(i) {
  return tail(i);
}

function add_interval(x, y) {
  return make_interval(lower_bound(x) + lower_bound(y),
                       upper_bound(x) + upper_bound(y));
}

// Testando
const i1 = make_interval(2, 4);
const i2 = make_interval(1, 3);
const i3 = add_interval(i1, i2);

lower_bound(i3); // deve ser 3
upper_bound(i3); // deve ser 7

Código editável · Ctrl+Enter executa · Esc solta o foco

Alyssa também calcula o produto de dois intervalos encontrando o mínimo e o máximo dos produtos dos limites e usando-os como os limites do intervalo resultante:

Exemplo de Código

1function make_interval(x, y) { return pair(x, y); }
2function lower_bound(i) { return head(i); }
3function upper_bound(i) { return tail(i); }
4
5function mul_interval(x, y) {
6  const p1 = lower_bound(x) * lower_bound(y);
7  const p2 = lower_bound(x) * upper_bound(y);
8  const p3 = upper_bound(x) * lower_bound(y);
9  const p4 = upper_bound(x) * upper_bound(y);
10  return make_interval(math_min(p1, p2, p3, p4),
11                       math_max(p1, p2, p3, p4));
12}

function make_interval(x, y) { return pair(x, y); }
function lower_bound(i) { return head(i); }
function upper_bound(i) { return tail(i); }

function mul_interval(x, y) {
  const p1 = lower_bound(x) * lower_bound(y);
  const p2 = lower_bound(x) * upper_bound(y);
  const p3 = upper_bound(x) * lower_bound(y);
  const p4 = upper_bound(x) * upper_bound(y);
  return make_interval(math_min(p1, p2, p3, p4),
                       math_max(p1, p2, p3, p4));
}

Código editável · Ctrl+Enter executa · Esc solta o foco

Para dividir dois intervalos, Alyssa multiplica o primeiro pelo recíproco do segundo. Observe que os limites do intervalo recíproco são o recíproco do limite superior e o recíproco do limite inferior, nessa ordem:

Exemplo de Código

1function div_interval(x, y) {
2  return mul_interval(x, make_interval(1 / upper_bound(y),
3                                       1 / lower_bound(y)));
4}

function div_interval(x, y) {
  return mul_interval(x, make_interval(1 / upper_bound(y),
                                       1 / lower_bound(y)));
}

Código editável · Ctrl+Enter executa · Esc solta o foco

Exercício 2.7

O programa de Alyssa está incompleto porque ela não especificou a implementação da abstração de intervalo. Defina os seletores upper_bound e lower_bound para completar a implementação.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Com make_interval construindo o par na ordem (inferior, superior), os seletores são diretos:

function lower_bound(i) {
    return head(i);
}
function upper_bound(i) {
    return tail(i);
}

(Se quiséssemos aceitar argumentos em qualquer ordem, bastaria math_min/math_max dos dois componentes — mas a convenção do construtor torna isso desnecessário.)

Resolvi o exercício 2.7

Exercício 2.8

Usando um raciocínio análogo ao de Alyssa, descreva como a diferença de dois intervalos pode ser calculada. Defina uma função correspondente chamada sub_interval.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Raciocínio. O menor valor da diferença $x - y$ ocorre com o menor $x$ e o maior $y$ ; o maior, com o maior $x$ e o menor $y$ :

Exemplo de Código

function sub_interval(x, y) {
  return make_interval(lower_bound(x) - upper_bound(y),
                       upper_bound(x) - lower_bound(y));
}

print_interval(sub_interval(make_interval(5, 10),
                          make_interval(1, 2)));

function sub_interval(x, y) {
  return make_interval(lower_bound(x) - upper_bound(y),
                       upper_bound(x) - lower_bound(y));
}

print_interval(sub_interval(make_interval(5, 10),
                          make_interval(1, 2)));

Código editável · Ctrl+Enter executa · Esc solta o foco

Equivalente a somar com o intervalo negado $[-u_y, -l_y]$ — repare a troca dos extremos, o detalhe de que o exercício trata.

Resolvi o exercício 2.8

Exercício 2.9

A largura de um intervalo é metade da diferença entre seus limites superior e inferior. A largura é uma medida da incerteza do número especificado pelo intervalo. Para algumas operações aritméticas, a largura do resultado de combinar dois intervalos é uma função apenas das larguras dos intervalos argumentos, enquanto para outras a largura do intervalo resultado da combinação não é uma função das larguras dos intervalos argumentos. Mostre que a largura da soma (ou diferença) de dois intervalos é uma função apenas das larguras dos intervalos sendo adicionados (ou subtraídos). Dê exemplos para mostrar que isso não é verdadeiro para multiplicação ou divisão.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Soma: com $x = [l_x, u_x]$ , $y = [l_y, u_y]$ ,

$w(x + y) = \frac{(u_x + u_y) - (l_x + l_y)}{2} = \frac{u_x - l_x}{2} + \frac{u_y - l_y}{2} = w(x) + w(y)$

e a subtração é idêntica (os extremos trocados não mudam a diferença). A largura do resultado depende só das larguras.

Multiplicação não: dois pares de intervalos com as mesmas larguras produzem larguras de produto diferentes —

Exemplo de Código

function width(i) {
  return (upper_bound(i) - lower_bound(i)) / 2;
}

// mesmas larguras (1 e 1), produtos com larguras diferentes:
display(width(mul_interval(make_interval(0, 2),
                         make_interval(0, 2))));
width(mul_interval(make_interval(4, 6),
                 make_interval(4, 6)));

function width(i) {
  return (upper_bound(i) - lower_bound(i)) / 2;
}

// mesmas larguras (1 e 1), produtos com larguras diferentes:
display(width(mul_interval(make_interval(0, 2),
                         make_interval(0, 2))));
width(mul_interval(make_interval(4, 6),
                 make_interval(4, 6)));

Código editável · Ctrl+Enter executa · Esc solta o foco

$[0,2] \times [0,2] = [0,4]$ tem largura 2, enquanto $[4,6] \times [4,6] = [16,36]$ tem largura 10 — larguras de entrada iguais, saídas diferentes. Logo a largura do produto (e da divisão, que multiplica pelo recíproco) depende também da posição dos intervalos, não apenas das larguras.

Resolvi o exercício 2.9

Exercício 2.10

Ben Bitdiddle, um especialista programador, observa que não faz sentido dividir por um intervalo que abrange zero. Modifique o código de Alyssa para verificar essa condição e sinalizar um erro se isso ocorrer.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Um intervalo "atravessa zero" quando $l \le 0 \le u$ — dividir por ele não faz sentido (o recíproco explode):

Exemplo de Código

function div_interval(x, y) {
  return lower_bound(y) <= 0 && upper_bound(y) >= 0
         ? error("intervalo do divisor atravessa zero -- div_interval")
         : mul_interval(x, make_interval(1 / upper_bound(y),
                                         1 / lower_bound(y)));
}

print_interval(div_interval(make_interval(1, 2),
                          make_interval(4, 5)));
div_interval(make_interval(1, 2), make_interval(-1, 1));

function div_interval(x, y) {
  return lower_bound(y) <= 0 && upper_bound(y) >= 0
         ? error("intervalo do divisor atravessa zero -- div_interval")
         : mul_interval(x, make_interval(1 / upper_bound(y),
                                         1 / lower_bound(y)));
}

print_interval(div_interval(make_interval(1, 2),
                          make_interval(4, 5)));
div_interval(make_interval(1, 2), make_interval(-1, 1));

Código editável · Ctrl+Enter executa · Esc solta o foco

A segunda chamada dispara o erro — execute e veja.

Resolvi o exercício 2.10

Exercício 2.11

Em passando por esse código, Ben também observa que é possível melhorar a eficiência de mul_interval usando o fato de que os pontos extremos dos intervalos são números. Mostre que existem nove casos para computar o produto de dois intervalos com base nos sinais dos pontos extremos, e reescreva mul_interval para levar vantagem disso.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Cada extremo pode ser negativo ou não-negativo; classificando os dois intervalos pelos sinais de $(l, u)$ há $3 \times 3 = 9$ combinações — e em oito delas os extremos do produto são conhecidos de antemão. Só quando ambos atravessam zero é preciso comparar produtos:

Exemplo de Código

function mul_interval(x, y) {
  const xl = lower_bound(x);
  const xu = upper_bound(x);
  const yl = lower_bound(y);
  const yu = upper_bound(y);
  return xl >= 0
         ? yl >= 0
           ? make_interval(xl * yl, xu * yu)
           : yu <= 0
           ? make_interval(xu * yl, xl * yu)
           : make_interval(xu * yl, xu * yu)
         : xu <= 0
         ? yl >= 0
           ? make_interval(xl * yu, xu * yl)
           : yu <= 0
           ? make_interval(xu * yu, xl * yl)
           : make_interval(xl * yu, xl * yl)
         : yl >= 0
         ? make_interval(xl * yu, xu * yu)
         : yu <= 0
         ? make_interval(xu * yl, xl * yl)
         : make_interval(math_min(xl * yu, xu * yl),
                         math_max(xl * yl, xu * yu));
}

print_interval(mul_interval(make_interval(-2, 3),
                          make_interval(-4, 5)));
print_interval(mul_interval(make_interval(2, 3),
                          make_interval(-5, -4)));
"nove casos, duas multiplicações em oito deles";

function mul_interval(x, y) {
  const xl = lower_bound(x);
  const xu = upper_bound(x);
  const yl = lower_bound(y);
  const yu = upper_bound(y);
  return xl >= 0
         ? yl >= 0
           ? make_interval(xl * yl, xu * yu)
           : yu <= 0
           ? make_interval(xu * yl, xl * yu)
           : make_interval(xu * yl, xu * yu)
         : xu <= 0
         ? yl >= 0
           ? make_interval(xl * yu, xu * yl)
           : yu <= 0
           ? make_interval(xu * yu, xl * yl)
           : make_interval(xl * yu, xl * yl)
         : yl >= 0
         ? make_interval(xl * yu, xu * yu)
         : yu <= 0
         ? make_interval(xu * yl, xl * yl)
         : make_interval(math_min(xl * yu, xu * yl),
                         math_max(xl * yl, xu * yu));
}

print_interval(mul_interval(make_interval(-2, 3),
                          make_interval(-4, 5)));
print_interval(mul_interval(make_interval(2, 3),
                          make_interval(-5, -4)));
"nove casos, duas multiplicações em oito deles";

Código editável · Ctrl+Enter executa · Esc solta o foco

Se vale a pena? Ben ganharia duas multiplicações ao custo de uma pirâmide de testes — o próprio livro sugere ceticismo com "otimizações" assim.

Resolvi o exercício 2.11

Exercício 2.12

Defina um construtor make_center_percent que recebe um centro e uma tolerância percentual e produz o intervalo desejado. Você também deve definir um seletor percent que produz a tolerância percentual para um dado intervalo.

Exemplo de Código

1function make_center_width(c, w) {
2  return make_interval(c - w, c + w);
3}
4function center(i) {
5  return (lower_bound(i) + upper_bound(i)) / 2;
6}
7function width(i) {
8  return (upper_bound(i) - lower_bound(i)) / 2;
9}
10
11function make_center_percent(c, p) {
12  // Sua implementação aqui
13  // p é a tolerância percentual
14}
15
16function percent(i) {
17  // Sua implementação aqui
18}

function make_center_width(c, w) {
  return make_interval(c - w, c + w);
}
function center(i) {
  return (lower_bound(i) + upper_bound(i)) / 2;
}
function width(i) {
  return (upper_bound(i) - lower_bound(i)) / 2;
}

function make_center_percent(c, p) {
  // Sua implementação aqui
  // p é a tolerância percentual
}

function percent(i) {
  // Sua implementação aqui
}

Código editável · Ctrl+Enter executa · Esc solta o foco

O Problema da Dependência

Ao explorar mais profundamente o sistema, você descobrirá que diferentes expressões algébricas que são matematicamente equivalentes podem produzir intervalos de resultados diferentes quando implementadas na aritmética de intervalos. Por exemplo, duas fórmulas para calcular resistências paralelas:

function par1(r1, r2) {
    return div_interval(mul_interval(r1, r2),
                       add_interval(r1, r2));
}

function par2(r1, r2) {
    const one = make_interval(1, 1);
    return div_interval(one,
                       add_interval(div_interval(one, r1),
                                   div_interval(one, r2)));
}

Essas duas funções produzem resultados diferentes! Isso ocorre porque a aritmética de intervalos trata cada ocorrência de uma variável como uma quantidade independente, levando a resultados mais imprecisos quando uma variável aparece várias vezes em uma expressão. Este é o problema da dependência na aritmética de intervalos.

Exercícios 2.13-2.16

Os exercícios restantes exploram mais profundamente este problema da dependência, derivando fórmulas para tolerância percentual em produtos, investigando por que par2 produz resultados melhores que par1, e explorando se é possível projetar um sistema de aritmética de intervalos que evite completamente esse problema.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Exemplo de Código

function make_center_width(c, w) {
  return make_interval(c - w, c + w);
}
function center(i) {
  return (lower_bound(i) + upper_bound(i)) / 2;
}
function width(i) {
  return (upper_bound(i) - lower_bound(i)) / 2;
}

function make_center_percent(c, p) {
  return make_center_width(c, c * p / 100);
}
function percent(i) {
  return width(i) / center(i) * 100;
}

const r = make_center_percent(6.8, 10);
print_interval(r);
display(center(r));
percent(r);

function make_center_width(c, w) {
  return make_interval(c - w, c + w);
}
function center(i) {
  return (lower_bound(i) + upper_bound(i)) / 2;
}
function width(i) {
  return (upper_bound(i) - lower_bound(i)) / 2;
}

function make_center_percent(c, p) {
  return make_center_width(c, c * p / 100);
}
function percent(i) {
  return width(i) / center(i) * 100;
}

const r = make_center_percent(6.8, 10);
print_interval(r);
display(center(r));
percent(r);

Código editável · Ctrl+Enter executa · Esc solta o foco

A tolerância percentual é só a largura relativa ao centro; os resistores de "6,8 kΩ com 10%" do texto viram [6.12, 7.48]. (Para centros negativos seria preciso um math_abs no percent — os resistores do livro, felizmente, são positivos.)

Resolvi o exercício 2.12

📝 Encontrou algo errado nesta página?

Sua ajuda é muito importante para melhorar a qualidade da tradução!

🐛 Encontrou um erro?

Se você encontrou:

Erro de tradução (palavra incorreta, termo técnico errado)
Erro de ortografia ou gramática
Link quebrado
Código de exemplo que não funciona
Problema de formatação

Reporte um bug →

❓ Tem uma dúvida?

Se você tem:

Dúvida sobre o conteúdo desta seção
Pergunta sobre um conceito do SICP
Dificuldade em entender algum exemplo
Questão sobre a tradução de algum termo

Inicie uma discussão →

💡 Tem uma sugestão de melhoria?

Se você quer sugerir:

Melhoria na explicação
Exemplo adicional
Recurso visual (diagrama, ilustração)
Qualquer outra ideia

Sugira uma melhoria →

🌍 Quer discutir a tradução?

Se você quer debater:

Escolha de tradução de algum termo
Consistência de terminologia
Nuances do português

Discussão de tradução →

Exercício 2.7​

Exercício 2.8​

Exercício 2.9​

Exercício 2.10​

Exercício 2.11​

Exercício 2.12​

O Problema da Dependência​

Exercícios 2.13-2.16​

📝 Encontrou algo errado nesta página?

🐛 Encontrou um erro?

❓ Tem uma dúvida?

💡 Tem uma sugestão de melhoria?

🌍 Quer discutir a tradução?

Exercício 2.7

Exercício 2.8

Exercício 2.9

Exercício 2.10

Exercício 2.11

Exercício 2.12

O Problema da Dependência

Exercícios 2.13-2.16