Function for Diophantine equations of form x^2 - N * y^2 = 1

Question

The problem that I'm having is in properly executing the 'chakravala' method in Python. It runs properly up until n = 181. I've tried to integrate the composition method into my function, but run into a decimal.Overflow almost instantly.

The string literal is my attempt at the integration, everything else is the function which runs off of this loop:

    for n in natural_number_generator(1):
    print(n)
    if n in squares_list:
        continue
    else:
        a = floor(sqrt(n))
        b = 1
        k = a ** 2 - n
        answer_list.append(chakravala(n, a, b, k))
        if answer_list[-1][1] > maximum:
            maximum = answer_list[-1][1]
            answer = answer_list[-1][0]
    # Breaks out of main loop when N reaches limit.
    if n >= limit:
        break

Actual Function:

def chakravala(n, a, b, k):
    # Creates variables and prints to check.
    m_list = []
    print(a, b, k)
    minimum = inf

    # Final step of iteration
    if k == 1:
        return [n, a, b]

    #TODO: Fix
    """
    if k in [-1, -2, -4, 2, 4]:
        while True:
            a, b = a ** 2 + n * b ** 2, 2 * a * b
            k = k ** 2
            if k != 1:
                a, b = Decimal(a / sqrt(k)), Decimal(b / sqrt(k))
                k = Decimal(k / k)
            else:
                a, b = Decimal(a / k), Decimal(b / k)
                k = Decimal(k / k)
            print(a, b, k)
            if float(a).is_integer() and float(b).is_integer():
                return [n, a, b]
            else:
                continue"""

    # Fills our m_list.
    for m in natural_number_generator(1):
        if (a + b * m) % abs(k) == 0:
            m_list.append(m)
            if m >= 2 * n:
                break

    # Finds the m for which abs(m^2 - n) is minimized.
    for i, check_m in enumerate(m_list):
        difference = check_m ** 2 - n
        if difference < minimum:
            m = check_m
            minimum = difference
        elif difference > minimum:
            break

    # Creates the next set of variables for iteration.
    a, b = (a * m + n * b) / abs(k), (a + m * b) / abs(k)
    k = (m ** 2 - n) / k
    a, b, k = int(a), int(b), int(k)
    return chakravala(n, a, b, k)

Any assistance much, much appreciated.

Answer 1

Problem solved over on math.stackexchange.com! The problem I was running into at n = 181 was that I was using float variables and they stepped over the invisible boundary of 2^52. To "solve" the problem, simply insert a few // in the place of /.

Code:

def chakravala(n, a, b, k):
# Creates variables and prints to check.
m_list = []
minimum = inf
m = 0
# Final step of iteration
if k == 1:
    return [n, a, b]

# Fills our m_list.
for m in natural_number_generator(1):
    if (a + b * m) % abs(k) == 0:
        m_list.append(m)
        if m >= 2 * n:
            break

# Finds the m for which abs(m^2 - n) is minimized.
for i, check_m in enumerate(m_list):
    difference = check_m ** 2 - n
    if difference < minimum:
        m = check_m
        minimum = difference
    elif difference > minimum:
        break

# Creates the next set of variables for iteration.
a, b = (a * m + n * b) // abs(k), (a + m * b) // abs(k)
k = (m ** 2 - n) // k
return chakravala(n, a, b, k)

Again a thank you to Sil over on math.stackexchange.com :)