5. Números harmônicos

Aqui os números harmônicos serão o nosso pretexto para considerarmos duas questões. A primeira questão diz respeito a representação aproximada de frações (como números reais) feita pelos computadores. A segunda questão é motivacional. A representação de frações nos guiará na prática da abstração de dados materializada na programação orientada a objetos.

5.1. Tópicos

  • Números harmônicos
  • Representação de frações
  • abstração de dados e programação orientada a objetos

5.2. Introdução

O número harmônico \(H_n\) de ordem \(n\), \(n > 0\), é o valors da soma:

\[H_n = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{n}\]

A ordem em que as adições são realizadas pelo computador podem alterar o resultado?

Será que faz diferença as adições serem feitas da esquerda para a direita (ED) ou da direita para a esquerda (DE)? Essa pergunta não faz muito sentido do ponto de vista matemático já que adição é associativa. Entretanto os números reais, em particular frações, são representados em computadores de forma aproximada através de coisas do tipo float. O acúmulo dessas aproximações por adições pode causar desvios cada vez maiores nos resultados.

Para investigar essa questão envolvendo aproximações, vamos escrever duas funções que, operando de maneiras diferentes, recebem \(n\) e calculam e retornam o valor de \(H_n\):

  • Hmenor(): calcula a soma realizando adições a partir do menor termo do somatório até o maior, da direita para a esquerda na expressão acima, adicionando os menores termos primeiro, ou seja, do termo \(1/n\) ao termo \(1/1\); e
  • Hmaior(): calcula a soma realizando adições a partir do maior termo da somatória até o menor, da esquerda para a direita na expressão, adicionando os maiores primeiro, ou seja, do termo \(1/1\) ao termo \(1/n\).

Vamos começar escrevendo a função Hmaior(), logo a seguir. Execute o trecho de código abaixo e confira o resultado.

Agora edite o trecho de código a seguir, substituindo os trechos com ? por valores adequados, completando a chamada da função range() para calcular a soma a partir do menor termo, que é \(1/n\), até o maior termo, que é \(1/1\). Se necessário, consulte a documentação da função range().

Caso você sinta dificuldade em expressar a sua solução com o comando de repetição for, tente expressá-la usando o while. Ou melhor, faça isso mesmo que você não tenha dificuldade em utilizar o comando for.

Aritmética de ponto flutuante (Floating Point Arithmetic: Issues and Limitations)

Em Python um int é um tipo nativo que representa números inteiros potencialmente ilimitados.

Representação de erros se refere ao fato de que muitas frações, muitas mesmo, não podem ser representadas exatamente como números binários (= base 2). Está é a razão principal para Python, Perl, C, C++, Java, Fortran e muitas outras linguagens não exibirem os números que esperamos.

Um valor como 1/10 = 0.1 é representado aproximadamente no computador e não exatamente, como inicialmente poderíamos imaginar. Em computadores todos os números são representados em binário e portanto usam apenas os algarismos \(0\) e \(1\).

Ao escrevermos 0.123 na base 10 estamos escrevendo o valor da soma \(1 \times 10^{-1} + 2 \times 10^{-2} + 2 \times 10^{-3}\) Um valor como 1/10 = 0.1 é o número \(1 \times 10^{-1}\). Surpreendentemente, na base binária, conseguimos apenas um representação aproximada de 1/10 já que este valor é uma dízima periódica. Essa é a mesma coisa que ocorre quando representamos 1/3 na base 10 e obtemos a dízima 0.3333.... Na base binária 1/10 é escrito como

0.0001100110011001100110011001100110011

ou seja, na base binária 1/10 é

\[0 \times 2^{-1} + 0 \times 2^{-2} + 0 \times 2^{-3} + 1 \times 2^{-4} + 1 \times 2^{-5} + 0 \times 2^{-6} + 0 \times 2^{-7} + 1 \times 2^{-8} + 1 \times 2^{-9} + \cdots\]

Em Python podemos mudar a representação de um número de float para a razão de dois números inteiros utilizando o método as_integer_ratio():

Python 3.4.3 (default, Mar 26 2015, 22:03:40)
[GCC 4.9.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> x = 1/10
>>> x.as_integer_ratio()
(3602879701896397, 36028797018963968)
>>> x
0.1
>>> x = 1/10 # internamente, a representação desse valor é aproximada
>>> x.as_integer_ratio() # retorna numerador e denominador
(3602879701896397, 36028797018963968)
>>> 3602879701896397/36028797018963968 # razão
0.1
>>> numerador, denominador = x.as_integer_ratio()
>>> numerador
3602879701896397
>>> denominador
36028797018963968
>>> numerador/denominador
0.1
>>> y = 3.1415
>>> numerador_y, denominador_y = y.as_integer_ratio()
>>> numerador_y
7074029114692207
>>> denominador_y
2251799813685248
>>> numerador_y / denominador_y
3.1415
>>>

Complicado? Bem, está disciplina não tratará desses disso. Tópicos como esse são centrais em disciplinas como Análise Numérica e Cálculo Numérico que estudam a instabilidade numérica de algoritmos que são aproximações calculadas por programas. Apesar dos resultados serem aproximados há técnica que permitem que foguetes lançados à Lua não terminem no Sol, ou coisas do gênero.

Qual função é mais precisa, Hmaior() ou Hmenor()?

Em Cálculo Numérico aprendemos que, a razão da diferença é que ambas as somas são aproximadas mas, ao somar os números “grandes” primeiro, a precisão da soma devido a grande quantidade de números “pequenos” é perdida. Portanto o resultado de Hmenor(), que faz as adições do termo \(1/n\) ao termo \(1/1\), é mais preciso que da soma calculada por Hmaior().

Será possível obter um resultado ainda mais preciso para o cálculo de um número harmônico? Uma possível solução para melhorar a precisão é evitar o uso de ponto flutuante e usar uma outra representação numérica, que será o tópico das próximas atividades.

Uma idéia é eliminar, ou evitar quando for possível, as aproximações considerando representado cada fração da soma através de dois números inteiros, o seu numerador e seu denominador.

A partir dai, podemos realizar todas as operações com frações manipulando os seus numeradores e denominadores. Por exemplo, representaríamos o resultado de \(1/2 + 2/3\) por \(5/6\), ao invés de fazermos \(0.5 + 0.66666\ldots\) e obtermos \(1.16666\ldots\). Observe que a representação de frações através dos seus numeradores e denominatores é exata, não há aproximação já que todos os valores envolvidos são inteiros. Quando utilizamos ponto flutuante criamos um erro ao limitar o número de digitos. Por exemplo, ao representarmos \(2/3\) em ponto flutuante com 6 dígitos decimais obtemos \(0.666667\) ao arrendondar o último dígito para 7 ou \(0.666666\) truncando no último dígito.

5.3. Cálculo de números harmônicos com frações

Antes de partimos para a definição de classes e criação de objetos, faremos um passo intermediário usando funções. No cálculo de números harmônicos utilizaremos a representação racional de números, em vez da representação com ponto flutuante, valores do tipo float.

Podemos representar uma fração como um par números inteiros. Assim, 1/10 e 3/4 serão representado como (1,10) e (3,4). O primeiro inteiro do par representa o numerador e o segundo o denominador da fração.

Vamos começar tentando imaginar uma função Hmaior_frac() que calcula a soma de 1/1 a 1/n usando uma função que soma frações, ao invés de somar reais.

Ao fazer isso, estamos aplicando o nosso velho método de decompor o problema em problemas mais simples. Podemos agora tentar imaginar que temos uma função de protótipo

def some_fracoes(num1, den1, num2, den2):
    ''' (int, int, int, int) -> int, int

    RECEBE quatro inteiros num1, den1, num2 e den2 representando
        as frações num1/den1 e num2/den2.
    RETORNA um par (num,den) que representa a soma dessas frações.

    PRÉ-CONDIÇÃO: a função supõe que os dois denominadores não
    são nulos.
    '''

    # você vai desenvolver essa função nos exercícios :-)
    return 0, 1

Se tivéssemos a função some_fracoes() a nossa disposição, poderíamos implementar a função Hmaior_frac() da seguinte forma:

def Hmaior_frac( n ):
    ''' (int) -> int, int

    RECEBE um número inteiro positivo n.
    RETORNA o número harmônico de ordem n. O número harmônico é
        calculado somando do maior para o menor termo.
    '''
    num, den = 0, 1 # numerador 0 e denominador 1
    for i in range (1, n+1):
        num, den = some_fracoes (num, den, 1, i)
    return num, den

O programa abaixo ilustra um programa main() feito para testar a função Hmaior_frac(), baseado no esqueleto adotado nesse curso.

'''
    Programa para teste das funções Hmaior() e soma_fracoes()
'''

def main():
    lista_n = [1, 2, 3, 5, 10, 15]

    for n in lista_n:
        num, den = Hmaior_frac(n)
        print(f"Hmaior_frac({n}) = {num}/{den} = {num/den}")

    print("Fim dos testes.")

# coloque aqui a definição da função Hmaior_frac( n ):

# seguida da definição da função some_fracoes()

# chama a função main()
if __name__ == '__main__':
    main()

5.4. Exercícios

  1. Escreva a função de protótipo

    def some_fracoes(num1, den1, num2, den2):
    ''' (int, int, int, int) -> int, int

    RECEBE quatro inteiros num1, den1, num2 e den2 representando
        as frações num1/den1 e num2/den2.
    RETORNA um par (num,den) que representa a soma dessas frações.

    PRÉ-CONDIÇÃO: a função supõe que os dois denominadores não
        são nulos.
    '''
    # escreva o código dessa função
    num, den = 0, 1
    return num, den

  2. Escreva a função de protóripo

    def Hmenor_frac( n ):
    ''' (int) -> int, int

    RECEBE um número inteiro positivo.
    RETORNA o número harmônico de ordem n. O número harmônico
        é calculado somando do menor para o maior termo.
    '''
    # escreva o código dessa função
    return 0, 1

# inclua também testes para a funcao Hmenor_frac

  3. Escreva um programa que lê um inteiro n e, para cada número k no intervalo de 1 a n, verifica que os valores de Hmenor_frac(k) são os mesmos das função Hmaior_frac(k). Seu programa deve imprimir os valore de k e os números retornados pelas função apenas quando os resultados forem distintos.

5.5. Onde estamos e para onde vamos?

Continuamos a revisar um pouco de Python com relação ao comportamento do Python com relação às operações com números reais. Esse comportamento, aliás, não é apenas do Python, mas da representação de reais usando ponto flutuante.

Vimos que o uso de frações pode eliminar o problema de acúmulo de erros de quantização devido à limitada capacidade de representação de números reais usando o tipo float. Vimos que o uso de frações usando um par de números inteiros, ou seja, um numerador e um denominados, nos permite representar e adicionar frações de forma exata, sem acumular erros.

No próximo passeio vamos ver como criar um tipo abstrato de dados capaz de manipular, fazer operações, com frações.