Last active
February 24, 2025 05:26
-
-
Save joshuachris2001/4443e2b09b3adfad0c48ee32fa16a54c to your computer and use it in GitHub Desktop.
dectofrac
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import math | |
| from math import pi | |
| def decToFrac(): | |
| decimal = float(input("Enter a decimal number to convert to a fraction: ")) | |
| # Handle negative numbers | |
| is_negative = decimal < 0 | |
| decimal = abs(decimal) | |
| # Tolerance for stopping the algorithm | |
| #tolerance = 1e-10 | |
| #max_denominator = 1000000 # To prevent excessively large denominators | |
| numerator, denominator = continued_fraction(decimal)#, tolerance, max_denominator) | |
| if is_negative: | |
| numerator = -numerator | |
| #print(f"The decimal {decimal} as a simplified fraction is {numerator}/{denominator}") | |
| print("The decimal " + str(decimal) + " as a simplified fraction is\n " + str(numerator)+"/"+str(denominator)) | |
| def decToRad(): | |
| decimal = float(input("Enter a decimal number to convert to a fraction of π: ")) | |
| pi = math.pi | |
| ratio = decimal / pi | |
| # Handle negative numbers | |
| is_negative = ratio < 0 | |
| ratio = abs(ratio) | |
| # Tolerance for stopping the algorithm | |
| #tolerance = 1e-10 | |
| #max_denominator = 1000000 # To prevent excessively large denominators | |
| numerator, denominator = continued_fraction(ratio)#, tolerance, max_denominator) | |
| if is_negative: | |
| numerator = -numerator | |
| #print(f"The decimal {decimal} as a fraction of π is {numerator}/{denominator}π") | |
| print("The decimal " + str(decimal) + " as a fraction of π is " + str(numerator) +"/"+ str(denominator)+"π") | |
| # backup brute forcing | |
| def brute_continued_fraction(_x, tolerance = 1e-5, max_denominator = 1000000): | |
| current_numerator, current_denominator = max_denominator, max_denominator | |
| for x in range(1,max_denominator): | |
| for y in range(1,max_denominator): | |
| D = x / y | |
| if abs(D - _x) <= tolerance and y < current_denominator: | |
| current_numerator = x | |
| current_denominator = y | |
| return current_numerator, current_denominator | |
| assert brute_continued_fraction(0.5,max_denominator = 50) == (1,2) | |
| def decimal_to_continued_fraction(x, tolerance=1e-2, max_terms=400): | |
| cf = [] | |
| sign = -1 if x < 0 else 1 | |
| x = abs(x) | |
| for _ in range(max_terms): | |
| term = math.floor(x) | |
| cf.append(term) | |
| remainder = x - term | |
| if remainder < tolerance: | |
| break | |
| try: | |
| x = 1 / remainder | |
| except ZeroDivisionError: | |
| break | |
| if cf: | |
| cf[0] *= sign # Apply sign to first term | |
| cf[0] | |
| #print(cf) | |
| return cf | |
| def continued_fraction_to_fraction(cf): | |
| if not cf: | |
| return 0, 1 | |
| numerator = 1 | |
| denominator = cf[-1] | |
| for term in reversed(cf[:-1]): | |
| numerator, denominator = denominator, term * denominator + numerator | |
| return (denominator, numerator) if len(cf) % 2 == 0 else (denominator, numerator) | |
| def continued_fraction(dec): | |
| cf = decimal_to_continued_fraction(dec) | |
| n, d = continued_fraction_to_fraction(cf) | |
| # print(n,d) | |
| return n, d | |
| def __continued_fraction(x, tolerance=1e-9, max_denominator=1000000): | |
| """Finds the fraction approximation for x using continued fractions.""" | |
| from math import floor | |
| # Handle exact integers | |
| if x == int(x): | |
| return int(x), 1 | |
| a0 = floor(x) | |
| h1, k1 = 1, 0 # Numerators and denominators for previous two convergents | |
| h0, k0 = a0, 1 | |
| x = x - a0 # Fractional part of x | |
| if x == 0: | |
| return h0, k0 | |
| while True: | |
| x = 1 / x | |
| a = floor(x) | |
| x = x - a | |
| h2 = a * h0 + h1 | |
| k2 = a * k0 + k1 | |
| if k2 > max_denominator: | |
| break | |
| approx = h2 / k2 | |
| actual = (h0 + h1 / k1) / (k0 + k1 / k1) | |
| #try: | |
| # actual = (h0 + h1 / k1) / (k0 + k1 / k1) | |
| #except Exception as e: | |
| # actual = (h0 + h1 / (k1+1)) / (k0 + k1 / (k1+1)) | |
| error = abs(approx - actual) | |
| if error < tolerance: | |
| break | |
| h1, k1 = h0, k0 | |
| h0, k0 = h2, k2-1 | |
| if x == 0 or abs(x) < tolerance: | |
| break | |
| print(h0, k0) | |
| return h0, k0 | |
| assert continued_fraction(0.5) == (1,2) | |
| assert continued_fraction(0.3333) == (1,3) | |
| assert continued_fraction(0.666666) == (2,3) | |
| def main(): | |
| for i in range(1): | |
| print("\n1. Convert decimal to fraction") | |
| print("2. Convert decimal to fraction of π") | |
| print("3. Exit") | |
| choice = input("Choose an option: ") | |
| if choice == "1": | |
| decToFrac() | |
| elif choice == "2": | |
| decToRad() | |
| elif choice == "3": | |
| break | |
| else: | |
| print("Invalid choice. Please choose a valid option.") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment