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