Skip to content

Instantly share code, notes, and snippets.

@sharmaeklavya2
Last active November 24, 2022 23:23
Show Gist options
  • Save sharmaeklavya2/87af6715f783d9e440df5dd410dff6fc to your computer and use it in GitHub Desktop.
Save sharmaeklavya2/87af6715f783d9e440df5dd410dff6fc to your computer and use it in GitHub Desktop.
float to nearest fraction
#!/usr/bin/env python3
"""
Convert a float to the nearest fraction.
"""
import math
import ast
import argparse
from fractions import Fraction as F
from collections.abc import Collection, Mapping
from typing import Any, Union
F.__repr__ = F.__str__ # type: ignore
DEFAULT_N = 1000
DEFAULT_EPS = 1e-8
def fareyBasic(x: float, N: int = DEFAULT_N, eps: float = DEFAULT_EPS) -> Union[int, float, F]:
xfloor = math.floor(x)
x -= xfloor
if abs(x) <= eps:
return xfloor
if abs(1-x) <= eps:
return xfloor + 1
a, b, c, d = 0, 1, 1, 1
while b <= N and d <= N:
mediant = (a+c)/(b+d)
if abs(x - mediant) <= eps:
if b + d <= N:
return xfloor + F(a+c, b+d)
elif d > b:
return xfloor + F(c, d)
else:
return xfloor + F(a, b)
elif x > mediant:
a, b = a+c, b+d
else:
c, d = a+c, b+d
return xfloor + x
def farey(x: Any, N: int = DEFAULT_N, eps: float = DEFAULT_EPS) -> Any:
if x is None:
return None
elif isinstance(x, Mapping):
return {k: farey(v, N, eps) for k, v in x.items()}
elif isinstance(x, Collection):
return [farey(y, N, eps) for y in x]
else:
return fareyBasic(x, N, eps)
def main() -> None:
parser = argparse.ArgumentParser(description=__doc__)
parser.add_argument('x', type=ast.literal_eval, help='number(s) to convert to fraction')
parser.add_argument('-N', type=int, default=DEFAULT_N, help='max denominator')
parser.add_argument('--eps', type=int, default=DEFAULT_EPS, help='precision')
args = parser.parse_args()
f = farey(args.x, N=args.N, eps=args.eps)
print(f)
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment