def closest_fraction(x, N):
    """Compute (a, b) such that a/b is closest to x from below, and with 0 <= a, b < N"""
    best_num = 0
    best_den = 1
    best_approx = 0.0

    assert(x >= 0)

    for den in range(1, N):
        num = round(den * x)
        approx = num / den
        if x - approx >= 0 and x - approx < x - best_approx:
            best_num = num
            best_den = den
            best_approx = approx

            # If we are very close, no need to search for more.
            if x - approx < 1e-5:
                break

    return (best_num, best_den)