.. -*- coding: utf-8 -*- 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*. Tópicos ------- - Números harmônicos - Representação de frações - abstração de dados e programação orientada a objetos Introdução ---------- O **número harmônico** :math:`H_n` de ordem :math:`n`, :math:`n > 0`, é o valors da soma: .. math:: H_n = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{n} .. admonition:: 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 :math:`n` e calculam e retornam o valor de :math:`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 :math:`1/n` ao termo :math:`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 :math:`1/1` ao termo :math:`1/n`. Vamos começar escrevendo a função ``Hmaior()``, logo a seguir. Execute o trecho de código abaixo e confira o resultado. .. raw:: html .. code:: Python def Hmaior(n): ''' (int) -> float Recebe um inteiro positivo e retorna o número harmônico de ordem n. O harmônico é calculado somando os termos do maior para o menor. ''' soma = 0 for i in range (1, n+1): soma += 1 / i return soma # testes print(f"Hmaior( 2) = {Hmaior( 2)}") print(f"Hmaior( 5) = {Hmaior( 5)}") print(f"Hmaior(10) = {Hmaior(10)}") print(f"Hmaior(15) = {Hmaior(15)}") 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 é :math:`1/n`, até o maior termo, que é :math:`1/1`. Se necessário, consulte a `documentação da função range() `__. .. raw:: html .. code:: Python def Hmenor(n): ''' (int) -> float Recebe um inteiro positivo e retorna o número harmônico de ordem n. O número harmônico é calculado somando os termos do menor para o maior. ''' soma = 0 for i in range (n, ?, ?): # completar soma += 1/i return soma # testes print(f"Hmenor( 2) = {Hmenor( 2)}") print(f"Hmenor( 5) = {Hmenor( 5)}") print(f"Hmenor(10) = {Hmenor(10)}") print(f"Hmenor(15) = {Hmenor(15)}") 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``. .. Observe que para :math:`n = 10`, os resultados são iguais, mas para :math:`n = 15 \ldots` .. admonition:: 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 :math:`0` e :math:`1`. Ao escrevermos ``0.123`` na base 10 estamos escrevendo o valor da soma :math:`1 \times 10^{-1} + 2 \times 10^{-2} + 2 \times 10^{-3}` Um valor como ``1/10 = 0.1`` é o número :math:`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 .. code-block:: python 0.0001100110011001100110011001100110011 ou seja, na base binária ``1/10`` é .. math:: 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()``: .. code-block:: python 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. .. admonition:: 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 :math:`1/n` ao termo :math:`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 :math:`1/2 + 2/3` por :math:`5/6`, ao invés de fazermos :math:`0.5 + 0.66666\ldots` e obtermos :math:`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 :math:`2/3` em ponto flutuante com 6 dígitos decimais obtemos :math:`0.666667` ao arrendondar o último dígito para 7 ou :math:`0.666666` truncando no último dígito. 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 .. code-block:: python 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: .. code-block:: python 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. .. code-block:: python ''' 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() Exercícios ---------- #. Escreva a função de protótipo .. code-block:: python 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 #. Escreva a função de protóripo .. code-block:: python 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 #. 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. .. Agora complete esse programa escrevendo o corpo da função ``Hmenor_frac()`` e os testes para essa função, para ver se há diferença entre as somas da direita para a esquerda e da esquerda para a direita usando frações. .. deixar para a atividade presencial admonition:: Dica O Python consegue trabalhar com números inteiros muito grandes, mas é muito difícil de se ver o resultado. Modifique a função `soma_frações` para que ela calcule o MDC entre `num` e `den` e retorne um racional simplificado (= *irredutível*). 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. Para saber mais --------------- * `Introdução à Computação com Python: um curso interativo `__. * `Como Pensar como um Cientista da Computação - Aprendendo com Python: Edição interativa `__ * `Tutorial de POO em Python `__. .. aula presencial * incluir a função mdc para retornar frações irredutíveis