Números gigantes

[Diego Rocha]

Pessoal,

Fiz um trabalho da faculdade (calma que eu não quero ajuda no trabalho, só estou contextualizando), onde o professor pediu para implementar um algoritmo recursivo de fatorial e calcular a saída até 100 em qualquer linguagem. 

Pensei logo: "Vou implementar em Python e ver como a linguagem se comporta".
Eu imaginava que assim como Pascal e C eu fosse ter problemas quando os resultados estourassem o tamanho máximo do inteiro.

Mas pra minha surpresa, eu percebi que Python lida muito bem números gigantes, o fatorial de 100 (93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000) tem 158 dígitos, pelos meus cálculos (do WolframAlpha na verdade) são necessários  525 bits para armazenar esse número.

Comecei a me perguntar como Python lida com números desse tamanho e qual seria o máximo possível.
Achei o sys.maxint, mas ele exibe um número bem pequeno, menor que o fatorial de 30 e o sistema calculou até 100 e corretamente!

Então, gostaria de saber se alguém aqui sabe como Python lida com esses números gigantes e qual seria (se existe) o máximo.

Atenciosamente,

Diego Rocha

[Douglas Camata]

Python vai conseguir responder até o fatorial de 1000 ou 10000, só vai demorar um pouco. Eu acho que tem relação com o fato da linguagem ser interpretada. Já leu sobre o módulo decimal? Usei ele para trabalhos de cálculo numérico e ele faz um trabalho semelhante com relação à precisão, ignorando completamente o erro introduzido pela representação de ponto flutuante em binário, genial.

2012/11/21 Diego Rocha <di...@diegorocha.com.br>

--
------------------------------------
Grupo Python-Brasil
http://www.python.org.br/wiki/AntesDePerguntar
 
<*> Para visitar o site do grupo na web, acesse:
http://groups.google.com/group/python-brasil
 
<*> Para sair deste grupo, envie um e-mail para:
python-brasi...@googlegroups.com

--
Douglas Camata
Graduando em Ciência da Computação (UENF)

Blog: http://douglascamata.net

Github: http://github.com/douglascamata

Twitter: @douglascamata

Skype: douglas_camata

-----------------------------------
Linux User #509211

[Christian S. Perone]

Diego, o interpretador utiliza um "long" primitivo do C para representar números inteiros (int), mas antes de acontecer um overflow no int ele promove esse tipo para "long" (do Python), o long é representado internamente em software e não é mapeado para um tipo primitivo do C, a vantagem é que isto fica transparente para o usuário e o long acaba ganhando um limite virtualmente ilimitado (virtualmente porque depende dos recursos de hardware), mas obviamente que esta representação tem um custo de manuseio bem maior do que quando você utiliza tipos primitivos. É semelhando ao uso da gmplib em C, só que de forma implícita e transparente.

PS: No Python 3k houve uma unificação entre int/long (http://docs.python.org/3.0/whatsnew/3.0.html#integers).

2012/11/27 Douglas Camata <d.ca...@gmail.com>

--
"Forgive, O Lord, my little jokes on Thee, and I'll forgive Thy great big joke on me."
http://pyevolve.sourceforge.net/wordpress/

[Antonio Ribeiro]

Já que a pergunta foi respondida, momento curiosidade inútil: o 50.000.000-ésimo número da sequência de Fibonacci, calculado com Python: https://github.com/alvesjnr/alvesjnr.github.com/raw/master/50000000

2012/11/27 Christian S. Perone <christia...@gmail.com>

--
Atenciosamente,

Antonio Ribeiro

Skype: alvesjnr

Twitter: http://twitter.com/alvesjnr

Blog: http://assemblando.wordpress.com

[Mario Domenech Goulart]

Alô Diego,

On Wed, 21 Nov 2012 01:14:01 -0200 Diego Rocha <di...@diegorocha.com.br> wrote:

> Fiz um trabalho da faculdade (calma que eu não quero ajuda no
> trabalho, só estou contextualizando), onde o professor pediu para
> implementar um algoritmo recursivo de fatorial e calcular a saída até
> 100 em qualquer linguagem. 
> Pensei logo: "Vou implementar em Python e ver como a linguagem se
> comporta".
> Eu imaginava que assim como Pascal e C eu fosse ter problemas quando
> os resultados estourassem o tamanho máximo do inteiro.

Outro aspecto a levar em consideração é o limite de profundidade de
recursão:
http://docs.python.org/2/library/sys.html#sys.getrecursionlimit

No Python 2.6.6 que tenho aqui, o limite é 1000, então só vais conseguir
calcular fatorial de números até 999 com um algoritmo recursivo se não
alterares a configuração padrão (o que, suponho, não deve ser
recomendado).

Assim, acho que o mais seguro é converter o algoritmo recursivo para um
iterativo com um acumulador.

Mario
--
http://parenteses.org/mario

[Diego Rocha]

Pessoal,

Muito obrigado, foi bastante esclarecedor!

Atenciosamente,

Diego Rocha

2012/11/27 Mario Domenech Goulart <mario....@gmail.com>

[Moises Trovó]

@Christian Na verdade o tipo inteiro no python eh limitado apenas pela memoria da maquina, nao pelo tamanho da word no processador. Internamente o python usa uma referencia de 32 bits (um int em C) para representar numeros pequenos e vai aumentando a quantidade de ints conforme o necessário. Dessa forma o tamanho de um número nunca vai ter overflow, nem com numeros muito maiores que um long do C.

Pode ler aqui nessa pergunta do stackoverflow http://stackoverflow.com/a/5470740, abaixo o texto:

Small Python integer numbers fit into machine word of the platform (e.g. 32 bit). If a number doesn't fit, it is automatically promoted to a 'long' integer which is as long as your RAM allows. You can't really have an integer overflow. 

2012/11/27 Christian S. Perone <christia...@gmail.com>

Diego, o interpretador utiliza um "long" primitivo do C para representar números inteiros (int), mas antes de acontecer um overflow no int ele promove esse tipo para "long" (do Python), o long é representado internamente em software e não é mapeado para um tipo primitivo do C, a vantagem é que isto fica transparente para o usuário e o long acaba ganhando um limite virtualmente ilimitado (virtualmente porque depende dos recursos de hardware), mas obviamente que esta representação tem um custo de manuseio bem maior do que quando você utiliza tipos primitivos. É semelhando ao uso da gmplib em C, só que de forma implícita e transparente.

[Christian S. Perone]

Moises, não entendi, não foi isto que eu falei anteriormente ? Ele é "virtualmente" ilimitado justamente por causa dos recursos de hardware (aka memória).

Att.

2012/11/27 Moises Trovó <moises...@gmail.com>

[Diego Rocha]

Pessoal,

Nos testes que eu fiz o fatorial de 100 precisa de mais de 200 bits pra ser armazenado e foi calculado corretamente em menos de 1 segundo.

Atenciosamente,

Diego Rocha

[Moises Trovó]

Vdd Christian, só passei o olho no começo do que vc escreveu e achei que estava errado, mals ae.

[Lucas Sampaio]

Também é possível cortar o recursion limit do Python usando tail recursion, que não empilha chamadas recursivas. Isso permite, teoricamente, recursões infinitas sem stack overflow.

O Python não tem suporte nativo a tail recursion, mas é possível implementar com o uso de um decorator[1]. Um tempo atrás, mais ou menos um ano, soube de um pacote que implementava isso, TailSpin[2], mas na época a documentação era uma droga, então deixei baixo.

[1]: http://lambda-the-ultimate.org/node/1331
[2]: http://pypi.python.org/pypi/TailSpin

---
Lucas S. Magalhães
Developer at Órama
http://lsmagalhaes.com

[Vinicius Assef]

Na Python Brasil, tivemos uma palestra sobre programação funcional que
demonstrou uma forma de superar esse limite de recursão, usando
memoization.

De repente os palestrantes estão por aqui na lista. Lembro que eles
são da globo.com.



2012/11/27 Lucas Sampaio <m...@lsmagalhaes.com>:

[Joao S. O. Bueno]

2012/11/27 Lucas Sampaio <m...@lsmagalhaes.com>:

> Também é possível cortar o recursion limit do Python usando tail recursion,
> que não empilha chamadas recursivas. Isso permite, teoricamente, recursões
> infinitas sem stack overflow.
>
> O Python não tem suporte nativo a tail recursion, mas é possível implementar
> com o uso de um decorator[1]. Um tempo atrás, mais ou menos um ano, soube de
> um pacote que implementava isso, TailSpin[2], mas na época a documentação
> era uma droga, então deixei baixo.
>
> [1]: http://lambda-the-ultimate.org/node/1331
> [2]: http://pypi.python.org/pypi/TailSpin

Tenho uma receita também - é legal como brinquedo:
http://metapython.blogspot.com.br/2010/11/tail-recursion-elimination-in-python.html

Mas para calculo intensivo, e não brincadeiras experiemtnais, a melhor coisa é
convertter o algoritmo de recursivo para interativo.

(Para algo rápido e simples, também é possivel alterar o limtite de
recursao do Python,
é só chamar sys.setrecursionlimit - mas na minha experiencia o
interpretador começa a travar com números
perto de 10000 recursões (cPython 2.6 64bit, 4GB, posix) )

js
-><-

[Lucas Sampaio]

Vish, usando threads, que maneiro! Vou dar uma olhada melhor mais tarde.

Na real, a única linguagem que conheço no momento a implementar tail recursion é Erlang... enfim, concordo contigo, em Python, pra coisas mais pesadas, um algoritmo iterativo é melhor mesmo.

---
Lucas S. Magalhães
Developer at Órama
http://lsmagalhaes.com

[Luciano Ramalho]

2012/11/27 Vinicius Assef <vinic...@gmail.com>:

> Na Python Brasil, tivemos uma palestra sobre programação funcional que
> demonstrou uma forma de superar esse limite de recursão, usando
> memoization.

Não tem como resolver o problema da recursão do fatorial por
memoization. Apenas no caso do Fibonacci que usa duas recursões isso
ajuda. Mas a implementação do Fibonacci com duas recursões é uma
aberração de qualquer jeito.

[ ]s
Luciano

Luciano Ramalho / OFICINAS TURING
Twitter: @ramalhoorg

Autor e professor dos cursos:

* Objetos Pythonicos --> http://turing.com.br/oopy
* Python para quem sabe Python --> http://turing.com.br/ppqsp

[leonardo]

Fiquei bem interessado nesta palestra de python funcional, mas não pude assistir pois coincidia horários.

Alguém sabe se os palestrantes disponibilizaram os slides em algum lugar ou deixaram algum contato ?

Abs\,