Exponential backoff

Let's say I had the equation T = sum(A**n) for n from 1 to M.

Now let's say I knew M and T, but wanted A. How would I solve for A?

I want to do an exponential backoff in the event of an error, but I don't want the total time spent backing off to be greater than T, nor the maximum number of retries to exceed M. So I'd need to find A.

The closed-form solution for sum(A**n) for n from 1 to M is (A^(M+1) - 1) / (A - 1) - 1. To see this work, let M = 3 and A = 2. Then 2^1 + 2^2 + 2^3 = 14, and (2^4 - 1) / (2 - 1) - 1 = 15 / 1 - 1 = 14.

So, we have the closed form expression T = (A ^ (M + 1) - 1) / (A - 1) - 1. This is a transcendental equation and has no closed-form solution. However, because the RHS is monotonically increasing in A (bigger values of A always give bigger values of the expression) then we can do what amounts to binary search to find an answer to arbitrary precision:

L = 0
H = MAX(T, 2)
A = (L + H) / 2
while |(A ^ (M + 1) - 1) / (A - 1) - 1 - T| > precision
    if (A ^ (M + 1) - 1) / (A - 1) - 1 > T then
        H = A
    else then
        L = A
    end if
    A = (L + H) / 2
loop

Example: T = 14, M = 3, epsilon = 0.25

L = 0
H = MAX(15, 2) = 14
A = L + H / 2 = 7

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 385 > 0.25
H = A = 7
A = (L + H) / 2 = 3.5

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 44.625 > 0.25
H = A = 3.5
A = (L + H) / 2 = 1.75

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 3.828125 > 0.25
L = A = 1.75
A = (L + H) / 2 = 2.625

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 13.603515625 > 0.25
H = A = 2.625
A = (L + H) / 2 = 2.1875

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 3.440185546875 > 0.25
H = A = 2.1875
A = (L + H) / 2 = 1.96875

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 0.524444580078125 > 0.25
L = A = 1.96875
A = (L + H) / 2 = 2.078125

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 1.371326446533203125 > 0.25
H = A = 2.078125
A = (L + H) / 2 = 2.0234375

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 0.402295589447021484375 > 0.25
H = A = 2.0234375
A = (L + H) / 2 = 1.99609375

|(A ^ (M + 1) - 1) / (A - 1) - 1 - T|
 = 0.066299498081207275390625 < 0.25

Solution: 1.99609375