'''
It is possible to show that the square root of two can be expressed as an infinite continued fraction.
sqrt{2}=1+frac{1}{2+frac{1}{2+frac{1}{2+...}}}

By expanding this for the first four iterations, we get:
begin{aligned}
 & 1+frac{1}{2}=frac{3}{2}=1.5 \\
 & 1+frac{1}{2+frac{1}{2}}=frac{7}{5}=1.4 \\
 & 1+frac{1}{2+frac{1}{2+frac{1}{2}}}=frac{17}{12}=1.41666... \\
 & 1+frac{1}{2+frac{1}{2+frac{1}{2+frac{1}{2}}}}=frac{41}{29}=1.41379 ldots
end{aligned}

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, 
is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than the denominator?
'''
import time
from functools import wraps
from typing import Any, Callable, TypeVar

from math import gcd

F = TypeVar("F", bound=Callable[..., Any])


def benchmark(repeat: int = 1) -> Callable[[F], F]:
    if repeat < 1:
        raise ValueError("repeat must >= 1")

    def decorator(func: F) -> F:
        @wraps(func)
        def wrapper(*args: Any, **kwargs: Any) -> Any:
            total = 0.0
            result = None

            for _ in range(repeat):
                start = time.perf_counter()
                result = func(*args, **kwargs)
                end = time.perf_counter()
                total += end - start

            wrapper.avg_time = total / repeat  # type: ignore[attr-defined]
            wrapper.total_time = total  # type: ignore[attr-defined]

            print(
                f"[Benchmark] {func.__name__} | repeated {repeat} times | "
                f"average: {wrapper.avg_time:.6f}s | total: {wrapper.total_time:.6f}s"  # type: ignore[attr-defined]
            )
            return result

        wrapper.avg_time = 0.0  # type: ignore[attr-defined]
        wrapper.total_time = 0.0  # type: ignore[attr-defined]
        return wrapper  # type: ignore[return-value]

    return decorator


def compute_square_root(n: int = 1000) -> list[tuple[int,int]] :
    """
    Compute the square root of 2 up to n expansions.
    """
    cf = [1] + [2 for _ in range(0, n)]
    p2, p1 = 0, 1   # p_{-2}, p_{-1}
    q2, q1 = 1, 0   # q_{-2}, q_{-1}
    results = []
    for a in cf:
        p = a * p1 + p2
        q = a * q1 + q2
        p2, p1 = p1, p
        q2, q1 = q1, q
        if gc := gcd(p, q) != 1:
            p //= gc
            q //= gc
        results.append((p, q))
    return results

@benchmark(20)
def main() -> None:
    results = compute_square_root(1000)
    count = 0
    for p, q in results:
        if len(str(p)) > len(str(q)):
            count += 1
    print(f"{count} fractions contain a numerator with more digits than the denominator.")
    print(f"sqrt{2} = {results[-1][0]/results[-1][1]:.15f}")


if __name__ == "__main__":
    main()