Exponentially increasing number towards maximum

Question

I'm trying to build a retry mechanism for sending e-mails. I'd like it to be configurable so that administrators can specify both;

• The number of retries (intervals)
• The maximum number of seconds before giving up

A further requirement is that the number of seconds to wait between each retry increases exponentially (or follows some other geometric sequence) up to the maximum.

Another way of describing the problem is: How can the maximum number of seconds be divided up into X number of intervals where each interval is exponentially larger than its predecessor?

I'm not sure if this can be expressed using a purely mathematical representation, if not examples in C# would be welcomed. However, I'm really just looking for the logic here so provided the it's well explained I'm sure any language could be easily translated.

Answer 1

I am not sure how useful this answer is but it was certainly fun to create. What makes this answer somewhat different is that it computes the base used for the exponential computation of the time intervals.

So the input is a total time as well as a number of intervals to divide this time span into. The length of the first interval is specified and the challenge is to compute the remaining intervals to ensure that they increase exponentially and sum to the total time.

This can be formulated as a mathematical equation:

t∙x⁰ + t∙x¹ + ... + t∙xⁿ = T

t is the length of the first interval and T is the total time. n is the number of intervals and x is the unknown base.

Assuming that x is not 1 then this equation can be rewritten into a standard form for a polynomial equation:

xⁿ - r∙x + r - 1 = 0

where r = T/t is the ratio between the total time and the length of the first interval.

As far as I know this equation has no general solution but it can be solved using an algorithm in a numerical analysis library. I chose a Newton-Raphson algorithm from the Math.Net Numerics library available on NuGet. For this algorithm the first derivative of the polynomium is required and this is

n∙x^{n - 1} - r

Putting it all together to create a sequence of exponentially growing time spans to wait:

IEnumerable<TimeSpan> ExponentialTimeSpans(TimeSpan firstTimeSpan, TimeSpan totalTimeSpan, Int32 count) {
  var ratio = totalTimeSpan.TotalSeconds/firstTimeSpan.TotalSeconds;
  var @base = RobustNewtonRaphson.FindRoot(
    x => Math.Pow(x, count) - ratio*x + ratio - 1,
    x => count*Math.Pow(x, count - 1) - ratio,
    1d + 1E-8, // Assume that base is > 1
    100d // Arbitrary (but BIG) upper limit on base
  );
  for (var i = 0; i < count; i += 1)
    yield return TimeSpan.FromSeconds(firstTimeSpan.TotalSeconds*Math.Pow(@base, i));
}

Note that you easily can provide input with no solutions and that will result in an exception being thrown. However, any sensible input based on the original problem statement should work as expected.

Answer 2

Some math : Lets have variable T (total time), N (number of retries), t (time of first try) and e (exponent). Each try would take: t*1 , t*e, t*e*e, t*e*e*e, etc..

So total time can be written as T = t*e^0 + t*e^1 + t*e^2 +.. + t*e^N rewritten : T = t*(e^0+e^1+e^2 .. + e^N). We can calculate the sum of powers as : sum = (e^N-1)/(e-1) .

So given T, N and e, we can calculate t as : t = T/((e^N-1)/(e-1))

To calculate time for ith iteration use : ti = t*e^i

For example, given T = 124(s), N = 5(tries) and e = 2, the first interval will be 124/((2^5-1)/(2-1)) = 4s . The following intervals will then be :

• 0th interval: 4s (t*e^0)
• 1st interval: 4*2 = 8s (t*e^1)
• 2nd interval: 8*2 = 4*2*2 = 16s (t*e^2)
• 3rd interval: 16*2 = 4*2*2*2 = 32s (t*e^3)
• 4nd interval: 32*2 = 4*2*2*2*2 = 64s (t*e^4)

For total time of 124s of waiting.

Sorry for the formatting. This question would probably be better for Mathematics.

The code to calculate all intervals would be :

public static void TestFunction(int max, int numIntervals) {

    List<double> intervals = new List<double>();

    double exponent = 2;

    double n = Math.Pow(exponent, numIntervals) - 1;
    double d = exponent - 1;

    double t = max / (n / d);

    for (int x = 0; x < numIntervals; x++) {
        double interval = t * Math.Pow(exponent, x);
        intervals.Add(interval);
    }

}

Answer 3

Step one - a simple solution - work in reverse! (Where the reduction is 50%)

I need to fit 10 intervals into 128 seconds.

Interval :  Time (Of occurrence)
1        :  128
2        :  64
3        :  32
4        :  16
5        :  8
6        :  4
7        :  2
8        :  1
9        :  1/2
10       :  1/4

Note: The above works fine (to keep under X, just start with X/2). The below, not so much. This techniques can be applies iteratively to find a 'good' solution though for now.

Great, but what happens if we need a minimum? 1/128th of a second between retries at the start may be unnecessary. So what we need to do, is vary the exponential.

Now the above can be written as result = 1/4 * 2^9 or more generally result = startingInterval * 2^(n-1). However we know the result we want, so we need to rearrange this formula.

(result/startingInterval)^(1/(n-1)) = base

With the above values: (128/(1/4))^(1/(10-1)) = base = 2

Or in other words, to get a total time of 128s starting with an interval of 1/4s and using 10 attempts (including the first one) then we need to increase the length between intervals by a factor of 2 each attempt.

Answer 4

Declare a max threshold value as well an offset to be added for each retry.

int maxRetryCount = 5;
int offSet = 10000;
int currRetryCount = 0;
int waitTime = 1000; //default value

while(currRetryCount < maxRetryCount)
{
    try
    {
        //Send Email 
        // break out once the email is send
        break;
    }
    catch
    {
        //Wait for a while
        Thread.Sleep(waitTime);

        //increase the wait time for next time
        waitTime += offSet;
        currRetryCount++;
    }
}

Here the code will attempt for at most 5 times to send an email where the wait time will increase by 10 sec each time.

Answer 5

Something like the following maybe?

var time_in_seconds = 10000; // usually done in milliseconds, so lets say 10 sec.

// if email fails:
time_in_seconds *= 10; 
// So, next will be 100, 1000, etc. & you get your exponential increment.