"""
The Fibonacci sequence is defined by the recurrence relation:
F_n = F_{n-1} + F_{n-2}, where F_1 = 1 and F_2 = 1.

Hence the first 12 terms will be: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
The 12th term, F_12, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000-digits?
"""

import math
import time


def timer(func):
    def wrapper(*args, **kwargs):
        start_time = time.time()
        result = func(*args, **kwargs)
        end_time = time.time()
        during = end_time - start_time
        if during > 1:
            print(f"function {func.__name__} taken: {during:.6f} seconds")
        elif during > 0.001:
            print(f"function {func.__name__} taken: {during * 1000:.3f} milliseconds")
        else:
            print(
                f"function {func.__name__} taken: {during * 1000000:.3f} microseconds"
            )
        return result

    return wrapper


def big_sum(a: str, b: str) -> str:
    length = max(len(a), len(b))
    carry = 0
    result = []
    for i in range(length):
        digit_a = int(a[-i - 1]) if i < len(a) else 0
        digit_b = int(b[-i - 1]) if i < len(b) else 0
        sum_digit = digit_a + digit_b + carry
        result.append(str(sum_digit % 10))
        carry = sum_digit // 10
    if carry:
        result.append(str(carry))
    return "".join(result[::-1])


def find_fibonacci_index(digits: int) -> int:
    a, b = "1", "1"
    index = 1
    while len(a) < digits:
        a, b = b, big_sum(a, b)
        index += 1
    return index


@timer
def main_in_bigint():
    print(find_fibonacci_index(1000))


def binet(n: int) -> int:
    index = math.ceil(
        (math.log10(math.sqrt(5)) + (n - 1)) / math.log10(0.5 * (1 + math.sqrt(5)))
    )
    return index


@timer
def main_use_binet():
    print(f"{binet(1000)}")


if __name__ == "__main__":
    main_in_bigint()
    main_use_binet()