# CS 526 Project 4 helper functions

# The below code is taken from SymPy
# Used under fair-use.
# https://raw.githubusercontent.com/sympy/sympy/733da515a7638bba4e08be366bf24c996ad84a61/sympy/core/power.py

from math import log as _log

def integer_nthroot(y, n):
    """
    Return a tuple containing x = floor(y**(1/n))
    and a boolean indicating whether the result is exact (that is,
    whether x**n == y).

    >>> from sympy import integer_nthroot
    >>> integer_nthroot(16,2)
    (4, True)
    >>> integer_nthroot(26,2)
    (5, False)

    """
    y, n = int(y), int(n)
    if y < 0:
        raise ValueError("y must be nonnegative")
    if n < 1:
        raise ValueError("n must be positive")
    if y in (0, 1):
        return y, True
    if n == 1:
        return y, True
    if n == 2:
        x, rem = _sqrtrem_python(y)
        return int(x), not rem
    if n > y:
        return 1, False
    # Get initial estimate for Newton's method. Care must be taken to
    # avoid overflow
    try:
        guess = int(y**(1./n) + 0.5)
    except OverflowError:
        exp = _log(y, 2)/n
        if exp > 53:
            shift = int(exp - 53)
            guess = int(2.0**(exp - shift) + 1) << shift
        else:
            guess = int(2.0**exp)
    if guess > 2**50:
        # Newton iteration
        xprev, x = -1, guess
        while 1:
            t = x**(n - 1)
            xprev, x = x, ((n - 1)*x + y//t)//n
            if abs(x - xprev) < 2:
                break
    else:
        x = guess
    # Compensate
    t = x**n
    while t < y:
        x += 1
        t = x**n
    while t > y:
        x -= 1
        t = x**n
    return x, t == y

# This code written by David Adrian, make fun of it!
import base64

def integer_to_base64(z):
    '''Converts an arbitrarily long integer to a big-endian base64 encoding'''
    s = ("%x"%z); s = (('0'*(len(s)%2))+s).decode('hex')
    return base64.b64encode(s)


def integer_to_bytes(n):
    '''Converts an arbitrarily long integer to bytes, big-endian'''
    negative = True if n < 0 else False
    out = list()
    while n > 0:
        out.append(chr(n & 0xFF))
        n >>= 8
    if not negative:
        out.append(chr(0x00))
    return ''.join(reversed(out))

def bytes_to_integer(b):
    '''Converts big-endian bytes to an arbitrarily long integer'''
    out = 0L
    for c in b:
        out <<= 8
        assert(ord(c) >= 0)
        out += ord(c)
        assert(out >= 0)
    return out

