continued_fraction uses float division, producing invalid terms for large integers and raising OverflowError
Maintainer antworten meist innerhalb von 2 Tagen
Bewertung
- Schwierigkeit
- 1/5
- Geschätzter Aufwand
- Unter einer Stunde
- Anfängerfreundlichkeit
- 88/100
Rechercherichtung
Öffne maths/continued_fraction.py und sieh dir die Schleife an, die jeden Term berechnet: Der Quotient wird mit floor(numerator / denominator) gebildet, was zuerst nach float konvertiert. Reproduziere es mit dem Snippet im Issue, ersetze diesen Schritt durch ganzzahlige Floor-Division, damit exakte Brüche beliebiger Größe funktionieren, und prüfe, dass continued_fraction(Fraction(2**53 + 3)) [9007199254740995] zurückgibt und der Fall 10**400 / 3 nicht mehr überläuft. Fertig bedeutet, dass sich beide Beispiele korrekt verhalten und negative Brüche weiterhin einen korrekten Kettenbruch ergeben.
Vom Indexierungsmodell aus dem Issue-Text verfasst.
Beschreibung
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.
- Vorherrschende Sprache
- Python
- Sterne
- 225k
- Forks
- 51.2k
- Ø Merge
- 1 T. 13 Std.
- Gemergte PRs (30 T.)
- 32
Entwicklungsumgebung
Startet den Dev-Container des Projekts im Browser, mit Ihrem eigenen GitHub-Konto.
- Kein Dockerfile und keine Docker-Compose-Datei
- Hat eine Pull-Request-Vorlage
- Beitragsleitfaden lesen
Erste Schritte
- Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
- Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
- Forken Sie das Repository und arbeiten Sie in einem Branch.
- Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.
Mehr aus TheAlgorithms/Python
-
binomial_distribution overflows at 171 trials even when the result is representableEvtl. vergeben @landfvit hat das vor 2 Tagen übernommen. Offen
Schwierigkeit 1/5 Unter einer Stunde Anfängerfreundlichkeit 85/100
TheAlgorithms/Python#15656 · 1 Kommentar ·
Maintainer antworten meist innerhalb von 2 Tagen
-
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 crashEvtl. vergeben @Nate-br hat das vor 4 Tagen übernommen. Offen
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 88/100
TheAlgorithms/Python#15636 · 1 Kommentar ·
Maintainer antworten meist innerhalb von 2 Tagen
-
ciphers/des_ecb.py: encrypt/decrypt silently corrupts any character above U+00FF (round-trip fails)Evtl. vergeben @mohammedanasnakhuda hat das vor 5 Tagen übernommen. Offen
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 88/100
TheAlgorithms/Python#15634 ·
Maintainer antworten meist innerhalb von 2 Tagen
-
other/password.py: alternative_password_generator ignores the requested length when the required characters exceed itEvtl. vergeben @raaj-2222 hat das vor 5 Tagen übernommen. Offen
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 85/100
TheAlgorithms/Python#15633 · 1 Kommentar ·
Maintainer antworten meist innerhalb von 2 Tagen
-
ciphers/base58.py is a copy of base64_cipher.py — no Base58 implementation exists in the fileEvtl. vergeben @SakshiYeole hat das vor 5 Tagen übernommen. Offen
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 45/100
TheAlgorithms/Python#15637 ·
Maintainer antworten meist innerhalb von 2 Tagen
Alle Issues in TheAlgorithms/Python
Ähnliche Issues
-
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 68/100
vllm-project/vllm#64845 ·
Maintainer antworten meist innerhalb von 1 Tag
-
bug
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 84/100
dekobon/big-code-analysis#1729 ·
Maintainer antworten meist innerhalb von 1 Tag
-
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 70/100
pydantic/pydantic-ai#12091 ·
Maintainer antworten meist innerhalb von 1 Tag
-
bug
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 88/100
Maintainer antworten meist innerhalb von 1 Tag
-
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 82/100