Wie bekomme ich eine bestimmte Anzahl von Dezimalstellen eines Bruchteils? ⇐ Python

[Anonymous]

damit ich viele Tuple wie folgt generieren kann:

Code: Select all

(601550405185810455248373798733610900689885946410558295383908863020551447581889414152035914344864580636662293641050147614154610394724089543305418716041082523503171641011728703744273399267895810412812627682686305964507416778143771218949050158028407021152173879713433156038667304976240165476457605035649956901133077856035193743615197184,
191479441008508487760634222418439911957601682008868450843945373670464368694409556412664937174591858285324642229867265839916055393493144203677491629737464170928066273172154431360491037381070068776978301192672069310596051608957593418323738306558817176090035871566224143565145070495468977426925354101694409791889484040439128875732421875)

Sie sind alle Tuple von zwei int s, sie repräsentieren Brüche mit (fast) unendlicher Präzision (nur durch Computergedächtnis begrenzt), die erste Zahl ist der Zähler, der zweite Nenner.

Code: Select all

'3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798'
< /code>
Ich habe alles mit Integer Math und ohne Bibliotheken gemacht. Ich habe keinen schwimmenden Punkt verwendet, weil ich weiß, dass sie alle endliche Präzision sind, im Gegensatz zu Int 

in der unendlichen Präzision in Python. gesucht.

Code: Select all

from typing import Dict, List, Tuple

def decimalize(dividend: int, divisor: int, places: int) -> str:
div, mod = divmod(dividend, divisor)
result = [f"{div}."]
while mod and places:
div, mod = divmod(mod * 10, divisor)
result.append(str(div))
places -= 1

integral, first, *others = result
return integral + first + "".join(others).rstrip("0")

def pad_cycles(mod: int, places: int, pairs: Dict[int, str], result: List[str]) -> None:
if mod and places:
i = list(pairs).index(mod)
cycle = "".join(list(pairs.values())[i:])
div, mod = divmod(places, len(cycle))
result.append(cycle * div + cycle[:mod])

def decimalize1(dividend: int, divisor: int, places: int) -> str:
div, mod = divmod(dividend, divisor)
result = [f"{div}."]
pairs = {}
while mod and places and mod not in pairs:
div, mod1 = divmod(mod * 10, divisor)
pairs[mod] = (div := str(div))
result.append(div)
mod = mod1
places -= 1

pad_cycles(mod, places, pairs, result)
integral, first, *others = result
return integral + first + "".join(others).rstrip("0")

Sie arbeiten, aber beide sind ineffizient, da sie buchstäblich lange Teilung durchführen. /> Wenn die letzten Ziffern der Dezimalerweiterung Cutoff 0 betragen, sollte das Ergebnis keine nachverfolgenden Nullen enthalten, es sei denn

Code: Select all

'0.'

Zusätzlich bricht die zweite Funktion aus der Schleife aus, sobald sie alle Ziffern eines Zyklus hat, und konstruiert die verbleibenden Ziffern, indem der Zyklus wiederholt wird. In jeder Iteration wird mehr Arbeit erledigt, sodass der Zyklus kurz und langsamer ist, wenn der Zyklus länger ist. Der schlimmste Fall ist, ob der Zyklus länger als Länge ist, sodass die gesamte zusätzliche Arbeit ohne frühzeitig endet:

Code: Select all

In [364]: %timeit decimalize(1, 3, 100)
25.8 μs ± 371 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [365]: %timeit decimalize1(1, 3, 100)
2.07 μs ± 20.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [366]: %timeit decimalize(1, 137, 100)
26.8 μs ± 209 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [367]: %timeit decimalize1(1, 137, 100)
4.94 μs ± 38.1 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [368]: %timeit decimalize1(1, 1337, 100)
43.4 μs ± 280 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [369]: %timeit decimalize(1, 1337, 100)
28.6 μs ± 389 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [370]: %timeit decimalize1(1, 123456789, 100)
42.4 μs ± 309 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [371]: %timeit decimalize(1, 123456789, 100)
29.7 μs ± 494 ns per loop (mean ± std. dev.  of 7 runs, 10,000 loops each)

In [372]: a = 60155040518581045524837379873361090068988594641055829538390886302055144758188941415203591434486458063666229364105014761415461039472408954330541871604108252350317164101172870374427339926789581041
...: 2812627682686305964507416778143771218949050158028407021152173879713433156038667304976240165476457605035649956901133077856035193743615197184

In [373]: b = 19147944100850848776063422241843991195760168200886845084394537367046436869440955641266493717459185828532464222986726583991605539349314420367749162973746417092806627317215443136049103738107006877
...: 6978301192672069310596051608957593418323738306558817176090035871566224143565145070495468977426925354101694409791889484040439128875732421875

In [374]: decimalize(a, b, 101)
Out[374]: '3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798'

In [375]: decimalize1(a, b, 101) == decimalize(a, b, 101)
Out[375]: True

In [376]: %timeit decimalize1(a, b, 101)
96.3 μs ± 295 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [377]: %timeit decimalize(a, b, 101)
64.4 μs ± 402 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
< /code>
Wie können wir es besser abschneiden als eine lange Abteilung, damit die Ausführungszeit drastisch reduziert wird, während wir dasselbe Ergebnis erzielen (unter Verwendung von Ganzzahlmathematik, um unendliche Präzisionsdarstellung von Brüchen zu erhalten)? Vorzugsweise sollte dies ohne Verwendung von Bibliotheken erfolgen, da ich den Algorithmus kennenlernen möchte.In [398]: decimalize1(1, 5, 99999999999999999999999999999999999999999)
Out[398]: '0.2'

In [399]: decimalize1(1, 5, 10**1000-1)
Out[399]: '0.2'
< /code>
In meiner Lösung, egal wie viele Ziffern gefragt werden, wird die Anzahl der gefragten Ziffern immer eine genaue Dezimalrepräsentation als kürzer als gefragt. An jedem n. [url=viewtopic.php?t=14917]Ich möchte[/url] wissen, welcher Algorithmus für unendliche Präzisionsdezimal verwendet werden kann.In [409]: places = 4096
...: div, mod = divmod(1, 1337)
...: result = [f"{div}."]
...: pairs = {}
...: while mod and places and mod not in pairs:
...:     div, mod1 = divmod(mod * 10, 1337)
...:     pairs[mod] = (div := str(div))
...:     result.append(div)
...:     mod = mod1
...:     places -= 1

In [410]: len(result)
Out[410]: 571

In [411]: len(pairs)
Out[411]: 570