Why does my python code produce an infinite loop if the number is larger than or equal to 772000000000000?

Question

I have a code that is supposed to produce the lowest monthly payment you need to make to payoff a balance within a year. It works perfectly for all numbers until (so far as I've tested) 772000000000000.

Here is the code (numbers I've tested are below with their results):

import time
balance = float(input("balance: "))
annualInterestRate = float(input("AIR: "))

# formulas for lower and higher binding for bisectional search
monthlyInterestRate = annualInterestRate / 12
lower = balance / 12
higher = (balance * (1 + monthlyInterestRate) ** 12) / 12

while True:
    guess = ((higher - lower) / 2 + lower)
    print('higher: %s' % higher)
    print('lower: %s' % lower)
    remaining = balance

    for i in range(12):
        unpaid = remaining - guess
        remaining = unpaid + monthlyInterestRate*unpaid

    if higher - lower <= .01 and remaining < 0:
        result = lower
        print("Lowest Payment: %s" % result)
        break

    elif higher - lower <= .01 and remaining >= 0:
        result = higher
        print("Lowest Payment: %s" % result)
        break

    elif remaining < -0.01:
        higher = guess
        print("remaining: %s" % remaining)
        print(guess)
        print('too high')
        time.sleep(.5)

    elif remaining > 0:
        lower = guess
        print("remaining: %s" % remaining)
        print(guess)
        print('too low')
        time.sleep(.5)

As I said, this gives the correct result for every number I tested but then I tested 999999999999999 and I got an infinite loop, I narrowed down where the issues start happening by testing the following values all using .2 as the AIR, using different AIR can produce different but similar results depending on the number, but the following should give you a good idea of what's happening:

662000000000000 works

771999999999999 works

772000000000000 repeats higher and lower over and over again after some time

772100000000000 works

772200000000000 repeats higher and lower over and over again after some time

772300000000000 infinite loop

772400000000000 infinite loop

772500000000000 infinite loop

882100000000000 infinite loop

999999999999999 infinite loop

Feel free to try them yourself, I'm completely dumbfounded why this is happening?

Answer 1

If you use floats you have to consider that these cannot represent all possible decimal values. If the values get big enough the difference between two representable floating point values might just exceed your threshold. That leads to a situation where the bisection cannot progress because there is just no "middle" float between the values. For example with:

balance = float("772300000000000")
annualInterestRate = float("0.2")

It ends up in an infinite loop with:

higher: 70368815315719.6
lower: 70368815315719.58

So, let's examine this a bit:

>>> a = 70368815315719.6
>>> b = 70368815315719.58
>>> import numpy as np
>>> np.nextafter(a, 0) == np.float64(b)
True
>>> np.nextafter(b, np.inf) == np.float64(a)
True

So there's no float between a and b but:

>>> b - a
-0.015625

So this is bigger than your threshold. So nothing can change between loops which results in the infinite loop.

However, you can easily fix this by using an arbitary precision Fraction:

from fractions import Fraction
balance = Fraction("772300000000000")
annualInterestRate = Fraction("0.2")

... # rest of your code

All operations in your code preserve the Fraction (if you had used math functions or ** it could be different) and at least on my computer it eventually finishes with:

higher: 161683724083791631395206486083981108997/2297661589986627614146560
lower: 41391033365450653948925712865241263190149/588201367036576669221519360
Lowest Payment: 161683724083791631395206486083981108997/2297661589986627614146560

Note the / in the output which comes from the Fraction.