Exponential backoff

Question

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.

You need to solve the equation, for a degree up to 7 there are articles on wikipedia en.wikipedia.org/wiki/Algebraic_equation#See_also If it does not need to be extremely precise - you can always brute-force (with binary search it would be quick) — zerkms
I'm voting to close this question as off-topic because it is not about programming. — High Performance Mark

Patrick87 Patrick87 · Accepted Answer · 2019-04-11T15:37:45

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

Exponential backoff

1 Answers