from operator import add, mul
from math import sqrt, e

#This is just a handy function that clears the screen on windows.
import os
clear = lambda: os.system('cls')

def trace1(fn):
    def traced(x):
        print('Calling', fn, '(', x, ')')
        result = fn(x)
        print('Got', result, 'from', fn, '(', x, ')')
        return result
    return traced

@trace1
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

def curry2(f):
    def outer(a):
        def inner(b):
            return f(a,b)
        return inner
    return outer    

def mul_rational(x, y):
    """Multiply two rationals together.

    >>> r = mul_rational(rational(3, 2), rational(3, 5))
    >>> numer(r) / denom(r)
    0.9
    """
    return rational(numer(x) * numer(y), denom(x) * denom(y))

def add_rational(x, y):
    """Add two rationals together.

    >>> r = add_rational(rational(3, 2), rational(3, 5))
    >>> numer(r) / denom(r)
    2.1
    """
    nx, dx = numer(x), denom(x)
    ny, dy = numer(y), denom(y)
    return rational(nx * dy + ny * dx, dx * dy)

def eq_rational(x, y):
    """Determine if two rationals are equal.

    >>> eq_rational(rational(1, 2), rational(2, 4))
    True
    >>> eq_rational(rational(1, 2), rational(3, 4))
    False
    """
    return numer(x) * denom(y) == numer(y) * denom(x)

# Representing rationals using tuples
from operator import getitem
from fractions import gcd

def rational(n, d):
    g = gcd(n, d)
    return (n//g, d//g)

def numer(x):
    return getitem(x, 0)

def denom(x):
    return getitem(x, 1)