continued_fraction uses float division, producing invalid terms for large integers and raising OverflowError
Mantenedores costumam responder em até 2 dias
Avaliação
- Dificuldade
- 1/5
- Tempo estimado
- Menos de uma hora
- Facilidade para iniciantes
- 88/100
Direção de pesquisa
Abra maths/continued_fraction.py e observe o loop que calcula cada termo: o quociente é obtido com floor(numerator / denominator), que converte para float primeiro. Reproduza com o snippet na issue, substitua essa etapa por divisão inteira com floor para que frações exatas de qualquer tamanho funcionem, e verifique que continued_fraction(Fraction(2**53 + 3)) retorna [9007199254740995] e que o caso 10**400 / 3 não estoura mais. Pronto significa que ambos os exemplos se comportam corretamente e que frações negativas ainda dão uma fração contínua correta.
Escrita pelo modelo de indexação a partir do texto da issue.
Descrição
Repository commit
6e03a48579ca212a08b36be00378f887dc41a003
Python version (python --version)
Python 3.11.0, macOS
Dependencies version (pip freeze)
The reproduction uses only Python's standard library; no third-party dependencies are involved.
Expected behavior
continued_fraction(Fraction(2**53 + 3)) should return [9007199254740995], the continued fraction of that integer. Large exact fractions should not fail merely because they exceed floating-point range.
Actual behavior
Run from the repository root:
from fractions import Fraction
from maths.continued_fraction import continued_fraction
print(continued_fraction(Fraction(2**53 + 3)))
try:
print(continued_fraction(Fraction(10**400, 3)))
except OverflowError as exc:
print(type(exc).__name__ + ':', exc)
Output:
[9007199254740996, -1]
OverflowError: integer division result too large for a float
The first result represents the same integer numerically, but is not the regular continued fraction: the trailing term is negative because the first quotient was rounded upward.
In maths/continued_fraction.py, floor(numerator / denominator) first converts the integer ratio to a float. This loses precision for sufficiently large values and can overflow. Computing the quotient directly with integer floor division (numerator // denominator) preserves exact arithmetic and also handles negative fractions.
I searched existing issues and PRs for continued fraction and continued_fraction; I did not find an existing report of this problem.
- Linguagem predominante
- Python
- Estrelas
- 226k
- Forks
- 51.3k
- Merge médio
- 1d 13h
- PRs com merge (30d)
- 32
Preparar o ambiente
Inicia o contêiner de desenvolvimento do projeto no navegador, com a sua própria conta do GitHub.
- Sem Dockerfile nem arquivo Docker Compose
- Tem um modelo de pull request
- Ler o guia de contribuição
Primeiros passos
- Leia a issue inteira e depois o guia de contribuição do projeto.
- Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
- Faça um fork do repositório e trabalhe em uma branch.
- Abra um pull request que referencie o número da issue.
Mais de TheAlgorithms/Python
-
binomial_distribution overflows at 171 trials even when the result is representableTalvez já em andamento @landfvit assumiu há 6 dias. Aberta
Dificuldade 1/5 Menos de uma hora Facilidade para iniciantes 85/100
TheAlgorithms/Python#15656 · 2 comentários ·
Mantenedores costumam responder em até 2 dias
-
ciphers/base32.py and ciphers/base85.py encode Unicode code points instead of bytes: output diverges from the spec for non-ASCII, round-trips corrupt chars >= U+0400, arbitrary bytes crashTalvez já em andamento @Nate-br assumiu há 7 dias. Aberta
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 88/100
TheAlgorithms/Python#15636 · 1 comentário ·
Mantenedores costumam responder em até 2 dias
-
ciphers/des_ecb.py: encrypt/decrypt silently corrupts any character above U+00FF (round-trip fails)Talvez já em andamento @mohammedanasnakhuda assumiu há 8 dias. Aberta
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 88/100
TheAlgorithms/Python#15634 ·
Mantenedores costumam responder em até 2 dias
-
other/password.py: alternative_password_generator ignores the requested length when the required characters exceed itTalvez já em andamento @raaj-2222 assumiu há 8 dias. Aberta
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 85/100
TheAlgorithms/Python#15633 · 1 comentário ·
Mantenedores costumam responder em até 2 dias
-
ciphers/base58.py is a copy of base64_cipher.py — no Base58 implementation exists in the fileTalvez já em andamento @SakshiYeole assumiu há 9 dias. Aberta
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 45/100
TheAlgorithms/Python#15637 ·
Mantenedores costumam responder em até 2 dias
Todas as issues de TheAlgorithms/Python
Issues semelhantes
-
cost:cheap practicality:seen-in-the-wild severity:medium
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 72/100
fairagro/m4.2_advanced_middleware_api#620 ·
Mantenedores costumam responder em até 1 dia
-
area:security effort:S priority:P2 provider:local-libvirt status:ready type:docs
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 75/100
randomparity/kdive#3495 ·
Mantenedores costumam responder em até 1 dia
-
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 82/100
microsoft/markitdown#2820 ·
Mantenedores costumam responder em até 1 dia
-
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 72/100
Mantenedores costumam responder em até 1 dia
-
Dificuldade 2/5 1-3 horas Facilidade para iniciantes 78/100
Mantenedores costumam responder em até 2 dias