#!/usr/bin/env python3
from Crypto.PublicKey import RSA
from Crypto.Util import number
from sympy.ntheory.continued_fraction import continued_fraction_iterator, continued_fraction_reduce
import math
import random

def chunks(l, n):
    """Yield successive n-sized chunks from l."""
    for i in range(0, len(l), n):
        yield l[i:i + n]

def write(name, message):
	if type(message) == int:
		message = str(message)
	writer = open(name,'w')
	writer.write(message)
	writer.close()

def random_string(length):
	return ''.join([chr(random.randint(32,255)) for _ in range(length)])

def ggt(a,b):
	if b == 0:
		return a
	return ggt(b, a % b)

def int_to_str(n):
	if n == 0:
		return ''
	return int_to_str(n // 256) + chr(n % 256)

def str_to_int(s):
	res = 0
	for char in s:
		res *= 256
		res += ord(char)
	return res

def bisect(f, low, up, rounding = 0):
	flow = f(low)
	fup = f(up)
	if flow == 0: return low
	if fup == 0: return up
	if flow * fup > 0: raise Exception('bad interval')
	if flow < 0:
		return _bisect(f, low,up,rounding)
	else:
		return _bisect(lambda x: -f(x), low, up,rounding)

def _bisect(f, low, up, rounding):
	"""Find root by bisection. Require: f(low) < 0 < f(up)."""
	if up <= low + 1:
		if rounding == 1:
			return up
		elif rounding == -1:
			return low
		else:
			raise Exception('no root or bad function')
	mid = (low + up) // 2
	midval = f(mid)
	if midval == 0: return mid
	if midval < 0: return _bisect(f, mid, up, rounding)
	if midval > 0: return _bisect(f, low, mid, rounding)

def cf_list(number, iterations):
	res = []
	cf = []
	gen = continued_fraction_iterator(number)
	for _ in range(iterations):
		cf.append(next(gen))
		frac = continued_fraction_reduce(cf)
		res.append(frac)
	return res