from fractions import Fraction
from math import sqrt
from itertools import chain, cycle

from typing import Generator, Iterable, List, Tuple


def convergent_sequence(generator: Iterable[int]) -> \
        Generator[Fraction, None, None]:
    h = (0, 1)
    k = (1, 0)

    for a in generator:
        h = h[1], a * h[1] + h[0]
        k = k[1], a * k[1] + k[0]

        yield Fraction(h[-1], k[-1])


def continued_fraction_sqrt(n: int) -> Tuple[List[int], List[int]]:
    remainders = []
    continued_fraction = []
    remainder = (Fraction(1), Fraction(0))  # remainder is sqrt(n) + 0.

    sqrt_n = sqrt(n)

    while remainder not in remainders:
        remainders.append(remainder)

        a = int(remainder[0] * sqrt_n + remainder[1])
        continued_fraction.append(a)

        norm = (remainder[1] - a) ** 2 - remainder[0] ** 2 * n
        remainder = (-remainder[0] / norm, (remainder[1] - a) / norm)

    index = remainders.index(remainder)

    return continued_fraction[:index], continued_fraction[index:]


def convergents_sqrt(n: int) -> Generator[Fraction, None, None]:
    initial, repeat = continued_fraction_sqrt(n)
    convergents = convergent_sequence(chain(initial, cycle(repeat)))

    yield from convergents

from fractions import Fraction
from math import sqrt
from itertools import chain, cycle

from typing import Generator, Iterable, List, Tuple

from .gcd import gcd
from ..sqrt import fsqrt


def convergent_sequence(generator: Iterable[int]) -> \
        Generator[Fraction, None, None]:
    h = (0, 1)
    k = (1, 0)

    for a in generator:
        h = h[1], a * h[1] + h[0]
        k = k[1], a * k[1] + k[0]

        yield Fraction(h[-1], k[-1])


def continued_fraction_sqrt(n: int) -> Tuple[List[int], List[int]]:
    sqrt_n = sqrt(n)
    remainders = []
    remainder = (0, 1)
    # remainder is an + (sqrt(n) - p) / q and these are initial.
    continued_fraction = []

    while remainder not in remainders:
        remainders.append(remainder)
        p, q = remainder

        q = (n - (p * p)) // q
        a = int((sqrt_n + p) / q)
        p = a * q - p

        continued_fraction.append(a)

        remainder = (p, q)

    index = remainders.index(remainder)

    return continued_fraction[1:index], continued_fraction[index:]


def convergents_sqrt(n: int) -> Generator[Fraction, None, None]:
    initial, repeat = continued_fraction_sqrt(n)
    convergents = convergent_sequence(chain(initial, cycle(repeat)))

    yield from convergents

Make continued fractions sqrt much faster
Make continued fractions sqrt much faster

  from fractions import Fraction
  from math import sqrt
  from itertools import chain, cycle
  
  from typing import Generator, Iterable, List, Tuple
+ 
+ from .gcd import gcd
+ from ..sqrt import fsqrt
  
  
  def convergent_sequence(generator: Iterable[int]) -> \
          Generator[Fraction, None, None]:
      h = (0, 1)
      k = (1, 0)
  
      for a in generator:
          h = h[1], a * h[1] + h[0]
          k = k[1], a * k[1] + k[0]
  
          yield Fraction(h[-1], k[-1])
  
  
  def continued_fraction_sqrt(n: int) -> Tuple[List[int], List[int]]:
+     sqrt_n = sqrt(n)
      remainders = []
+     remainder = (0, 1)
+     # remainder is an + (sqrt(n) - p) / q and these are initial.
      continued_fraction = []
-     remainder = (Fraction(1), Fraction(0))  # remainder is sqrt(n) + 0.
- 
-     sqrt_n = sqrt(n)
  
      while remainder not in remainders:
          remainders.append(remainder)
+         p, q = remainder
  
-         a = int(remainder[0] * sqrt_n + remainder[1])
+         q = (n - (p * p)) // q
+         a = int((sqrt_n + p) / q)
+         p = a * q - p
+ 
          continued_fraction.append(a)
  
+         remainder = (p, q)
-         norm = (remainder[1] - a) ** 2 - remainder[0] ** 2 * n
-         remainder = (-remainder[0] / norm, (remainder[1] - a) / norm)
  
      index = remainders.index(remainder)
  
-     return continued_fraction[:index], continued_fraction[index:]
+     return continued_fraction[1:index], continued_fraction[index:]
  
  
  def convergents_sqrt(n: int) -> Generator[Fraction, None, None]:
      initial, repeat = continued_fraction_sqrt(n)
      convergents = convergent_sequence(chain(initial, cycle(repeat)))
  
      yield from convergents
  
Make continued fractions sqrt much faster
## Code Before:
from fractions import Fraction
from math import sqrt
from itertools import chain, cycle

from typing import Generator, Iterable, List, Tuple


def convergent_sequence(generator: Iterable[int]) -> \
        Generator[Fraction, None, None]:
    h = (0, 1)
    k = (1, 0)

    for a in generator:
        h = h[1], a * h[1] + h[0]
        k = k[1], a * k[1] + k[0]

        yield Fraction(h[-1], k[-1])


def continued_fraction_sqrt(n: int) -> Tuple[List[int], List[int]]:
    remainders = []
    continued_fraction = []
    remainder = (Fraction(1), Fraction(0))  # remainder is sqrt(n) + 0.

    sqrt_n = sqrt(n)

    while remainder not in remainders:
        remainders.append(remainder)

        a = int(remainder[0] * sqrt_n + remainder[1])
        continued_fraction.append(a)

        norm = (remainder[1] - a) ** 2 - remainder[0] ** 2 * n
        remainder = (-remainder[0] / norm, (remainder[1] - a) / norm)

    index = remainders.index(remainder)

    return continued_fraction[:index], continued_fraction[index:]


def convergents_sqrt(n: int) -> Generator[Fraction, None, None]:
    initial, repeat = continued_fraction_sqrt(n)
    convergents = convergent_sequence(chain(initial, cycle(repeat)))

    yield from convergents

## Instruction:
Make continued fractions sqrt much faster
## Code After:
from fractions import Fraction
from math import sqrt
from itertools import chain, cycle

from typing import Generator, Iterable, List, Tuple

from .gcd import gcd
from ..sqrt import fsqrt


def convergent_sequence(generator: Iterable[int]) -> \
        Generator[Fraction, None, None]:
    h = (0, 1)
    k = (1, 0)

    for a in generator:
        h = h[1], a * h[1] + h[0]
        k = k[1], a * k[1] + k[0]

        yield Fraction(h[-1], k[-1])


def continued_fraction_sqrt(n: int) -> Tuple[List[int], List[int]]:
    sqrt_n = sqrt(n)
    remainders = []
    remainder = (0, 1)
    # remainder is an + (sqrt(n) - p) / q and these are initial.
    continued_fraction = []

    while remainder not in remainders:
        remainders.append(remainder)
        p, q = remainder

        q = (n - (p * p)) // q
        a = int((sqrt_n + p) / q)
        p = a * q - p

        continued_fraction.append(a)

        remainder = (p, q)

    index = remainders.index(remainder)

    return continued_fraction[1:index], continued_fraction[index:]


def convergents_sqrt(n: int) -> Generator[Fraction, None, None]:
    initial, repeat = continued_fraction_sqrt(n)
    convergents = convergent_sequence(chain(initial, cycle(repeat)))

    yield from convergents
