A Sequence Of Predictable Events

| 0 Comments

With our various pseudo random number generators[1][2] we have sought to create sequences of numbers that come as close as possible to having all of the properties of truly random variables, despite being entirely deterministic.
Now this behaviour is somewhat atypical, in the sense that most sequences that we bother to name have values that are self-evidently deterministic.

Arithmetic For Beginners

Perhaps the simplest of these are arithmetic sequences, having values \(s_i\) that are consecutively separated by a constant difference \(d\)
\[ s_{i+1} - s_i = d \]
If we start with a value of \(a\), then the sequence will trivially progress with
\[ \begin{align*} s_1 &= a\\ s_2 &= a + d\\ s_3 &= a + 2 \times d\\ s_4 &= a + 3 \times d\\ \vdots \end{align*} \]
yielding an \(i^\mathrm{th}\) term of
\[ s_i = a + (i-1) \times d \]
A natural way to implement a sequence is as a function returning the term at a given index. To ensure that such a function implementing an arithmetic sequence has the required first term and difference we must create it with another function that takes them as arguments, much as we did to create pseudo random number generators with particular parameters and/or seeds.
Listing 1 gives the implementation of a function to create arithmetic sequences in exactly this manner.

Listing 1: ak.arithmeticSequence
ak.arithmeticSequence = function(a, d) {
 if(ak.nativeType(a)!==ak.NUMBER_T || !isFinite(a)) {
  throw new Error('invalid first term in ak.arithmeticSequence');
 }

 if(ak.nativeType(d)!==ak.NUMBER_T || !isFinite(d)) {
  throw new Error('invalid difference in ak.arithmeticSequence');
 }

 return function(i) {
  if(i!==ak.floor(i) || i<0) {
   throw new Error('invalid index in ak.arithmeticSequence');
  }
  return a + i*d;
 };
};

Here we first check that the first term and difference are both finite numbers before returning a function that implements the arithmetic sequence defined by them. Note that we're following the convention of array indices by starting the sequence at zero rather than one.

Unfortunately, this implementation has a rather subtle bug; if the difference is zero then every term must be equal to the first term, even at the limit of infinity for which the function that it creates would instead return the sum of the first term and infinity multiplied by zero which is not a number, or in other words NaN.
To correct this we must treat a difference of zero as a special case, as is done in listing 2.

Listing 2: The Corrected ak.arithmeticSequence
ak.arithmeticSequence = function(a, d) {
 if(ak.nativeType(a)!==ak.NUMBER_T || !isFinite(a)) {
  throw new Error('invalid first term in ak.arithmeticSequence');
 }

 if(ak.nativeType(d)!==ak.NUMBER_T || !isFinite(d)) {
  throw new Error('invalid difference in ak.arithmeticSequence');
 }

 if(d!==0) {
  return function(i) {
   if(i!==ak.floor(i) || i<0) {
    throw new Error('invalid index in ak.arithmeticSequence');
   }
   return a + i*d;
  };
 }

 return function(i) {
  if(i!==ak.floor(i) || i<0) {
   throw new Error('invalid index in ak.arithmeticSequence');
  }
  return a;
 };
};

Program 1 demonstrates this implementation, which can be found in ArithmeticSequence.js
.
Program 1: ak.arithmeticSequence

Learn Your Sums

One of the things that we're interested in about sequences are the sums of their terms, known as series. Specifically, the \(i^\mathrm{th}\) term of a series is the sum of all of the terms up to and including the \(i^\mathrm{th}\) term of its associated sequence, or in other words
Derivation 1: The Correctness Of The Arithmetic Series
Firstly, note that
\[ S_1 = 1 \times a + \tfrac{1}{2} \times 1 \times 0 \times d = a = s_1 \]
Next, we have
\[ S_{n+1}-S_n\\ \;= \left((n+1)a + \tfrac{1}{2} (n+1) n d\right) - \left(na + \tfrac{1}{2} n (n-1) d\right)\\ \;= \left((n+1)a - na\right) + \left(\tfrac{1}{2} (n+1) n d - \tfrac{1}{2} n (n-1) d\right)\\ \;= a + \tfrac{1}{2} \left((n+1) - (n-1)\right) n d\\ \;= a + \tfrac{1}{2} \times 2 \times nd = a + nd = s_{n+1} \]
\[ S_n = \sum_{i=1}^n s_i \]
where \(\sum\) is the summation sign.

The terms of an arithmetic series are given by
\[ S_n = n \times a + \tfrac{1}{2} \times n \times (n-1) \times d \]
which we can easily confirm by checking that the first term of the series is the same as the first term of the sequence and that the difference between \(S_n+1\) and \(S_n\) is \(s_{n+1}\), as is done in derivation 1.

When it come to the implementation we must be just as careful to deal with corner cases as we were for arithmetic sequences. Specifically, if we want to handle the infinite limits of arithmetic series correctly we need to treat first terms and differences of zero as special cases so that we never multiply zero by infinity, as done in listing 3.

Listing 3: ak.arithmeticSeries
ak.arithmeticSeries = function(a, d) {
 if(ak.nativeType(a)!==ak.NUMBER_T || !isFinite(a)) {
  throw new Error('invalid first term in ak.arithmeticSeries');
 }

 if(ak.nativeType(d)!==ak.NUMBER_T || !isFinite(d)) {
  throw new Error('invalid difference in ak.arithmeticSeries');
 }

 if(a!==0 && d!==0) {
  return function(i) {
   if(i!==ak.floor(i) || i<0) {
    throw new Error('invalid index in ak.arithmeticSeries');
   }
   return (i+1)*(a + 0.5*i*d);
  };
 }

 if(a!==0) {
  return function(i) {
   if(i!==ak.floor(i) || i<0) {
    throw new Error('invalid index in ak.arithmeticSeries');
   }
   return (i+1)*a;
  };
 }

 if(d!==0) {
  return function(i) {
   if(i!==ak.floor(i) || i<0) {
    throw new Error('invalid index in ak.arithmeticSeries');
   }
   return 0.5*i*(i+1)*d;
  };
 }

 return function(i) {
  if(i!==ak.floor(i) || i<0) {
   throw new Error('invalid index in ak.arithmeticSeries');
  }
  return 0;
 };
};

Note that we are again following the convention of starting with an index of zero rather than one.

This implementation can be found in ArithmeticSeries.js and is demonstrated by program 2.

Program 2: ak.arithmeticSeries

Multiplying Our Efforts

Geometric sequences, in contrast, have consecutive elements \(s_i\) that differ by a constant ratio \(r\)
\[ s_{i+1} \div s_i = r \]
and so progress from a first term \(a\) as
\[ \begin{align*} s_1 &= a\\ s_2 &= a \times r\\ s_3 &= a \times r^2\\ s_4 &= a \times r^3\\ \vdots\\ s_i &= a \times r^{i-1}\\ \end{align*} \]
When implementing geometric sequences we must yet again take care to treat the corner cases at the infinite limit correctly.
Firstly, if the first term is zero, then every term must equal zero. If we were to use the above formula, then we might end up multiplying zero by infinity at the limit, yielding NaN rather than zero.
Secondly, if the ratio is less than or equal to minus one then the sequence will oscillate between non-decreasing positive and negative multiples of \(a\) and so we cannot meaningfully determine its sign at the infinite limit, which we shall indicate by returning NaN.
Finally, in JavaScript one to the power of infinity is NaN and so we must treat it as a special case too.

Listing 4 gives the implementation of ak.geometricSequence which creates one of three functions that cover all of these cases to implement sequences that again start at an index of zero.

Listing 4: ak.geometricSequence
ak.geometricSequence = function(a, r) {
 if(ak.nativeType(a)!==ak.NUMBER_T || !isFinite(a)) {
  throw new Error('invalid first term in ak.geometricSequence');
 }

 if(ak.nativeType(r)!==ak.NUMBER_T || !isFinite(r)) {
  throw new Error('invalid ratio in ak.geometricSequence');
 }

 if(a!==0 && r<=-1) {
  return function(i) {
   if(i!==ak.floor(i) || i<0) {
    throw new Error('invalid index in ak.geometricSequence');
   }
   return isFinite(i) ? a * Math.pow(r, i) : ak.NaN;
  };
 }

 if(a!==0 && r!==1) {
  return function(i) {
   if(i!==ak.floor(i) || i<0) {
    throw new Error('invalid index in ak.geometricSequence');
   }
   return a * Math.pow(r, i);
  };
 }

 return function(i) {
  if(i!==ak.floor(i) || i<0) {
   throw new Error('invalid index in ak.geometricSequence');
  }
  return a;
 };
};

Note that the third function handles both \(a\) equal to zero and \(r\) equal to one, since in both cases every term must equal \(a\).

Program 3 illustrates the use of this function, which is defined in GeometricSequence.js.

Program 3: ak.geometricSequence

Derivation 2: The Correctness Of The Geometric Series
The first term is given by
\[ S_1 = a \times \frac{1-r^1}{1-r} = a \times \frac{1-r}{1-r} = a = s_1 \]
and adding \(s_{n+1}\) to \(S_n\) yields
\[ \begin{align*} s_{n+1} + S_n &= a \times r^n + a \times \frac{1-r^n}{1-r}\\ &= a \times \left(r^n + \frac{1-r^n}{1-r}\right)\\ &= a \times \frac{(1-r) \times r^n + \left(1-r^n\right)}{1-r}\\ &= a \times \frac{r^n - r^{n+1} + 1 - r^n}{1-r}\\ &= a \times \frac{1 - r^{n+1}}{1-r} = S_{n+1} \end{align*} \]
The geometric series of the sum of the first \(n\) terms of a geometric sequence is given by
\[ S_n = a \times \frac{1-r^n}{1-r} \]
as proven by derivation 2.

Unfortunately, we'll run into trouble again if \(r\) is exactly equal to one since this time we'll end up dividing zero by zero. To handle this, we need simply note that every term of the geometric sequence is equal to the first and so the sum of \(n\) of them is trivially
\[ S_n = a \times n \]
This means that we must treat the case of \(a\) equal to zero separately from that of \(r\) equal to one if we are to be sure that we'll never multiply zero by infinity.
Finally, if \(r\) is less than or equal to minus one, then the terms will oscillate just as they did for the sequence which we shall again handle by returning NaN at the infinite limit.

The ak.geometricSeries function given in listing 5 covers all of these cases and, as usual, creates series that start from an index of zero.

Listing 5: ak.geometricSeries
ak.geometricSeries = function(a, r) {
 var mul;

 if(ak.nativeType(a)!==ak.NUMBER_T || !isFinite(a)) {
  throw new Error('invalid first term in ak.geometricSeries');
 }

 if(ak.nativeType(r)!==ak.NUMBER_T || !isFinite(r)) {
  throw new Error('invalid ratio in ak.geometricSeries');
 }

 if(a!==0 && r<=-1) {
  mul = 1/(1-r);

  return function(i) {
   if(i!==ak.floor(i) || i<0) {
    throw new Error('invalid index in ak.geometricSeries');
   }
   return isFinite(i+1) ? a*(1-Math.pow(r, i+1))*mul : ak.NaN;
  };
 }

 if(a!=0 && r!==1) {
  mul = 1/(1-r);

  return function(i) {
   if(i!==ak.floor(i) || i<0) {
    throw new Error('invalid index in ak.geometricSeries');
   }
   return a*(1-Math.pow(r, i+1))*mul;
  };
 }

 if(a!==0) {
  return function(i) {
   if(i!==ak.floor(i) || i<0) {
    throw new Error('invalid index in ak.geometricSeries');
   }
   return (i+1)*a;
  };
 }

 return function(i) {
  if(i!==ak.floor(i) || i<0) {
   throw new Error('invalid index in ak.geometricSeries');
  }
  return 0;
 };
};

This function can be found in GeometricSeries.js and is demonstrated by program 4.

Program 4: ak.geometricSeries

Unlike arithmetic series, geometric series can have finite values at their infinite limits even when the first term is non-zero. Specifically, if the ratio lies strictly between plus and minus one, we have
\[ S_\infty = \frac{a}{1-r} \]
Program 5 illustrates the finite, infinite and oscillatory limits of a few different geometric series.

Program 5: Some Infinite Limits

A Useful Reminder?

Mathematically speaking, arithmetic and geometric sequences and series are so trivial that they aren't typically given dedicated functions. However, I think that the subtleties of their implementations have served as a useful reminder of how careful we need to be if we are to use floating point arithmetic effectively, but also that if we are sufficiently careful then we can create functions that behave reasonably for all valid arguments!

References

[1] Talkin' 'Bout My Generators, www.thusspakeak.com, 2016.

[2] Let's Twist Again, www.thusspakeak.com, 2016.

Leave a comment