.. -*- 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