[Python] How to get specified number of decimal places of any fraction?

So I can generate many tuples like this:

(601550405185810455248373798733610900689885946410558295383908863020551447581889414152035914344864580636662293641050147614154610394724089543305418716041082523503171641011728703744273399267895810412812627682686305964507416778143771218949050158028407021152173879713433156038667304976240165476457605035649956901133077856035193743615197184,
191479441008508487760634222418439911957601682008868450843945373670464368694409556412664937174591858285324642229867265839916055393493144203677491629737464170928066273172154431360491037381070068776978301192672069310596051608957593418323738306558817176090035871566224143565145070495468977426925354101694409791889484040439128875732421875)


They are all tuples of two ints, they represent fractions with (nearly) infinite precision (bounded only by computer memory), the first number is the numerator, the second denominator.

If we divide them, we get the first 101 decimal places of π:

'3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798'


I did everything using integer math and without using any libraries. I didn't use any floating point because I know they are all of finite precision, in contrast to int's infinite precision in Python.

Python's float uses this, and it only has log10(2) * 52 = 15.653559774527022 decimal places, far less than what I wanted.

I wrote two correct functions to get n specified decimal places of any fraction:

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")


They work but both are inefficient, as they are literally doing long division.

They both adhere to the following rules:

They should return the fraction expanded to the desired width, unless the fraction terminates before reaching the width (we had an exact finite decimal representation before reaching the width);

If the last few digits of the decimal expansion cutoff are 0, in which case the result should not contain any trailing zeros, unless the very first decimal digit is 0. For example, it should be '0.0' instead of '0.'

Additionally, the second function breaks out of the loop once it has all digits of one cycle, and constructs the remaining digits by repeating the cycle, though in each iteration more work is done, as a result it is faster if the cycle is short, and slower if the cycle is longer. Worst case is if the cycle is longer than length, so it does all the extra work without terminating early:

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)


How can we do better than long division, so that the execution time is reduced drastically, while achieving the same result (using integer math to get infinite precision representation of fractions)? Preferably this should be done without using any libraries as I would like to know the algorithm.

Continue reading...